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
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