Data Structures and Algorithms in Java, 6th Edition

Chapter 11

Search Trees

Contents

11.1 Binary Search Trees

11.1.1 Searching Within a Binary Search Tree

11.1.2 Insertions and Deletions

11.1.3 Java Implementation

11.1.4 Performance of a Binary Search Tree

11.2 Balanced Search Trees

11.2.1 Java Framework for Balancing Search Trees

11.3 AVL Trees

11.3.1 Update Operations

11.3.2 Java Implementation

11.4 Splay Trees

11.4.1 Splaying

11.4.2 When to Splay

11.4.3 Java Implementation

11.4.4 Amortized Analysis of Splaying

11.5 (2,4) Trees

11.5.1 Multiway Search Trees

11.5.2 (2,4)-Tree Operations

11.6 Red-Black Trees

11.6.1 Red-Black Tree Operations

11.6.2 Java Implementation

11.7 Exercises

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