Programming Praxis

In past exercises we have seen several flavors of search trees: simple (unbalanced) binary trees, red/black trees, treaps, and ternary search trees. In today’s exercise we look at the oldest, and in some ways simplest, of the balanced binary search trees, known as AVL trees, invented in 1962 by the Russian mathematicians Georgii Maksimovich Adelson-Velskii and Evgenii Mikhailovich Landis.

AVL trees are a type of binary search tree, and maintain the property that all elements in the left child of each node have keys that are less than the key of the current node, and all elements in the right child of each node have keys that are greater than the key of the current node. AVL trees maintain balance using a height field in each node, along with the key, value, and pointers to the two children; the height of a node is length of the longest path from the node to the bottom of the tree. An AVL tree is balanced if, for every node in the tree, the heights of its children differ by no more than 1. Thus, the maximum height of the tree is O(log₂ n), where n is the number of nodes in the tree, so all operations — lookup, insert and delete — can be performed in guaranteed (not expected, not amortized) logarithmic time in both the average case and the worst case.

The lookup operation is simple, and works exactly the same way as a simple (unbalanced) binary search tree. If the key at the root of the tree is the desired key, return the associated value. Otherwise, lookup the desired key recursively in either the left subtree or the right subtree, depending on whether the desired key is less than or greater than the current tree. If you reach a nil tree, the key is not in the tree and the search fails.

The insertion operation works by searching to the point where the new node is to be inserted, then rewriting the tree locally to insert the new point. This maintains the binary search tree property that all left children are less than the current node and all right children are greater than the current but may violate the AVL tree property that the height of the two children of a node differ by no more than 1. In that case, either one or two local rotations are performed to maintain the binary search tree property and regain the AVL tree property; the box at right, which is stolen from Wikipedia, gives the two symmetric cases. There are two special cases, where insertion occurs at the leaf of a tree, and where the key already exists in the tree; be sure to handle them properly.

As is usual with tree operations, deletion is the trickiest operation. The basic idea is to search to the node to be deleted, replace it with either its maximal predecessor or minimal successor, then delete the maximal predecessor or minimal successor and rebalance the tree at each node back up to the point of the replacement. In the normal case, only a few rebalancing operations are required, as there is sufficient slack in the tree to absorb any imbalance. Note that although this description sounds simple, getting the details right can be anything but. There is a single special case: when the key doesn’t exist in the tree, the original tree should be returned.

The final operation we consider enrolls the elements of an AVL tree in a list, in order. The procedure begins at the root of the tree and recursively appends the list formed by the left child, the current item, and the list formed by the right child; the base of the recursion is the nil tree, which is represented as a null list.

Your task is to write a library of functions for manipulating AVL trees; be sure to provide a comprehensive test suite. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2