AVL Tree

Named after its inventors Adelson-Velsky and Landis, an AVL Tree rigorously maintains balance by ensuring that for every node, the difference between the heights of its left and right subtrees is never more than 1. If an operation violates this condition, the tree automatically rebalances itself through a series of rotations. This ensures that operations like search, insert, and delete have a worst-case time complexity of O(log n).

How it Works

Every time a node is inserted or deleted, the AVL tree checks the balance factor of each affected node. If a node becomes unbalanced, rotations are performed to restore balance. There are four types of rotations:

• Right Rotation (LL) – Applied when a left child’s left subtree causes imbalance.
• Left Rotation (RR) – Applied when a right child’s right subtree causes imbalance.
• Left-Right Rotation (LR) – Applied when a left child’s right subtree causes imbalance.
• Right-Left Rotation (RL) – Applied when a right child’s left subtree causes imbalance.

Step by Step

1. Insert or delete a node like in a normal BST.
2. Traverse back up to the root, updating height and checking the balance factor of each ancestor.
3. If a node is unbalanced, identify the type of rotation needed (LL, RR, LR, RL).
4. Perform the rotation to restore the AVL property.

Pseudocode

function rebalance(node):

    updateHeight(node)

    nodeBf = balanceFactor(node)

    if nodeBf > 1:

        if balanceFactor(node.left) > 0:

            rotateRight(node)

        else:

            rotateLeft(node.left)

            rotateRight(node)

    if nodeBf < -1:

        if balanceFactor(node.right) < 0:

            rotateLeft(node)

        else:

            rotateRight(node.right)

            rotateLeft(node)

    if node.parent:

        rebalance(node.parent)