Advanced Trees

This chapter discusses four advanced data structures based on trees. Heaps (Section 14.1) provide an efficient implementation of a new kind of queue, as well as an interesting sorting algorithm. Section 14.2 uses trees to model a cluster of disjoint sets. Digital search trees (Section 14.3) provide a new way to store sets of Strings. Red-black trees (Section 14.4), a variation on binary search trees, are guaranteed to remain balanced, avoiding the linear worst-case time of binary search tree operations.