Data Structures and Algorithms in Java, 2nd Edition

9. Red-Black Trees

In This Chapter

• Our Approach to the Discussion

• Balanced and Unbalanced Trees

• Experimenting with the Workshop Applet

• Rotations

• Inserting a New Node

• Deletion

• The Efficiency of Red-Black Trees

• Red-Black Tree Implementation

• Other Balanced Trees

As you learned in Chapter 8, “Binary Trees,” ordinary binary search trees offer important advantages as data storage devices: You can quickly search for an item with a given key, and you can also quickly insert or delete an item. Other data storage structures, such as arrays, sorted arrays, and linked lists, perform one or the other of these activities slowly. Thus, binary search trees might appear to be the ideal data storage structure.

Unfortunately, ordinary binary ...