Data Structures and Algorithms in Python

Chapter 11

Search Trees

Contents

11.1 Binary Search Trees

11.1.1 Navigating a Binary Search Tree

11.1.2 Searches

11.1.3 Insertions and Deletions

11.1.4 Python Implementation

11.1.5 Performance of a Binary Search Tree

11.2 Balanced Search Trees

11.2.1 Python Framework for Balancing Search Trees

11.3 AVL Trees

11.3.1 Update Operations

11.3.2 Python Implementation

11.4 Splay Trees

11.4.1 Splaying

11.4.2 When to Splay

11.4.3 Python 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 Python 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 332). In this chapter, we use a search tree structure to efficiently implement a sorted map. The three most fundamental methods of a map M (see Section 10.1.1) are:

M[k]:	Return the value v associated with key k in map M, if one exists; otherwise raise a KeyError; implemented with _ _getitem_ _ method.
M[k] = v:	Associate value v with key k in map M, replacing the existing value if the map already contains an item with key equal to k; implemented with ...