Super Edges
2–3–4 trees are really cool, and I think I can draw them on a whiteboard. But the idea of actually coding them up gives me the heebie-jeebies!
The implementation is tricky, for sure. All of the “squeezing in” of new values and promoting values up is logistically complicated.
Let's try to make this idea more practical to implement…
Converting a 2–3–4 Tree to a Binary Tree
The main snag in implementing 2–3–4 trees is that nodes have to fluidly change amongst multiple different types with different numbers of keys and children.
To get around that, we are going to try to “binarize” a 2–3–4 tree, to find a binary tree that is equivalent in structure. We already know how to represent a binary tree, so that would make things easier, right?
A 2-node is already basically the same as a binary tree node, so those are easy.
The main idea is replace 3-nodes and 4-nodes with miniature BSTs that we operate on as a unit.
Converting 4-Nodes to “Mini Trees”
Anywhere we have a four-node in a 2–3–4 tree, we could draw an equivalent binary tree where the 4-node is broken up into three BST nodes.
This should be satisfying: It's the same “breaking up of 4-nodes” that we did when we promoted the middle value up to break up 4-nodes during insertion!
In other words, anywhere we see a node in our tree like this one,
we could replace it with three nodes like
Notice that we've marked the edges between the three nodes that were part of our original 4-node by making them bright red and thicker. That's our way of remembering that those nodes were acting like a single unit. If we wanted to, we could convert the BST with these “super edges” back into the original 2–3–4 tree!
Here's our original 4-node in the context of a bigger tree:
And here's what that tree would look like with our converted mini tree with “super edges” between its edges:
Converting 3-Nodes to “Mini Trees”
We can do the same thing with our 3-nodes, though we have a little bit of choice in how to break them up.
Anywhere we have a three-node in a 2–3–4 tree, we could draw one of two equivalent binary trees where the 3-node was broken up into two BST nodes.
In other words, anywhere we see a node like this in our tree:
We could replace it with either of these “mini trees” with “super edges”:
And as long as we mark which edges were originally part of a 3-node together, we will, again, be able to recover the original 3-node!
Going back to the tree we had above, we could convert the two 3-nodes into mini-trees like this:
Is It Balanced?
Meh. Now the tree isn't balanced!
-
Welllll, it's not perfectly balanced, that's true.
-
But it's still pretty balanced, right?
Since a 2–3–4 tree is perfectly balanced, every branch has the same height: \( h(n) \in \Theta( \log n ) \).
We convert each 3- and 4-node to a tiny BST of height 1, which will make some branches longer than others, ruining the “perfection”.
But how imbalanced could it get?
In the worst case, imagine a single branch of a 2–3–4 tree that is made entirely of 3-nodes and all other nodes are 2-nodes. When we perform our conversion, the branch with all the 3-nodes doubles in height, making it the longest branch. But then its height is still \( 2h(n) \in \Theta( \log n ) \).
Even though the binary representation isn't perfectly balanced, its height is still \( \Theta( \log n ) \), so we still call it balanced.
A Problem: Encoding Super Edges
-
You're right! There's only one kind of
Node*in the C++ language. -
Phew!
-
Pointers are just a primitive type that stores memory addresses; they don't have data members.
-
That means we don't have a good way to have “normal edges” and “super strong red edges”.
-
A
Node*is aNode*is aNode*. 
Could we create our own
Edgeclass that has a pointer and aboolsaying whether the edge is a super edge?-
We could, but it turns out there's an easier way…
(When logged in, completion status appears here.)