Chapter 11

Search Trees



11.1 Binary Search Trees

In Chapter 8 we introduced the tree data structure and demonstrated a variety of applications. One important use is as a search tree (as described on page 338). In this chapter, we use a search-tree structure to efficiently implement a sorted map. The three most fundamental methods of of a map (see Section 10.1.1) are:

get(k): Returns the value v associated with key k, if such an entry exists; otherwise returns null.
put(k, v): Associates value v with key k, replacing and returning any existing value if the map already contains an entry with key equal to k.
remove(k): Removes the entry with key equal to k, if one exists, ...

Get Data Structures and Algorithms in Java, 6th Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.