Why the node split when inserting into 2-3-4 tree?

Question

In the depicted 2-3-4 tree below (from Data Structures & Algorithm in Java, 2nd ed), why does inserting 99 cause the node split of 83/92/104 when it seems like 99 could've been inserted into the right child (the C child, into the spot immediately after 97) without any splitting done?

enter image description here

score 2 · Accepted Answer · answered Aug 03 '12 at 15:32

2

Inserting 99 into C would be OK in that it would maintain all the invariants, but the algorithm is simpler in general if insert always expands 4-nodes on the way down. Then there will always be room for any needed lifting and rotations. It may help to compare the case where C is already a 4-node itself.

answered Aug 03 '12 at 15:32

xan

7,511
2
32
45

Ah, I see. That makes sense. If `C` were full (e.g., `96/97/98`) and we didn't do the node-splits on the way down, we'd have to split `C` in order to insert `99`. However, splitting `C` in that case would cause the tree to become unbalanced, which violates the implicit rules of the 2-3-4 tree. – tony19 Aug 03 '12 at 22:19

score 0 · Answer 2 · answered Aug 02 '12 at 23:28

0

To keep the tree balanced, to guarantee performance. The insertion is recursive and it hits a 4-node (node with 3 values and 4 children) , which will cause a split to be done.

answered Aug 02 '12 at 23:28

Markus Mikkolainen

3,397
18
21

Sorry, I'm still confused. How is the tree *unbalanced* if `99` were simply inserted into `C` without splitting its parent? – tony19 Aug 02 '12 at 23:30
most of the nodes would fall in the branch starting with the parent. – Markus Mikkolainen Aug 02 '12 at 23:34

Why the node split when inserting into 2-3-4 tree?

2 Answers2