Insertion in 2–3–4 Trees
Very well, bovine creature. But how does this proliferation of node varieties aid the arboreal structure in maintaining balance?
Let's walk through an example and see!
Example: Inserting into an Empty 2–3–4 Tree
Let's walk through inserting the first few values into an empty 2–3–4 Tree.
Important Notes
- During insertion, we promote the middle value of all 4-nodes as we encounter them on our way down the tree.
- When we promote the middle value in a 4-node, it joins the layer above (if there is one).
In this simple example, we were promoting the value from the root node, so it simply became a 2-node as the new root.
In general, there will be some node above the 4-node that is guaranteed not to be a 4-node, because we promote as we go down. The promoted value joins that parent node.
Your Turn
Remember that after the first four inserts, our tree looks like this:
Now, on a piece of scratch paper or in a notebook, draw what happens when you insert the following values into our existing 2–3–4 Tree:
- 25
- 50
- 70
- 41
- 40
- 44
- 43
(When logged in, completion status appears here.)