O'Reilly logo

Data Structures and Algorithms in C++, Second Edition by David M. Mount, Roberto Tamassia, Michael T. Goodrich

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 10. Search Trees

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

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