本文主要探讨了B树删除的主要步骤及代码，参考自算法导论。
基本概念：
（1）度数为t的B树，除了根节点以外的所有节点都至少有t-1个值，t个孩子
（2）度数为t的B树，除了根节点以外的所有节点都至多有2t-1个值，2t个孩子
B树(度数为t)的删除情况分为：
-
key k 在 node x （当前节点）上，且当前节点为叶节点，直接删除key k
（这里需要注意，叶子节点值的个数也在[t-1,2t-1]这个区间，但这一步不需要判断删除key k后节点数小于t-1的可能性， 因为包括在了后面的步骤中。同时这里也解决了一个特例就是B树只有一个根节点，没有孩子的情况。） -
key k 在 node x （当前节点）上，且当前节点为非叶节点
(a）k的右孩子 至少有 t 个值，那么找到key k的直接后继 k'，改为删除k'，最后将key k的值改为k' （k'一定在叶节点）
(b) k的右孩子 只有 t-1 个值，但k的左孩子 至少有 t 个值，那么找到key k的直接前驱 k'，改为删除k'，最后将key k的值改为k' （k'一定在叶节点）
(c) k的左右孩子 都只有 t-1 个值，将k与其左右孩子merge，得到共2k-1个值，删除k -
key k 不在 node x （当前节点）上,首先寻找到一定含有k的子树 Ci[x] （这一步就是维持B树结构的保障）
(a）若Ci[x]只有t-1个值，但它的兄弟节点有至少t个值，将兄弟的一个值（最小或大值）上移至父节点，再将父节点的值移到Ci[x]
(b) 若Ci[x]与它的兄弟们只有t-1个值，合并它们。
B-TREE-DELETE-KEY(x,k)
i = 1
if x.leaf //第一步，叶节点的操作
While i <= x.n and k > x.keyi
i = i + 1
if i <= x.n and k == x.keyi
For j = i + 1 to x.n
x.keyj-1 = x.keyj
x.n = x.n - 1
DISK-WRITE(x)
else error ‘key doesn’t exist’
else while i <= x.n and k > x.keyi
i = i + 1
DISK-READ(x.ci)
y = x.ci
if i <= x.n
DISK-READ(x.ci+1)
z = x.ci+1 //y是当前点的左子树，z为右子树
if i <= x.n and k == x.keyi //step2
if y.n >= t //step2.a
k’ = B-TREE-SEARCH-PREDECESSOR(y)
B-TREE-DELETE-KEY(y,k’)
x.keyi = k’
if z.n >= t //step2.b
k’ = B-TREE-SEARCH-SUCCESSOR(z)
B-TREE-DELETE-KEY(z,k’)
x.keyi = k’
else B-TREE-MERGE-CHILD(x,i,y,z) //step2.c
B-TREE-DELETE-KEY(y,k)
else //step3
if i > 1
DISK-READ(x.ci-1)
w = x.ci-1
if y.n = t - 1
if i > 1 and w.n >= t //step3.a
B-TREE-SHIFT-TO-RIGHT-CHILD(x,i,w,y)
else if i <= x.n and z.n >= t //step3.a
B-TREE-SHIFT-TO-LEFT-CHILD(x,i,y,z)
else if i > 1 //step3.b
B-TREE-MERGE-CHILD(x,i,w,y)
y = w
else B-TREE-MERGE-CHILD(x,i,y,z) //step3.b
B-TREE-DELETE-KEY(y,k)
B-TREE-SEARCH-PREDECESSOR(y)
x = y
i = x.n
while not x.leaf
do DISK-READ(x.ci+1)
x = x.ci+1
i = x.n
return x.keyi
B-TREE-SEARCH-SUCCESSOR(y)
x = z
while not x.leaf
do DISK-READ(x.c1)
x = x.c1
return x.key1
B-TREE-MERGE-CHILD(x,i,y,z)
y.n = 2t-1
for j = t+1 to 2t-1
y.keyj = z.keyj-t
y.keyt = x.keyi
if not y.leaf
for j = t+1 to 2t-1
y.cj = z.cj-t
for j = i+1 to x.n
x.cj = x.cj+1
x.n = x.n - 1
DISK-WRITE(y)
DISK-WRITE(z)
DISK-WRITE(x)
B-TREE-SHIFT-TO-RIGHT-CHILD(x,i,y,z)
z.n = z.n + 1
for j = z.n to 2
z.keyj = z.keyj-1
z.key1 = x.keyi
x.keyi = y.keyy.n
if not z.leaf
for j = 1 to z.n
z.cj+1 = z.cj
z.c1 = y.cy.n+1
y.n = y.n - 1
DISK-WRITE(y)
DISK-WRITE(z)
DISK-WRITE(x)
B-TREE-SHIFT-TO-LEFT-CHILD(x,i,y,z)
y.n = y.n + 1
y.keyy.n = x.keyi
x.keyi = z.key1
z.n = z.n - 1
for j = 1 to z.n
z.keyj = z.keyj+1
if not z.leaf
y.cy.n+1 = z.c1
for j = 1 to z.n
z.cj = z.cj+1
DISK-WRITE(y)
DISK-WRITE(z)
DISK-WRITE(x)
网友评论