ABSTRACT
Used By: Tree sort (Sections 11.4.4 and 15.5.4), TaggedRedBlackTree (Section 49.9.5), historical event collection case study (Sections 29.1 and 50.1)
Strengths: The red-black tree is a form of a balanced binary search tree that guarantees that the height of the tree is at most 2 log2(n + 1). Through partial analysis and simulations, it has been shown that a search in a red-black tree constructed from n elements, inserted in a random order, uses about 1.002 log2 n comparisons on average [136]. The red-black tree is the best generalpurpose ordered collection data structure since it has guaranteed worst-case logarithmic bounds for all methods and has very fast search time. If it is important to have constant time methods to perform iteration, it could be threaded, as illustrated with the pairing heap (Chapter 27) at the expense of increased space usage and a small amount of overhead in the time complexity.
