Search code examples
data-structuresbinary-treebranching-and-mergingb-tree

B tree insertion

hey i have a questions on my homework and i am being able to solve it i just want someone to see if i am doing right or wrong...

A b-tree with minimum branching factor of t=3

               [D][G][K][N][V]
             /  /  /    |  \   \
            /  /  /     |   \   \
           /  /  /      |    \   \
          AC EF  HI    LM  OPRST  WX

Now when i insert J in above tree this is the output i am getting.... 
                     [K]
                   /      \
                  /        \
                 /          \     
               [D][G]    [N][V]
             /  /  /     /  \   \
            /  /  /     /    \   \
           /  /  /     /      \   \
          AC EF  HIJ  LM    OPRST  WX


After Inserting Q in above tree this is the Final tree i am getting.
                      [K]
                   /      \
                  /        \
                 /          \     
               [D][G]    [N][Q][V]
             /  /  /     /  / \  \
            /  /  /     /  /   \  \
           /  /  /     /  /     \  \
          AC EF  HIJ  LM  OP   RST  WX

  Is this the Final Tree Correct?
Solution

  • No, the final B tree is not correct. The intermediate one is though. The last one should be like this

                      [K]
               /      \
              /        \
             /          \     
           [D][G]    [N][R][V]
         /  /  /     /  / \  \
        /  /  /     /  /   \  \
       /  /  /     /  /     \  \
      AC EF  HIJ  LM  OPQ   ST  WX

    You missed something very important. In a B-tree, insertions are only done in the leaf node and every full node on the way is split. You inserted Q in a level 2 node in your final tree.

    Edit: I think you are confused about the insertion algorithm. Insertions only take place in the leaf node. In the downward path from root to leaf, if any full node is encountered it is split first. If the leaf node is full, it will be split first and then the key will be inserted. In your case the leaf node OPRST will be split when it is encountered because it has 5 nodes and is full. Thus R will be moved up and and a new leaf node containing keys ST will be created. The older leaf node now will only have OP keys. Q is then compared with R and search moves leftward to OP node where Q finally gets inserted.