Description:

An AVL tree is another balanced binary search tree. Named after their inventors, Adelson-Velskii and Landis, they were the first dynamically balanced trees to be proposed. Like red-black trees, they are not perfectly balanced, but pairs of sub-trees differ in height by at most 1, maintaining an O(logn) search time. Addition and deletion operations also take O(logn) time.

Def: An AVL tree is a binary search tree with a balance condition i.e the difference between left subtree height and right subtree height is at most 1.

As an Example, among the above binary search trees, the left one is not an AVL tree, whereas the right binary seacrh tree is an AVL tree.

Properties of AVL Tree:-

A binary tree is said to be an AVL tree, if:

1)It is a binary search tree, and2)For any node X, the height of left subtree of X and height of right subtree of X differ by at most 1.3) Every sub-tree is an AVL tree

AVL Tree Declaration :

Since AVL tree is a BST, the declaration of AVL is similar to that of BST. But just to simplify the operations, I also include the height as part of the declaration.

class AVLNode: def _init_ (self,data,balanccFactor,left,right): self.data= data self. balanceFactor = 0 self.left = left self.right= right def height(self): return self.recHeight(self.root) def recHeight(self,root): if root == None: return 0 else: leftH = self.recHeight(r.left) rightH = self. recHeight(r.right) if leftH>rightH: return 1 +leftH else: return 1 +rightH

Minimum/Maximum Number of Nodes in AVL Tree:

For simplicity let us assume that the height of an AVL tree is h and N(h) indicates the number of nodes in AVL tree with height h. To get the minimum number of nodes with height h, we should fill the tree with the minimum

number of nodes possible. That means if we fill the left subtree with height h-1 then we should fill the right subtree with height h - 2. As a result, the minimum number of nodes with height h is:

N(h) = N(h - 1) + N(h - 2) + 1

In the above equation:

%u2022 N(h - 1) indicates the minimum number of nodes with height h - 1.

%u2022 N(h - 2) indicates the minimum number of nodes with height h - 2.

%u2022 ln the above expression, "1" indicates the current node.

We can give N(h -1) either for left subtree or right subtree

AVL tree property is ensuring that the height of an AVL tree with n nodes is O(logn).

## Comments