AVL Trees

An AVL Tree (named after its inventors) is a self-balancing binary search tree.

Height Balance §

A height-balance property $B(n)$ is defined as

$$B(n)=\mathrm{height}(n.left)-\mathrm{height}(n.right)$$

The value of $B(n)$ for a tree can be interpreted as:

• $B(n)>0$ - Tree is left-heavy.
• $B(n)<0$ - Tree is right-heavy.
• $B(n)=0$ - Tree is balanced.

For an AVL tree $n$, it is guaranteed that $|B(n)|\le 1$ .

Following insertions and deletions, rotation operations are performed to maintain height balance.

Rotations §

A rotation is a tree-manipulation operation which moves nodes around in a tree whilst maintaining the required invariants. A rotation in an AVL tree changes the root of the tree.

Right-rotation §

A right-rotation shifts nodes to the right of the tree

graph TB;
    A((A))-->B((B))
    A-->C((z))
    B-->D((x))
    B-->E((y))

Becomes

graph TB;
    A((B))-->B((x))
    A-->C((A))
    C-->D((y))
    C-->E((z))

Left-rotation §

A left-rotation shifts nodes to the left of the tree

graph TB;
    A((A))-->B((z))
    A-->C((B))
    C-->D((y))
    C-->E((x))

Becomes

graph TB;
    A((B))-->B((A))
    A-->C((x))
    B-->D((z))
    B-->E((y))

Left-right rotation §

When there is a left-heavy right subtree, perform a right-rotation on the left subtree, then a left-rotation on the root tree.

Applying Rotations §

After an insertion or deletion, rotation operations should be applied as many times as necessary to balance the tree. This should be applied inwards-out - that is, start with the smallest subtree.