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:

Step by Step

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)