Question

Insert into an initially empty 2-3-4 tree, in the order given, the following values:

12, 13, 17, 10, 4, 6, 9, 15, 30, 25, 20, 40.
Show the intermediate trees after each insertion that causes a split. For consistency, we will
split the nodes in the bottom-up manner. Note that a node is full when it has 3 keys and a
full node should be split if a new key is inserted into it.

Answer 1

This answer explains how to insert values into an initially empty 2-3-4 tree, showing the intermediate trees after each insertion that causes a split.

Step-by-step explanation:

A 2-3-4 tree is a type of self-balancing search tree where each node can hold up to three keys. When a node becomes full, it is split into two new nodes. To insert values into an initially empty 2-3-4 tree, we follow these steps:

1. Insert 12 into the empty tree, resulting in the following:
2. 12
3. Insert 13, which causes a split: 12, 13
4. Insert 17, which also causes a split: 13
   12 17
5. Insert 10, which causes a split: 13, 17
   10 12
6. Insert 4, which causes a split: 13, 17,
   4 10 12
7. Insert 6, which causes another split: 13, 17,
   4 6 10 12
8. Insert 9: 13, 17,
   4 6 9 10 12
9. Insert 15, and another split occurs: 13, 17,
   4 6 9 10 12 15
10. Insert 30: 13, 17 30
    4 6 9 10 12 15 25
11. Insert 25: 13, 17 25 30
    4 6 9 10 12 15 20 25
12. Insert 20, which causes a split: 13, 17 25
    4 6 9 10 12 15 20 25
13. Insert 40, causing a final split: 13, 17 30
    4 6 9 10 12 15 20 25 40