leonacwa / leonacwa.github.io Goto Github PK
View Code? Open in Web Editor NEWMy BLog
My BLog
《算法导论》第3版
为简单起见,我们假定,就像二叉搜索树和红黑树中一样,任何和关键字相联系的“卫星数据”(satellite information)将与关键字一样存放在同一节点中。实际上,人们可能只是为每个关键字存放一个指针,这个指针指向存放该关键字的卫星数据的磁盘页。
一个常见的B树的变种,称为 B+树(B+ - Tree),他把所有卫星数据都存储在叶节点中,内部节点只存放关键字和孩子指针,一次最大化了内部节点的分支因子。
一棵B树 T 是具有以下性质的有根树(根为 T.root):
B树上大部分的操作所需的磁盘存取次数与B树的高度是成正比的。现在来分析B树最坏情况下的高度。
定理 18.1 如果 n >= 1,那么对任意一颗包含n个关键字、高度为和、最小度数t>=2的B树T,有: h <= logt (n+1/2) 。
约定:B树的根节点始终在主存中;当根节点被改变后,需要对根节点做一次 DISK-WRITE 操作。任何被当作参数的节点在被传递之前,都要对他们先做一次 DISK-READ 操作。
B-TREE-SEARCH(x, k) :
i = 1
while i <= x.n and k > x.key[i] :
i = i + 1
if i <= x.n and k == x.key[i] :
return (x, i) // k 在 x 节点的 i 下标位置
elif x.leaf : // x 是叶节点
return NIL
else :
DISK-READ(x.c[i]) // 读取 x 节点 c[i] 孩子
return B-TREE-SEARCH(x.c[i], k)
ALLOCATE-NODE 在 O(1) 时间内为一个新节点分配一个磁盘页。我们可以假定由 ALLOCATE-NODE 所创建的节点并不需要 DISK-READ ,因为磁盘上还没有关于该节点的有用信息。
B-TREE-CREATE(T) :
x = ALLOCATE-NODE()
x.leaf = TRUE # 初始化的第一个节点是叶子节点
x.n = 0
DISK-WRITE(x)
T.root = x
由于不能将关键字插入一个满的叶节点,故引入一个操作,将一个满的节点 y (有2t-1个关键字)按其中间关键字(midian key) y.key[t] 分裂(split) 为两个各含 t-1 个关键字的节点。中间关键字被提升到 y 的父节点,以标识两棵新树的划分点。但是如果 y 的父节点也是满的,就必须在插入新的关键字之前将其分裂,最终满节点的分裂会沿着树向上传播。
我们不是等到找出插入过程中实际要分裂的满节点时才做分裂。相反,当沿着树往下查找新的关键字所属位置时,就分裂沿途遇到的每个满节点(包括叶节点本身)。因此,每当要分裂一个满节点 y 时,就能确保它的父节点不是满的。
分裂是树长高的唯一途径。
B-TREE-SPLIT-CHILD(x, i) : // 分裂 x 节点的 i 孩子, x.c[i] 包含 2t-1 个关键字
z = ALLOCATE-NODE() // 创建的新节点 z 存储 x.c[i] 右边的关键字,即 x.c[i].key[t+1..2t-1]
y = x.c[i]
z.leaf = y.leaf
z.n = t - 1
for j = 1 to t-1 :
z.key[j] = y.key[j+t]
if not y.leaf : // 分裂的 y 节点不是叶子
for j = 1 to t :
z.[j] = y.c[j+t]
y.n = t - 1
for j = x.n + 1 downto i + 1 : // 移动孩子节点 x.c[i+1 .. x.n+1]
x.c[j+1] = x.c[j]
x.c[i+1] = z
for j = x.n downto i : // 移动关键字 x.key[i .. x.n]
x.key[j+1] = x.key[j]
x.key[i] = y.key[t]
x.n = x.n + 1
DISK-WRITE(y)
DISK-WRITE(z)
DISK-WRITE(x)
在一棵高度为h的B树T中,以沿着树单程下行方式插入一个关键字k的操作需要O(h)次磁盘存取。所需要的CPU时间为O(th)=O(t logt n)。
B-TREE-INSERT(T, k) :
r = T.root
if r.n == 2t - 1 : // 如果根节点是满的
s = ALLOCATE-NODE()
T.root = s
s.leaf = FALSE
s.n = 0
s.c[1] = r
B-TREE-SPLIT-CHILD(s, 1)
B-TREE-INSERT-NONFULL(s, k)
else :
B-TREE-INSERT-NONFULL(r, k)
B-TREE-INSERT-NONFULL(x, k) :
i = x.n
if x.leaf :
while i >= 1 and k < x.key[i]
x.key[i+1] = x.key[i]
i = i - 1
x.key[i+1] = k
x.n = x.n + 1
DISK-WRITE(x)
else :
while i >= 1 and k < x.key[i] :
i = i - 1
i = i + 1
DISK-READ(x.c[i])
if x.c[i].n == 2t - 1 : // x.c[i] 是满的,有 2t-1 个关键字,需要分裂
B-TREE-SPLIT-CHILD(x, i)
if k > x.key[i] :
i = i + 1
B-TREE-INSERT-NONFULL(x.c[i], k)
删除时要保证当前节点 x 至少包含 t 个关键字,这样从 x 中删除 k 时,剩余 t-1 个关键字还能保证B树的性质。为了保证 x 节点至少包含 t 个关键字,可能要从兄弟子树借来一个节点,或者合并两个相邻子树,来保证 x 节点有至少 t 个关键字。
删除时遇到的情况:
如果关键字 k 在节点 x 中,并且 x 是叶节点,则从 x 中删除 k 。
如果关键字 k 在节点 x 中,并且 x 是内部节点,(y中的关键字都小于 k ,或者是在k之前),则做如下操作:
a. 如果节点 x 中在 k 之前的孩子节点 y 有至少 t 个关键字,则在孩子节点 y 中找到 k 的前驱关键字 k' ,递归删除 k' ,然后在节点 x 中用 k' 替换 k 。(找到 k ' 并删除它可以在沿树下降的过程中完成)
b. 如果 x 的孩子节点 y 拥有的关键字数量少于 t 个,即只有 t-1 个,那么,检查 x 节点中在关键字 k 之后的孩子节点 z ,如果 z 至少有 t 个关键字,则在 z 中找出 k 的后继 k' ,递归的删除 k' ,然后用 k' 替换掉 k 。(找到 k ' 并删除它可以在沿树下降的过程中完成)
c. 如果孩子节点 y 和 z 都只有 t-1 个关键字,则将 k 和 z 的全部关键字和孩子节点连接合并进 y ,这样 x 就失去了 k 和 指向 z 的指针,此时的 y 包含 2t-1 个关键字。然后释放 z ,并递归地从 y 中删除 k 。
如果关键字 k 不在节点 x 中,则要确定必包含 k 的子树的根 x.c[i] (如果k确实在树中)。如果 x.c[i] 只有 t-1 个关键字,必须执行步骤 3a 或 3b 来保证降至一个至少包含 t 个关键字的的节点。然后通过对 x 某个合适的子节点进行递归而结束。
a. 如果 x.c[i] 只有 t-1 个关键字,但是它的一个相邻的兄弟至少包含 t 个关键字,则将 x 中的某个关键字降至 x.c[i] 中,将 x.c[i] 的相邻左兄弟或者右兄弟中的一个关键字升至 x ,将该兄弟中相应的孩子指针移动到 x.c[i] 中,这样就使得 x.c[i] 增加了一个额外的关键字。
b. 如果 x.c[i] 和 x.c[i] 的所有相邻兄弟都只包含 t-1 个关键字,则将 x.c[i] 与一个兄弟合并,即将 x 的一个关键字移动到新合并的节点,使之成为该节点的中间关键字。
B-TREE-DELETE(T, k) :
r = T.root
p = B-TREE-SEARCH(x, k)
if p == NIL :
return
B-TREE-DELETE-NODE(r, k)
B-TREE-GET-PREDECESSOR-KEY( y )
while FALSE == y.leaf :
y = y.c[y.n + 1]
retrun y.key[y.n]
B-TREE-GET-SUCCESSOR-KEY( y )
while FALSE === y.leaf :
y = y.c[1]
return y.key[1]
B-TREE-MERGE-CHILD(x, i) : # 将 x.key[i] 和 z 合并到 y 中,此时 y.n 和 z.n 应该都是 t-1,x.n至少是t
y = x.c[i] # k 之前的 孩子节点
z = x.c[i+1] # k 之后的孩子节点
y.key[y.n+1] = x.key[i] #
for j = 1 to z.n : # 复制 z 的数据到 y 中
y.key[y.n+1+j] = z.key[j]
y.c[y.n+1+j] = z.c[j]
y.n = y.n + 1 + z.n
y.c[y.n + 1] = z.c[z.n + 1]
for j = i to x.n-1 :
x.key[j] = x.key[j+1]
x.c[j] = x.c[j+1]
x.n = x.n - 1
B-TREE-RELEASE(z) # 最后释放 z 节点
B-TREE-DELETE-NODE(x, k) :
i = 1
while i <= x.n and x.key[i] < k :
i = i + 1
if i <= x.n and x.key[i] == k : # Case 1 & 2 : k 在节点 x 中
if x.leaf : # Case 1: x 是叶子节点
for j = i to (x.n - 1) :
x.key[j] = x.key[j+1]
x.n = x.n - 1
return
else : # Case 2 : x 是内节点
y = x.c[i] # k 之前的孩子节点
z = x.c[i+1] # k 之后的孩子节点
if y.n >= t : # Case 2a : 节点 x 中在 k 之前的孩子节点 y 有至少 t 个关键字
k2 = B-TREE-GET-PREDECESSOR-KEY( y )
B-TREE-DELETE-NODE(y, k2)
x.key[i] = k2
return
elif z.n >= t : # Case 2b : 节点 x 中在关键字 k 之后的孩子节点 z 至少有 t 个关键字
k2 = B-TREE-GET-SUCCESSOR-KEY( z )
B-TREE-DELETE-NODE(z, k2)
x.key[i] = k2
return
else : # Case 2c :
B-TREE-MERGE-CHILD(x, i)
B-TREE-DELETE-NODE(y, k)
return
else : # Case 3 : k 不在 x 节点中
c = x.c[i]
if c.n < t : # Case 3 :
left = i > 1 ? x.c[i-1] : NIL
right = i <= x.n ? x.c[i+1] : NIL
if left != NIL and left.n >= t : # Case 3a.1 x.c[i] 其中一个兄弟如果有
for j = c.n downto 1 :
c.key[j+1] = c.key[j]
c.key[1] = x.key[i-1]
# 如果 left 是叶子节点,可以不用复制孩子数组
for j = c.n+1 downto 1 :
c.c[j+1] = c.c[j]
c.c[1] = left.c[left.n+1]
c.n = c.n + 1
x.key[i-1] = left.key[left.n]
left.n = left.n - 1
elif right != NIL and right.n >= t : # Case 3a.2 x.c[i] 其中一个兄弟如果有
c.key[c.n+1] = x.key[i]
c.n = c.n + 1
x.key[i] = right.key[1]
right.n = right.n - 1
for j = 1 to right.n :
right.key[j] = right.key[j+1]
# 如果 right 是叶子节点,可以不用复制孩子数组
c.c[c.n+1] = right.c[1]
for j = 1 to right.n + 1 :
right.c[j] = right.c[j+1]
else : # Case 3b : 将 x.c[i] 与其中一个兄弟节点合并
if left != NIL :
B-TREE-MERGE-CHILD(x, i - 1)
c = x.c[i-1]
elif right != NIL :
B-TREE-MERGE-CHILD(x, i)
c = x.c[i]
B-TREE-DELETE-NODE(c, k)
分析:尽管这个过程很复杂,但是一棵高度为 h 的B树,它只需要 O(h) 次磁盘操作,因为在递归调用该过程之间,仅需 O(1) 次对 DISK-READ 和 DISK-WRITE 的调用。所需的CPU时间为 O(t h) = O(t logt n)
.
.
.
.
End.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.