Essential Algorithms, 2nd Edition

CHAPTER 11Balanced 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 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 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 time.

NOTE

This chapter doesn't use the pseudocode that's included in 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 ...