Red-Black Trees
【二叉平衡搜索树】
红黑树的性质
（5） 对于每个节点，从节点到子代叶子的所有简单路径都包含相同数量的黑色节点。
红黑树的结构
空叶结点算作【外部节点】
Black-height
【一个红黑树的黑高最多是2ln(N+1)】
证明：
(1) 对任意节点x，sizeof(x) >= 2bh(x) – 1
如果h(x) = 0, x 为 null -> sizeof(x) >= 20 – 1 = 0
假设对所有h(x)<=k成立，对x且h(x)=k+1：
bh(child) = bh(x) 或 bh(x) – 1
由于 h(child) <= k，sizeof(child) >= 2bh(child) – 1 >= 2bh(x) – 1
因此 sizeof(x) = 1 + 2sizeof(child) >= 2bh(x) – 1
(2) bh(Tree) >= h(Tree)/2
Insert 插入
(1) 基础插入操作，同二叉搜索树
(2) 染色操作。如果染成黑色，会影响整个树的黑高；如果染成红色，会存在相邻红节点，或插入为根，破坏了根节点为黑的性质。
->插入思想：按照二叉树插入并染成红色。
*如果能够局部调整，就使用局部调整解决。如果局部调整解决不了，就将问题转移到根节点，通过根节点换色解决。
Delete 删除
(1) 查找树的删除
删除叶结点：把父节点的指针置为NULL
删除单孩节点：把父节点的指针指向单孩节点
删除满节点：找出替换当前位置节点的新节点（左子树最大or右子树最小）把替换节点保持住被删除节点的颜色。
(2) 删除黑节点的情况需要调整。
用例：
①兄弟红易兄弟黑，换色斜旋接着推；
②侄黑父红换兄色，父侄全黑兄染红，上推；
③近侄红来远侄黑，换色斜旋模样改；
④远侄红来令其黑，父兄换色斜旋坠。
B+ Trees
【用于二级存储】
*I/O访问与内存访问相比速度差万倍单位。
B+树的性质
M阶B+树是具有以下结构属性的树：
（1） 根要么是一片叶子，要么有2到M个孩子。
（2） 所有非叶节点（根除外）都有⌈M/2⌉到M个子节点。
（3） 所有的叶子都在同一深度。
假设每个非根叶也有⌈M/2⌉到M个子叶。
叶结点放数据，非叶结点放索引。
4阶B+树（2-3-4树）
B+树的插入
Btree Insert ( ElementType X, Btree T )
{
Search from root to leaf for X and find the proper leaf node;
Insert X;
while ( this node has M+1 keys ) {
split it into 2 nodes with (M+1)/2 and (M+1)/2 keys, respectively;
if (this node is the root)
create a new root with two children;
check its parent;
}
}
*The best choice of M is 3 or 4.
0 条评论