1

Introduction

2-3 trees are a form of balanced tree that can be used to implement a dictionary, as well as

other types of operations.

Recall that in its most basic form, a dictionary maintains a set of key/value pairs, and

supports the following operations:

insert: insert a given key/value pair into the data structure; if there is already a pair

with same key component, then simply update the value component;

search: given a key, determine if there is a key/value pair with a matching key com-

ponent, and if so, return the corresponding value component;

delete: given a key, delete the key/value pair, if any, with matching key component.

There are many data structures that may be used to implement a dictionary, such as

binary search trees, hash tables, etc. 2-3 trees are one such data structure. As we shall

see, if we implement a dictionary using 2-3 trees, then all three of the dictionary operations

take time O(log n), where n is the number of key/value pairs in the dictionary. We will also

see how to use 2-3 trees to implement other types of operations, beyond those of a simple

dictionary.

2

2-3 trees: the basics

Before we start, a word of warning: the exposition here of 2-3 trees is a little bit dierent

from what one usually sees in the literature. See Section 6 below for more on this.

Also, before we start, recall that the depth of a given node in a tree is the length of the

path (i.e., the number of edges in the path) from the root to that node. Also recall that

the height of a tree is the maximum depth of any node in the tree.

Now, at a high level, our notion of a 2-3 tree is that of a tree with the following properties:

key/value pairs stored only at leaves (with no duplicate keys);

all leaves are at the same depth;

looking at the leaves from left to right, keys appear in sorted order;

each internal node