0

我的作业中有关于最小分支因子 t=2 的 b-tree 删除的问题。

                 [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

这将是删除 Y 后的最后一棵树吗……我不确定这就是为什么要在此处更正的原因……谢谢

4

3 回答 3

0

这是个好问题。L 到根，P 到它的右孩子并坐在 WN 附近，它的孩子成为 P 的左孩子删除 Y，W 必须在 R 的中间向下，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-24T18:27:46.717 回答
0

我认为这是不正确的，因为 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-19T16:54:52.073 回答
0

这是个好问题。L 到根，P 到它的右孩子并坐在 WN 附近，它的孩子成为 P 的左孩子删除 Y，W 必须在 R 的中间向下，Y 在 X 和 Z 之间向下，现在你可以删除 Y .. .

            [   L  ]
            /      \

！！！！！！/ \ / \ / \ / \
[G] [P] / \ / \ / \ / \ / \ / \ [BD] [J] NRW
/ | \ / \ / \ / | \
ACFIKMOQ ST XZ --->Y

于 2013-10-24T18:24:32.280 回答