AVL(Adelson-Velskii and Landis) Tree

AVL Tree is the extended version of Binary Search Tree(BST), and also AVL Tree remove the disadvantage of Binary Search Tree(BST).In BST worst Time complexity for searching is O(n). and also in worst case BST is also not an balanced BST. AVL Tree makes Time Complexity for searching is O(Logn) or just height of the Tree.

• AVL Tree is the self balancing data structure.
• AVL Tree use one terminology Balance_Factor to balance the Tree.
• Balance_Factor is actually difference of left subtree height and right subtree height. Example

AVL Tree Properties

There are some Following Properties of AVL Tree :

• AVL Tree is an Binary Search Tree(BST).
• For Every Node(Let’s Say X) of AVL Tree, The Height of left Subtree of X , and Height of right Subtree of X must be differ by at most 1.

Min & Max Number of Nodes in AVL Tree

Mathematically and Logically ,we can drive the Min & Max Number of Node s in AVL tree into the Mathematical Function.
If we assume that h is the height of AVL Tree and N(h) is the total number of nodes with height h.

• To find the Min number of nodes , we have to fill the left subtree with height (h-1) and right subtree will be fill with (h-2) height, then resultant Min Number of nodes in AVL Tree will be

In above Equation :
1-: N(h-1) means minimum number of nodes with h-1 height.
2-: N(h-2) means minimum number of nodes with h-2 height.
3-: 1 is added here for the current node.
Note : we can give N(h-1) either for Left Subtree or right Subtree.
If we solve the above recurrence relation :

In the case of Min-Number of Nodes in AVL Tree , the Mathematial Function is N(h)=O(Logn).

• To find the Max number of nodes , we have to fill both the left subtree and right Subtree with height (h-1), then resultant Max Number of nodes in AVL Tree will be

If we solve the above recurrence relation :

In the case of Max-Number of Nodes in AVL Tree , the Mathematial Function is N(h)=O(Logn).

Operations of AVL Tree

There are some basic operation ,which can apply on the AVL :

• Insertion : Addition of a node.
• Deletion : Removal of a node.
• Searching : Finding the specific elements.
• Traversing : Visiting on all the node at least once.
• And many more :