9.1 2-4 Trees

A 2-4 tree is a rooted tree with the following properties:

Property 9..1 (height)   All leaves have the same depth.

Property 9..2 (degree)   Every internal node has 2, 3, or 4 children.

An example of a 2-4 tree is shown in Figure 9.1.

Figure 9.1: A 2-4 tree of height 3.

The properties of 2-4 trees imply that their height is logarithmic in the number of leaves:

Lemma 9..1   A 2-4 tree with $\ensuremath{\ensuremath{\mathit{n}}}$ leaves has height at most $\log \ensuremath{\ensuremath{\ensuremath{\mathit{n}}}}$.

Proof. The lower-bound of 2 on the number of children of an internal node implies that, if the height of a 2-4 tree is $h$, then it has at least $2^h$ leaves. In other words,

$$\ensuremath{\ensuremath{\ensuremath{\mathit{n}}}} \ge 2^h \enspace .$$

Taking logarithms on both sides of this inequality gives $h \le \log \ensuremath{\ensuremath{\ensuremath{\mathit{n}}}}$. $\qedsymbol$

9.1.1 Adding a Leaf

Adding a leaf to a 2-4 tree is easy (see Figure 9.2). If we want to add a leaf $\ensuremath{\ensuremath{\mathit{u}}}$ as the child of some node $\ensuremath{\ensuremath{\mathit{w}}}$ on the second-last level, then we simply make $\ensuremath{\ensuremath{\mathit{u}}}$ a child of $\ensuremath{\ensuremath{\mathit{w}}}$. This certainly maintains the height property, but could violate the degree property; if $\ensuremath{\ensuremath{\mathit{w}}}$ had four children prior to adding $\ensuremath{\ensuremath{\mathit{u}}}$, then $\ensuremath{\ensuremath{\mathit{w}}}$ now has five children. In this case, we split $\ensuremath{\ensuremath{\mathit{w}}}$ into two nodes, $\ensuremath{\ensuremath{\mathit{w}}}$ and $\ensuremath{\ensuremath{\mathit{w}}}$', having two and three children, respectively. But now $\ensuremath{\ensuremath{\mathit{w}}}$' has no parent, so we recursively make $\ensuremath{\ensuremath{\mathit{w}}}$' a child of $\ensuremath{\ensuremath{\mathit{w}}}$'s parent. Again, this may cause $\ensuremath{\ensuremath{\mathit{w}}}$'s parent to have too many children in which case we split it. This process goes on until we reach a node that has fewer than four children, or until we split the root, $\ensuremath{\ensuremath{\mathit{r}}}$, into two nodes $\ensuremath{\ensuremath{\mathit{r}}}$ and $\ensuremath{r}'$. In the latter case, we make a new root that has $\ensuremath{\ensuremath{\mathit{r}}}$ and $\ensuremath{r}'$ as children. This simultaneously increases the depth of all leaves and so maintains the height property.

Figure 9.2: Adding a leaf to a 2-4 Tree. This process stops after one split because $\ensuremath{\ensuremath{\mathit{w}}.\ensuremath{\mathit{parent}}}$ has a degree of less than 4 before the addition.

Since the height of the 2-4 tree is never more than $\log \ensuremath{\ensuremath{\ensuremath{\mathit{n}}}}$, the process of adding a leaf finishes after at most $\log \ensuremath{\ensuremath{\ensuremath{\mathit{n}}}}$ steps.

9.1.2 Removing a Leaf

Removing a leaf from a 2-4 tree is a little more tricky (see Figure 9.3). To remove a leaf $\ensuremath{\ensuremath{\mathit{u}}}$ from its parent $\ensuremath{\ensuremath{\mathit{w}}}$, we just remove it. If $\ensuremath{\ensuremath{\mathit{w}}}$ had only two children prior to the removal of $\ensuremath{\ensuremath{\mathit{u}}}$, then $\ensuremath{\ensuremath{\mathit{w}}}$ is left with only one child and violates the degree property.

Figure 9.3: Removing a leaf from a 2-4 Tree. This process goes all the way to the root because each of $\ensuremath{\ensuremath{\mathit{u}}}$'s ancestors and their siblings have only two children.

To correct this, we look at $\ensuremath{\ensuremath{\mathit{w}}}$'s sibling, $\ensuremath{w}'$. The node $\ensuremath{w}'$ is sure to exist since $\ensuremath{\ensuremath{\mathit{w}}}$'s parent had at least two children. If $\ensuremath{w}'$ has three or four children, then we take one of these children from $\ensuremath{w}'$ and give it to $\ensuremath{\ensuremath{\mathit{w}}}$. Now $\ensuremath{\ensuremath{\mathit{w}}}$ has two children and $\ensuremath{w}'$ has two or three children and we are done.

On the other hand, if $\ensuremath{w}'$ has only two children, then we merge $\ensuremath{\ensuremath{\mathit{w}}}$ and $\ensuremath{w}'$ into a single node, $\ensuremath{\ensuremath{\mathit{w}}}$, that has three children. Next we recursively remove $\ensuremath{w}'$ from the parent of $\ensuremath{w}'$. This process ends when we reach a node, $\ensuremath{\ensuremath{\mathit{u}}}$, where $\ensuremath{\ensuremath{\mathit{u}}}$ or its sibling has more than two children, or when we reach the root. In the latter case, if the root is left with only one child, then we delete the root and make its child the new root. Again, this simultaneously decreases the height of every leaf and therefore maintains the height property.

Again, since the height of the tree is never more than $\log \ensuremath{\ensuremath{\ensuremath{\mathit{n}}}}$, the process of removing a leaf finishes after at most $\log \ensuremath{\ensuremath{\ensuremath{\mathit{n}}}}$ steps.