AVL tree

Invented by Adelson-Velskii, Landis (1962)
Idea:
  • 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)\)
Advantages:
  • guaranteed \(O(\log n)\) time (in the worst case) for each dictionary operation
Disadvantages:
  • harder to implement
Implementation: avl_set, avl_multiset, and avltree classes in Boost.Intrusive library
[You can download the application for offline viewing.]

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)\).

References

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