The AVL Tree

An AVL tree is a binary search tree that repairs its shape after every insertion and removal, so its height stays about $\log n$ whatever order the values are inserted in. In this chapter, you will work with AVL trees by hand. In the next chapter, you will implement one.

After reading this chapter, you should be able to:

• Decide whether a binary search tree is an AVL tree by computing the balance factor of every node
• Rebalance a node by hand with the four rotations: single right, single left, double right-left, and double left-right
• Choose the rotation from the balance factors of the unbalanced node and its heavy child
• Trace a sequence of insertions and removals on an AVL tree, rotating at each node that becomes unbalanced
• Explain why an insertion needs at most one repair while a removal can need repairs at several ancestors
• Explain why the AVL property keeps the tree’s height $O(\log n)$, using the minimal AVL tree of each height

Sections

1. Keeping the Tree Balanced
2. The Balance Factor
3. The AVL Property
4. Structural Rotation
5. Single Rotations
6. Double Rotations
7. Choosing the Rotation
8. Tracing a Full Sequence
9. One Repair per Insertion
10. Removal Can Rebalance Several Ancestors
11. Why Balance Keeps the Tree Short