O'Reilly logo

Data Structures and the Java Collections Framework, Third Edition by William J. Collins

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required