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 (known as the "balance factor") is never more than 1 or less 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).

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)