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