AVL Trees

Tags

comp-sci

Is a self balancing binary search tree algorithm that works by rotating the tree after insertion and deletion operations to ensure it stays balanced.

In an AVL tree all nodes are locally balanced: The height of the left and right sub-trees [see page 4, differ] by at most 1. That is \( \text{bal}(v) = h(T_l) - h(T_r) \) where \( \text{bal}(v) \in \{ -1, 0, +1 \} \). This property is enforced by recording the height of a node in the node itself (to avoid having to repeatedly calculate it). This doesn't mean that an AVL tree cannot be [see page 5, lop-sided], the tree will always be relatively balanced.

It can be [see page 6, shown] that the height of an AVL tree with at most \( n \) nodes is:

\begin{align*} h \leq \frac{1}{\log (\frac{\sqrt{5} + 1}{2})} \qquad \simeq 1.44 \log n \end{align*}

When inserting an element into an AVL tree we must check whether the left or right sub-trees of the current node or any of its parent nodes have been unbalanced. We then branch depending on whether the tree was lop-sided due to an [see page 14, outside] or [see page 15, inside] problem. There are similar considerations when deleting depending on whether it's an [see page 20, outside] or [see page 21, inside] problem.

[see page 17, Insertion] and [see page 22, removal] has worst-case performance \( \mathcal{O}(h) \).