Deletion from B tree

Question

I have question in my homework its about b-tree deletion with minimum branching factor t=2.

                 [P]
               /      \
              /        \
             /          \
            /            \
           /              \     
        [G][L]            [W]
       /  |   \          /   \
      /   |    \        /     \
     /    |     \      /       \
   BD     J      N     R        Y
 / | \   / \    / \   / \      / \
A  C  F  I K    M  O  Q  ST   X   Z

Now after deleting Y from the above tree i get the final tree..

                 [P]
               /      \
              /        \
             /          \
            /            \
           /              \     
        [G][L]            [W]
       /  |   \          /   \
      /   |    \        /     \
     /    |     \      /       \
   BD     J      N     R        X
 / | \   / \    / \   / \      / \
A  C  F  I K    M  O  Q  S    T   Z

Will this be the final tree after Deleting Y... i am not sure thats why posting here to be corrected..thankss

Answer 1

I don't think it's correct, T cannot be in the right sub-tree of W since T comes before W.

                 [P]
               /      \
              /        \
             /          \
            /            \
           /              \     
        [G][L]            [T]
       /  |   \          /   \
      /   |    \        /     \
     /    |     \      /       \
   BD     J      N     R        X
 / | \   / \    / \   / \      / \
A  C  F  I K    M  O  Q  S    W   Z

Here are the steps:

Remove Y:

                 [P]
               /      \
              /        \
             /          \
            /            \
           /              \     
        [G][L]            [W]
       /  |   \          /   \
      /   |    \        /     \
     /    |     \      /       \
   BD     J      N     R       null
 / | \   / \    / \   / \      / \
A  C  F  I K    M  O  Q  ST   X   Z

Replace with smallest from right sub-tree (Z), rebalance at Z's old location

                 [P]
               /      \
              /        \
             /          \
            /            \
           /              \     
        [G][L]            [W]
       /  |   \          /   \
      /   |    \        /     \
     /    |     \      /       \
   BD     J      N     R        Z
 / | \   / \    / \   / \      /
A  C  F  I K    M  O  Q  ST   X 

Cannot borrow from sibling (X), merge children at Z:

                 [P]
               /      \
              /        \
             /          \
            /            \
           /              \     
        [G][L]            [W]
       /  |   \          /   \
      /   |    \        /     \
     /    |     \      /       \
   BD     J      N     R      [X,Z]
 / | \   / \    / \   / \  
A  C  F  I K    M  O  Q  ST

Cannot borrow from sibling (R), merge children at W:

                 [P]
               /      \
              /        \
             /          \
            /            \
           /              \     
        [G][L]      [Q,R,S,T,W,X,Z]
       /  |   \       
      /   |    \    
     /    |     \   
   BD     J      N  
 / | \   / \    / \  
A  C  F  I K    M  O

Merged node (previously W) is now too large, split evenly:

                 [P]
               /      \
              /        \
             /          \
            /            \
           /              \     
        [G][L]            [T]
       /  |   \          /   \
      /   |    \     [Q,R,S] [W,X,Z]
     /    |     \   
   BD     J      N  
 / | \   / \    / \  
A  C  F  I K    M  O

Left node of T is now too large, split evenly:

                 [P]
               /      \
              /        \
             /          \
            /            \
           /              \     
        [G][L]            [T]
       /  |   \          /   \
      /   |    \        / [W,X,Z]
     /    |     \      /
   BD     J      N     R
 / | \   / \    / \   / \
A  C  F  I K    M  O  Q  S

Right node of T is also too large, split evenly:

                 [P]
               /      \
              /        \
             /          \
            /            \
           /              \     
        [G][L]            [T]
       /  |   \          /   \
      /   |    \        /     \
     /    |     \      /       \
   BD     J      N     R        X
 / | \   / \    / \   / \      /  \
A  C  F  I K    M  O  Q  S    W    Z

Answer 2

it is so good question. L goes to the root, P goes to it's right child and sit near W N and it's children becomes left child of P for delete Y, W must go middle down of R and Y Y goes down between X and Z now you can delete Y ...

            [   L  ]
            /      \

!!!!!! / \ / \ / \ / \
[G] [P] / \ / \ / \ / \ / \ / \ [B D] [J] N R W
/ | \ / \ / \ / | \
A C F I K M O Q ST X Z --->Y

Answer 3

it is so good question. L goes to the root, P goes to it's right child and sit near W N and it's children becomes left child of P for delete Y, W must go middle down of R and Y Y goes down between X and Z now you can delete Y ...

            [   L  ]
            /      \
           /        \
          /          \
         /            \
        /              \     
      [G]              [P]
      /  \            /   \
     /    \          /     \
    /      \        /       \
 [B D]     [J]     N       R  W      
 / | \     / \    / \     /  |  \     
A  C  F   I   K  M   O   Q  ST  X Z --->Y