AVL Tree

AVL Tree is a self-balancing BST where for any node - the difference in height of the left and the right subtree can not be more than $1$.

Therefore, the strucwture of the AVL tree node also stores the height for each node. The structure would look like this:

struct Node {  
    int key;  
    Node *left;  
    Node *right;  
    int height;  
}; 

$height(node) = max\{height(node.left), \space height(node.right)\} + 1$

---

Implementation

The search operation doesn’t change and remains the same as discussed in the BST chapter.

As discussed earlier, the implementation is not very relevant but for understanding, we’ll discuss the insert operation. If you understand BST, extending these operations to self-balancing BST should be intuitive.

---

Insertion

The first part of insertion is the same as BST, we traverse the BST to find the position where the new key needs to go.

Once the new key is added, it changes the height of its ancestors i.e., nodes on the path from the root to this node. The height of the other nodes remains the same. This means that only the nodes on the path might need rotation to balance the subtrees. This we can do recursively as we move up after adding the new node.

In the worst case, we end up rotating all such nodes. There are $logN$ such nodes since the height is $logN$. So the time complexity is $O(logN)$.

Let’s understand this better using the below illustration. The sequence of values is $[1,2,3,4,5,6]$, which is the case of simple BST results in a tree of height $N$.