Data Structures and the Java Collections Framework, Third Edition

CHAPTER 12

Tree Maps and Tree Sets

We begin this chapter by introducing another kind of balanced binary tree: the red-black tree. Red-black trees provide the underpinning for two extremely valuable classes: the TreeMap class and the TreeSet class, both of which are in the Java Collections Framework. Each element in a TreeMap object has two parts: a key part—by which the element is compared to other elements—and a value part consisting of the rest of the element. No two elements in a TreeMap object can have the same key. A TreeSet object is a TreeMap object in which all the elements have the same value part. There are applications of both the TreeMap class (a simple thesaurus) and the TreeSet class (a spell-checker). TreeMap objects and TreeSet objects are close to ideal: For inserting, removing and searching, worstTime(n) is logarithmic in n.

CHAPTER OBJECTIVES

1. Be able to define what a red-black tree is, and be able to distinguish between a red-black tree and an AVL tree.
2. Understand the Map interface and the overall idea of how the TreeMap implementation of the Map interface is based on red-black trees.
3. Compare TreeMap and TreeSet objects.

12.1 Red-Black Trees

Basically, a red-black tree is a binary search tree in which we adopt a coloring convention for each element in the tree. Specifically, with each element we associate a color of either red or black, according to rules we will give shortly. One of the rules involves paths. Recall, from Chapter 9, that if element A is an ...