Source code online books for professionals by professionals

Figure 6-10.  The node types in a 2-3-tree
Note
 
■
  the 2-3-tree is a special case of the b-tree, which forms the basis of almost all database systems, and  
disk-based trees used in such diverse areas as geographic information systems and image retrieval. the important  
extension is that b-trees can have thousands of keys (and subtrees), and each node is usually stored as a contiguous 
block on disk. the main motivation for the large blocks is to minimize the number of disk accesses.
Searching a 2-3-node is pretty straightforward—just a recursive traversal with pruning, like in a plain binary 
search tree. Insertion requires a bit of extra attention, though. As in a binary search tree, you first search for the proper 
leaf where the new value can be inserted. In a binary search tree, though, that will always be a None reference (that 
is, an empty child), where you can “append” the new node as a child of an existing one. In a 2-3-tree, though, you’ll 
always try to add the new value to an existing leaf. (The first value added to the tree will necessarily need to create a 
new node, though; that’s the same for any tree.) If there’s room in the node (that is, it’s a 2-node), you simply add the 
value. If not, you have three keys to consider (the two already there and your new one).
The solution is to split the node, moving the middle of the three values up to the parent. (If you’re splitting the 
root, you’ll have to make a new root.) If the parent is now overfull, you’ll need to split that, and so forth. The important 
result of this splitting behavior is that all leaves end up on the same level, meaning that the tree is fully balanced.
Now, while the idea of node splitting is relatively easy to understand, let’s stick to our even simpler binary trees 
for now. You see, it’s possible to use the idea of the 2-3-tree while not really implementing it as a 2-3-tree. We can 
simulate the whole thing using only binary nodes! There are two upsides to this: First, the structure is simpler and 
more consistent, and second, you get to learn about rotations (an important technique in general) without having to 
worry about a whole new balancing scheme!

---

Chapter 6 
■
 DiviDe, Combine, anD Conquer
133
The “simulation” I’m going to show you is called the AA-tree, after its creator, Arne Andersson.
16
 Among the many 
rotation-based balancing schemes, the AA-tree really stands out in its simplicity (though there’s still quite a bit to wrap 
your head around, if you’re new to this kind of thing). The AA-tree is a binary tree, so we need to have a look at how to 
simulate the 3-nodes we’ll be using to get balance. You can see how this works in Figure 
6-11
.