INSERT ANSWER

Given the following tree:


              (29 # _ )
            /           \
           /             \
          /               \
      (21 # _)            (37 # 50 )
     /    \             /     |     \
    /      \           /      |      \
(7,9,11)   (21,23)  (29,30) (37,49)  (50,100)
Insertion of 22,40,70 would not cause the root to split.

The "22" key would simply fill the second leaf from the left.
The "40" key would simply fill up the second leaf from the right.
The "70" key would simply fill up the rightmost leaf.
In fact, no split would be needed, at all.

BACK