Trace INSERT

Consider the insertion of 8 into this tree:


              (37 # _ )
            /           \
           /             \
          /               \
      (21 # 29)            (50 # _ )
     /    |     \          /       \
    /     |      \        /         \
(7,9,11) (21,23) (29,30) (37,49)   (50,100)

Clearly it belongs in the left most leaf. But that would overfill that leaf (4 keys instead of the maximum 3). So, we must split that node and pass a key up.


              (37 # _ )
            /             \
           /               ----
          /                    \
       (9 # 21 # 29)           (50 # _ )
     /  |      |     \          /       \
    /   |      |      \        /         \
(7,8) (9,11) (21,23) (29,30) (37,49)   (50,100)

But now the interior node is overfull, so it must be split as well.


              ( 21 # 37 )
            /    |        \
           /     |         ------
          /      |               \
       (9 # _) (29 # _)           (50 # _ )
     /  |       |     \           /       \
    /   |       |      \         /         \
(7,8) (9,11) (21,23) (29,30) (37,49)   (50,100)

Now, the root is full, but not overfull, so it does not need to split--the height of the tree remains the same.

NEXT BACK