AVL trees

An AVL (Adel'son-Velskii - Lan'dis) tree is a full binary tree (with failure nodes) satisfying at every internal node the balance criterion | h(L) - h(R) | <= 1. (One could describe a k-AVL tree in which the maximum difference could be k or less, or extend the concept to k-ary trees.) One can look at the definition of an AVL tree as a context-sensitive inductive definition.

The key results on AVL trees are (1) that the maximum depth of an AVL tree is O (lg n), and (2) that the AVL invariant can be restored on insertion or deletion with O (lg n) work. We outline these results below.

The minimum number of internal nodes in an AVL tree of height h is given by the following inductive definition:

min_AVL (0) = 0

min_AVL (1) = 1

min_AVL (h) = 1 + min_AVL (h - 1) + min_AVL (h-2) // since heights can differ by at most one.

It can be shown that the solution to this recursion is min_AVL (h) = Fib (h+1) - 1. Since Fib (n) is approximately N n (where N ~ 1.61 is the "golden ratio"), solving for h shows h is at least O (lg n).

The key to the logarithmic update cost is rotation in trees. Basically, a right rotation at a node v moves the left child of v up to the location of v, v down to the right child, and hangs everything else so that the tree still possesses the binary search property (that is, inorder traversal is the same as key order); a left rotation does the reverse.

The insert algorithm has the following high-level pseudocode:

insert (tree T, key k) returns boolean

use binary search on T to find the insertion spot v for k;

if k is found, return an error (and exit);

else make a new node containing k with failure node children;

repeat

follow parent pointers from v up the tree visiting nodes w

until one of the following occurs:

(1) reach the root: tree is balanced;

(2) the two children of w have the same height:

tree is balanced;

(3) the tree is out of balance at w:

look at the last two pointers (or find k from w);

if they both went in the same direction (e.g., right-right)

perform a rotation at w in the opposite direction;

otherwise /* they went left-right or right-left */

/* --- first case is illustrated */

perform a left rotation at the left child of w

followed by a right rotation at w

/* brings the grandchild to the root */

/* rotation will always restore the balance invariant */

/* proof given in class */

end

The delete algorithm is a little more subtle for two reasons:

if the key to be deleted is not at a node both of whose children are failure nodes, then it can't just be deleted, but has to be exchanged with an immediate predecessor or immediate successor first (as in any binary search tree), and
rotation does not necessarily restore the balance condition --- O (lg n) rotations may be required. Further, it isn't enough to have the two children have the same height; we need the height of the parent not to have changed. We do not give further details here.

We will cover B-trees and related structures, and homework on AVL and B-trees, in the next set of notes.