Geek asks and answers

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

In the 2-3-4 tree below (from Data Structures and Algorithm in Java, 2nd ed. ), Why insertion 99causes the node to split 83/92/104when it seems that it 99can be inserted into the right child element ( Cchild, in the place immediately after 97) without any separation?

enter image description here

+5
source share
2 answers

Inserting 99 into C will be OK in that it preserves all the invariants, but the algorithm is generally simpler if the insert always extends 4-nodes along the way down. Then there is always a place for any necessary lifts and turns. This can help compare the case where C is already 4 node itself.

+2

, . , 4- node (node 3 4 ), .

0

More articles:


All Articles