Dr. Ted Shaneyfelt - University of Hawaii at Hilo - Computer Science Department

# Programming Adelson-Velskii & Landis Tree Data Structures

AVL trees are balanced so that no subtree of any node is remains more than one node taller than the opposite subtree. The difference in height is the balance factor, kept in a tag in each node. During insertions or deltions, the balance factor may transiently be off-balance by +/- 2, but growth (positive or negative) is handled by rotating to mitigate this imbalance before returning from the function that operates on that node.

The remainder of this document assumes that you know what AVL trees are and explains how to write the software.

## Insertion into an AVL tree:

Insertion is done recursively. The ins function returns the amount of growth in height that results from inserting into the subtree.

## Deletion from an AVL tree:

Deletion is done recursively. The del function returns the amount of growth in height (possibly negative or zero) that results from deleting from the subtree.

## Managing growth (and shrinkage) for an AVL tree:

The balance factor tag indicates the difference in height between the right subtree and the left subtree below each node.

## Rebalancing an AVL tree:

Rebalancing rotates nodes to shift height left or right in case the balance factor indicates that one subtree of a node is two higer than the other.

If the tag is 2 or -2, then nodes are rotated according to the pattern of the tag and right or left child, and then the balance factors are adjusted depending on the node that rotated into the subroot position.

After writing your software, test it thoroughly. For each branch in the flowchart, determine what needs to be inserted and deleted for that code to be executed, then verify that it does get executed, and that the correct tree results, with the correct balance factors. Retest it both at root nodes where possible, and at interior nodes for all cases.

Using a graphing tool such as graphviz can be helpful for testing. When your code appears to be working for all cases, check also for memory leaks using a tool such as valgrind.

Helper functions to rotate nodes left and right may be helpful for rebalancing.