Self-Balancing Tree
提纲:
AVL Tree
Red-black Tree
B Tree
B+ Tree
AVL Tree
AVL Tree 是一种自平衡二叉搜索树(self-balancing BST),数中任意节点的左子树与右子树的高度差小于或等于 1,举例如下:
返例如下:
图中节点 8 的左子树高度为 3,右子树高度为 1,差为 2。
AVL 提出的原因在于解决普通二叉树可能出现的降格问题,保证在二叉树中的搜索、插入、删除操作的复杂度都能控制在 的范围内。
Operations
Insertion
Deletion
Insertion
每次插入新节点,先按普通二叉树的 insertion 方式插入,若树中所有节点都满足 AVL Tree 的规定,则插入完毕;若树中有节点不满足 AVL Tree 的规定,则根据情况作出相应的调整。可能出现的情况有 4 种:
i) left - left:
ii) left - right:
iii) right - right:
iv) right - left:
代码实现如下:
Deletion
每次删除节点,先按普通二叉树的 deletion 方式删除,若树中所有节点都满足 AVL Tree 的规定,则删除完毕;若树中有节点不满足 AVL Tree 的规定,则根据情况作出相应的调整。可能出现的情况有 4 种,与 insertion 中的 4 种情况相同,代码实现如下:
Red-Black Tree
Red-Black Tree 与 AVL 一样是自平衡二叉搜索树(self-balancing BST),它的结构要求:
每个 node 都有一种颜色,红或者黑
root node 永远是黑色
不能出现相邻的红色 nodes,即一个红色 node 的 parent 和 child 都必须是黑色
从任意 node 出发到所有 leaf node 的路径上包含的黑色 nodes 数量相等
一棵典型的 Red-Black Tree 举例如下:
Red-Black Tree 提出的原因与 AVL Tree 相同,都在于解决普通二叉树可能出现的降格问题,保证在二叉树中的搜索、插入、删除操作的复杂度都能控制在 的范围内。
它与 AVL Tree 相比:
AVL Tree 在 insert 和 delete 操作中会出现更多的 rotations,因此如果应用的 insert 和 delete 操作频繁,则 Red-Black Tree 更合适;若应用的 search 操作较多,insert 和 delete 操作较少,则 AVL Tree 更合适。
值得注意的是:
一棵只含黑色 nodes 的树有可能是 Red-Black Tree,但它必须是完美平衡树(Perfect Balanced Tree)
存在一棵 Red-Black Tree 不满足 AVL Tree 的性质,如上图中的树
Operations
Insertion
Deletion
Insertion
略
Deletion
略
B Tree
B Tree 是自平衡搜索树 (self-balancing search tree),与 AVL Tree 以及 Red-Black Tree 不同,它不是二叉搜索树,它的使用场景主要在于整棵树无法一次性载入到内存中的场景,当数据需要在 memory 与 disk 之间传输时,各个操作的时间瓶颈就出现在了 disk I/O 上。因此,B Tree 的设计思想是尽可能地矮,使得通往目标 node 的路径尽可能短,从而减少 disk I/O 次数。通常 B Tree 的每个 node 大小为一个 page/block。
B Tree 的主要性质有:
所有的 leaf nodes 都在同一 level
B Tree 的类型由 minimum degree --- t 来定义,t 的取值取决于 page/block 大小
除 root node 外的 nodes 都至少包含 k-1 个 keys,root node 至少包含 1 个 key
所有 nodes 至多包含 2t - 1 个 keys
每个 node 的 children 数量比 keys 数量多 1
一个 node 内部的所有 keys 按升序排列,在 k1 与 k2 之间的所有 keys 都包含在 k1、k2 之间的 child node 中
B Tree 的所有操作复杂度都为
一棵典型的 B Tree 如下图所示:
Operations
Search
Traverse
Insertion
Deletion
Search
与其它搜索树的 search 操作类似,递归地从 root node 开始往下搜索,找到合适的 child node,若发现相应的 key 则返回结果,若知道 leaf node 都没找到, 则返回 NULL。
Traverse
traverse 与 inorder traversal 类似,从左下角的 leaf node 开始,inorder traverse 所有 node。
Insertion
与 BST 类似,从 root node 开始往下搜索,直到 leaf nodes 位置,在路径上每遇到一个 node,都先检查该 node 是否已经 full,若是,则先将其分裂成两个 nodes:
初始化 x 为 root
当 x 不是 leaf node 时
a. 找到 x 中与 key 对应的 child,记为 y
b. 如果 y 不满,则修改 x 为 y
c. 如果 y 已满,则将 y 分裂,根据 key 的大小将 x 修改为 y 分裂后的其中一个 node
循环执行第 2 步,直到 x 为 leaf 为止,这时 x 肯定有足够的空间,直接插入 key 即可
这种实现采用主动分裂的策略,但有可能做出不必要的分裂操作。
Deletion
deletion 操作比较复杂,考虑的情况也比较多,有可能需要:
直接删除
parent 中的某 key 被删除后拆借 child 中的 key
parent 中的某 key 被删除后合并 children
一些可能性如下图所示:
Last updated