Source code online books for professionals by professionals

Figure 6-12.  An overfull pseudonode, and the result of the repairing left rotation (swapping the edges (e,d) and (c,e)),  
as well as making e the new child of a
Figure 6-11.  Two simulated 3-nodes (highlighted) in an AA-tree. Note that the one on the left is reversed and must be 
repaired
This figure shows you several things at once. First, you get an idea of how a 3-node is simulated: You simply link 
up two nodes to act as a single pseudonode (as highlighted). Second, the figure illustrates the idea of level. Each node 
is assigned a level (a number), with the level of all leaves being 1. When we pretend that two nodes form a 3-node, we 
simply give them the same level, as shown by the vertical placement in the figure. Third, the edge “inside” a 3-node 
(called a horizontal edge) can point only to the right. That means that the leftmost subfigure illustrates an illegal node, 
which must be repaired, using a right rotation: Make c the left child of d and d the right child of b, and finally, make d’s 
old parent the parent of b instead. Presto! You’ve got the rightmost subfigure (which is valid). In other words, the edge 
to the middle child and the horizontal edge switch places. This operation is called skew.
There is one other form of illegal situation that can occur and that must be fixed with rotations: an overfull 
pseudonode (that is, a 4-node). This is shown in Figure 
6-12
. Here we have three nodes chained on the same level (c, 
e, and f). We want to simulate a split, where the middle key (e) would be moved up to the parent (a), as in a 2-3-tree. 
In this case, that’s as simple as rotating c and e, using a left rotation. This is basically just the opposite of what we did 
in Figure 
6-11
. In other words, we move the child pointer of c down from e to d, and we move the child pointer of e up 
from d to c. Finally, we move the child pointer of a from c to e. To later remember that a and e now form a new 3-node, 
we increment the level of e (see Figure 
6-12
). This operation is called (naturally enough) split.
16
The AA-tree is, in a way, a version of the BB-tree, or the binary B-tree, which was introduced by Rudolph Bayer in 1971 as a 
binary representation of the 2-3-tree.

---

Chapter 6 
■
 DiviDe, Combine, anD Conquer
134
You insert a node into an AA-tree just like you would in a standard, unbalanced binary tree; the only difference 
is that you perform some cleanup afterward (using skew and split). The full code can be found in Listing 6-6. As you 
can see, the cleanup (one call to skew and one to split) is performed as part of the backtracking in the recursion—so 
nodes are repaired on the path back up to the root. How does that work, really?
The operations further down along the path can really do only one thing that will affect us: They can put another 
node into “our” current simulated node. At the leaf level, this happens whenever we add a node, because they all have 
level 1. If the current node is further up in the tree, we can get another node in our current (simulated) node if one 
has been moved up during a split. Either way, this node that is now suddenly on our level can be either a left child or 
a right child. If it’s a left child, we skew (do a right rotation), and we’ve gotten rid of the problem. If it’s a right child, 
it’s not a problem to begin with. However, if it’s a right grandchild, we have an overfull node, so we do a split (a left 
rotation) and promote the middle node of our simulated 4-node up to the parent’s level.
This is all pretty tricky to describe in words—I hope the code is clear enough that you’ll understand what’s going 
on. (It might take some time and head-scratching, though.)