Essential Algorithms: A Practical Approach to Computer Algorithms

CHAPTER 11

Balanced Trees

The previous chapter explained trees in general and some of the algorithms that use trees. Some algorithms, such as tree traversals, have run times that depend on the tree's total size. Other algorithms, such as one for inserting a node in a sorted tree, have run times that depend on the tree's height. If a sorted tree containing N nodes is relatively short and wide, inserting a new node takes O(log N) steps. However, if the nodes are added to the tree in sorted order, the tree grows tall and thin, so adding a new node takes O(N) time, which is much longer.

This chapter describes balanced trees. A balanced tree is one that rearranges its nodes as necessary to guarantee that it doesn't become too tall and thin. These trees may not be perfectly balanced or have the minimum height possible for a given number of nodes, but they are balanced enough that algorithms that travel through them from top to bottom run in O(log N) time.

NOTE This chapter doesn't use the pseudocode used by much of the rest of the book. Balanced tree algorithms are much easier to explain and understand if you use pictures instead of code.

The following sections describe three kinds of balanced trees: AVL trees, 2-3 trees, and B-trees.

AVL Trees

An AVL tree is a sorted binary tree in which the heights of two subtrees at any given node differ by at most 1. When a node is added or removed, the tree is rebalanced if necessary to ensure that the subtrees again have heights differing by ...