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?
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With