# AVL tree

Invented by Adelson-Velskii, Landis (1962) for each node of the BST, store its balance = height of the right subtree – height of the left subtree a BST is an AVL tree, if balance of each node is –1, 0, or +1 this ensures that the height of an AVL tree is less than $1.44 \log_2 (n + 2)$ guaranteed $O(\log n)$ time (in the worst case) for each dictionary operation harder to implement avl_set, avl_multiset, and avltree classes in Boost.Intrusive library

## Balancing

When inserting and deleting nodes in an AVL tree, node balances change – but only those on the path from added/deleted node to the root. We update them on a way back to root. Lets say the balance of a node $y$ decreases to $-2$ (see figure below; the $+2$ situation is symmetrical). This means the left subtree is higher by 2 than the right subtree. This happens if we inserted to the left subtree or deleted from the right subtree. An intuitive solution is to rotate $x$$z$ right:

But we need to be a little more careful. If balance of $x$ is $-1$ or $0$, so $\alpha$ is higher or the same height as $\beta$ as in the figure above, this will work: after the rotation, all the balances will be equal or $+$/$-1$.

However, if $\beta$ was higher than $\alpha$ (if balance of $x$ was $+1$), that would mean that $\beta$ is higher than $\gamma$ by 2 and after the rotation, $z$ would have become imbalanced. This case happens if we inserted to right subtree of $x$ or deleted from right subtree of $z$.

The solution (see figure below) is to first rotate $y$$x$ left. This will move $\alpha$ down and balance of $y$ will become $-1$ or $0$ – effectively reducing the situation to the first case above (so we rotate $y$ again).

Summary: If balance of node $z$ is $-2$, then let $x=left(z)$

• case I: if balance of $x$ is $-1$ or $0$, we rotate($x$)
• case II: if balance of $x$ is $+1$, let $y=right(x)$, we rotate($y$) twice

symmetrically, if balance of $z$ is $+2$, then let $x=right(z)$

• case I: if balance of $x$ is $+1$ or $0$, we rotate($x$)
• case II: if balance of $x$ is $-1$, let $y=left(x)$, we rotate($y$) twice

## Analysis

What is the maximum height of an AVL tree with $n$ nodes?

Well, with questions like these, it is actually easier when we turn them around and ask: What is the minimum number of nodes that we need for an AVL tree of height $h$?

Let $T_h$ be an AVL tree of height $h$ with minimum number of nodes (it will not be unique, but its size is). Here are a few examples:

So the minimum number of nodes is 1, 2, 4, 7, 12, … (does it look familiar?)

In general, if we want to create $T_h$, since we want to minimize the number of nodes, it better be imbalanced. Without loss of generality, let the root have balance $-1$. That means, that the left subtree has height $h-1$ and the right subtree has height $h-2$. But trees with minimum number of nodes of height $h-1$ and $h-2$ are $T_{h-1}$ and $T_{h-2}$. So we can create $T_h$ recursively:

and $|T_h| = |T_{h-1}| + |T_{h-2}| + 1$. These trees are called Fibonacci trees and their size is one less than a Fibonacci number.

But Fibonacci number $F_h$ is asymptotically $\Theta(\varphi^h)$ where $\varphi\approx 1.618$ is the golden ratio and if $n$, the number of nodes is exponential in height ($n = \Omega(\varphi^h)$), that implies that $h$ must be logarithmic in $n$ ($h = O(\log n)$). A more careful analysis proves that $h \leq 1.44\log_2(n+2)$.

• G.A. Velskii and E. Landis. An algorithm for the organisation of information. In Doklady Akademii Nauk SSSR, volume 146, pages 263-266, 1962.