Data Structures and Algorithms in C++, Second Edition

Chapter 10. Search Trees

Contents

10.1 Binary Search Trees	424
10.1.1 Searching	426
10.1.2 Update Operations	428
10.1.3 C++ Implementation of a Binary Search Tree	432
10.2 AVL Trees	438
10.2.1 Update Operations	440
10.2.2 C++ Implementation of an AVL Tree	446
10.3 Splay Trees	450
10.3.1 Splaying	450
10.3.2 When to Splay	454
10.3.3 Amortized Analysis of Splaying*	456
10.4 (2,4) Trees	461
10.4.1 Multi-Way Search Trees	461
10.4.2 Update Operations for (2,4) Trees	467
10.5 Red-Black Trees	473
10.5.1 Update Operations	475
10.5.2 C++ Implementation of a Red-Black Tree	488
10.6 Exercises	492

Binary Search Trees

All of the structures that we discuss in this chapter are search trees, that is, tree data structures that can be used to implement ordered maps and ordered dictionaries. Recall from Chapter 9 that a map is a collection of key-value entries, with each value associated with a distinct key. A dictionary differs in that multiple values may share the same key value. Our presentation focuses mostly on maps, but we consider both data structures in this chapter.

We assume that maps and dictionaries provide a special pointer object, called an iterator, which permits us to reference and enumerate the entries of the structure. In order to indicate that an object is not present, there exists a special sentinel iterator called end. By convention, this sentinel refers to an imaginary element that lies just beyond the last element of ...