从B树删除

我在我的家庭作业中有关于最小分支因子t = 2的B树删除的问题。从B树删除

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

现在从上面的树除去Y后，我得到了最终的树..

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

这会不会是最后的树Ÿ删除后......我不知道这就是为什么在这里张贴到是corrected..thankss

来源

2013-10-19 Daket

T怎么能在W的右子树上？ – Justin

我不认为这是正确的，T不能在W的因为T谈到W.

前

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

右子树

步骤如下：

删除Y：

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

替换右子树（Z）最小的，平衡的个Z旧的位置

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

无法从兄弟姐妹借钱（ X）合并Z的子女：

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

不能从兄弟姐妹（R）借用，合并子女仁为W：

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

合并节点（先前W）现过大，平分：

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

的T左节点现在是过大，平分：

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

T的右节点也太大，均匀分割：

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

来源

2013-10-19 16:54:52 Justin

你在这里应用的删除案例：我没有得到这个答案...我现在知道，T不能在右边的子树W ... – Daket

@ambani我已经更新了我的答案，以帮助解释。 – Justin

谢谢，我明白了......感谢一吨...... :) – Daket

这是个好问题。 L去根， P去它的右边的孩子，坐在W N附近，它的孩子成为删除Y的P 的左边孩子，W必须去掉R和Y的中间部分 Y在X和Z之间下降现在你可以删除Y ...

  [ L ] 
      / \

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

来源

2013-10-24 18:24:32 strftm

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

来源

2013-10-24 18:27:46 strftm

回答

相关问题