Oldest Self-Balancing Binary Search Tree invented

# AVL Tree

Learned in CS240.

An AVL Tree is a BST with an additional height-balance property at every node: $TheÂ heightsÂ ofÂ theÂ leftÂ andÂ rightÂ subtreeÂ differÂ byÂ atÂ mostÂ 1.$

Important

The height of an empty tree is defined to be $â1$.

If node $v$ has left subtree $L$ and right subtree $R$, then $balance(v):=height(R)âheight(L)â{â1,0,1}$

- $balance(v)=â1$ means $v$ is left-heavy
- $balance(v)=+1$ means $v$ is right-heavy

Theorem

An AVL tree on $n$ nodes has $Î(gn)$ height. search, insert, delete all cost $Î(gn)$ in the worst case!

- See Tree Rotation

In the case of ties

VERY IMPORTANT: Ties must be broken to

prefer single rotation. There are scenarios where if we donât prefer the single rotation, applying double rotation does not result in a valid AVL tree afterwards.

- Note here: the parent here on line 2 refers to the parent of the node with value $k$ after the swap. Like in the example below, calling delete 22, we get the min key of the right subtree, do the swap, and then the parent will be the node with key $31$.