Relaxing a Constraint: Multiple Types of Nodes
A perfect tree is one where every leaf is exactly the same distance from the root.
Most trees can't be perfect. Why is that?
Well, nobody's perfect!
-
Well, that's true. But also…
Because only certain sized trees can be perfect! If you don't have the right number of nodes to exactly fill a level, then your tree won't be perfect no matter how balanced it is!
-
Exactly! But that doesn't stop our first tree today—the 2–3–4 tree.
-
2–3–4 Trees relentlessly demand perfection.
-
In a 2–3–4 tree, every leaf will always be exactly the same distance from the root!
That… seems too good to be true.
-
Well, yes and no. Something has to give. In the case of 2–3–4 trees, it's the binary part of binary-search tree.
Whoah, what? How is that even a thing?
2-, 3-, and 4-Nodes
In a 2–3–4 Tree, we can have three different node types:
2-Node
A 2-node is what other BSTs just call a “node”. It stores one value, which we'll call key. It has two children:
- The left subtree holds values that are less than key.
- The right subtree holds values that are greater than key.
3-Node
A 3-node expands on a 2-node by allowing a second value to be stored in it. We'll call the values key1 and key2. A 3-Node has three children:
- The left subtree holds values that are less than key1.
- The middle subtree holds values that are between key1 and key2.
- The right subtree holds values that are greater than key2.
4-Node
As you might have guessed, a 4-node expands on a 3-node by allowing a third value to be stored in it As long as we're being creative, let's call them key1, key2, and key3. A 4-Node has four children:
- The left subtree holds values that are less than key1.
- The next subtree holds values that are between key1 and key2.
- The third subtree holds values that are between key2 and key3.
- The right subtree holds values that are greater than key3.
(When logged in, completion status appears here.)