B树和红黑树

1.B树

2.B树和红黑树的关系

3.红黑树

1.B树

B树是一种平衡的多路搜索树，多用于文件系统、数据库的实现

1.1特点：

1. 1 个节点可以存储超过 2 个元素、可以拥有超过 2 个子节点
2. 拥有二叉搜索树的一些性质
3. 平衡，每个节点的所有子树高度一致
4. 矮，查找比较次数少

1.2 n阶B树的性质

• 假设一个节点存储元素的个数为x
  • 根节点： 1<= x <= n-1
  • 非根节点：ceiling(n/2) -1 <=x <=n-1
• 如果有子节点，子节点数目 y= x+1
  • 根节点的子节点数 2<=y<=n
  • 非根节点子节点数 ceiling(n/2) <=y <=n

有个结论：eg : n=4 2<=y<=4 因此称4阶B树为 (2,4)树、 2-3-4树

1.3 B树的搜索

• 类似与BST
  

1. 先在节点内部从小到大开始搜索元素
2. 如果命中，搜索结束
3. 如果未命中，再去对应的子节点中搜索元素，重复步骤 1

1.4 添加元素到B树

• 以添加76为例

添加过程中，当节点的元素个数 等于n（阶数），会产生上溢的现象

• 上溢过程中，可能导致父节点的个数也等于n，那么也会一直上溢，极端情况一直溢到根节点

1.5 B树删除元素

• 删除的元素在叶子节点，则直接删除就可以
• 删除的元素在非叶子节点（复杂）

1. 先找到这个节点的前驱或素，覆盖所需删除元素的值

• 前驱和后继元素必定在叶子节点中

2. 再把所选的前驱或后继元素删除

以删除 元素60为例

(1) 找到前驱元素55 或 后继元素 70
(2) 55或 70覆盖掉 60
(3) 删除叶子节点中 元素55 或 元素 70
(4) 根据B树的性质来，调整B树

• 删除元素后，可能会出现下溢，（不满足 ceiling(n/2)-1<=x <=n-1) ,这里以5阶B树为例

删除元素 22

【22 24】为叶子节点，直接删除，变为【24】不满足 2<=x <=4

如何解决下溢问题

首先，我们应该清楚 下溢的节点 元素的个数必然等于 ceiling(n/2)-2

• 如果下溢节点临近的兄弟节点，有至少ceiling(n/2)个元素，可以向其借一个元素
  • 将父节点的元素 b（最大的元素）插入到下溢节点的0位置。
  • 用兄弟节点的元素a（最大元素）替代父节点的元素b

• 如果下溢节点临近的兄弟节点，只有 ceiling(n/2) − 1 个元素
  • 将父节点的元素 b 挪下来跟左右子节点进行合并
  • 合并后的节点元素个数等于ceiling(n/2) + ceiling(n/2) − 2，不超过 m − 1
  • 这个操作可能会导致父节点下溢，依然按照上述方法解决，下溢现象可能会一直往上传播

删除22，满足第二种情况

关于红黑树和B树

先学习4阶B树（2-3-4树），将能更好地学习理解红黑树

红黑树（RBTree）

红黑树也是一种自平衡的BST，也成为平衡二叉B树

红黑树必须满足一下5种性质：

1. 节点是RED或BLACK
2. 根节点是BLACK
3. 叶子节点（外部节点，空节点）都是BLACK
4. RED节点的子节点都是BLACK
   • RED节点的parent都是BLACK
   • 从根节点到叶子节点的所有路径上不能有两个连续的RED节点
5. 从任一节点，到叶子节点的所有路径都包含相同数目的BLACK节点

满足了以上5种条件，就能保证平衡

2.1红黑树和 4阶B树的等价交换

• 红黑树 和 4阶B树 具有等价性
• BLACK节点 与它 的RED 节点 融合在一起，形成 1 个B树节点
• 红黑树的黑色节点个数 等于 对应 B树的节点的数目

2.2关于树节点的几个term（术语）

• 父节点/子节点

• 兄弟节点

• 叔父节点

• 祖父节点

2.3添加节点

• B树添加节点，新元素必定添加到叶子节点中，此外4阶B树的节点个数要求在 【1，3】之间

• 建议新添加的节点默认为RED，能尽快满足 红黑树的性质，除了性质4 (不能有两个连续的RED节点)
  • 如果添加的是根节点，则染成BLACK

2.3.1添加的所有情况

• 满足（性质4）：即父节点为BLACK（非空）

• 不满足（性质4）：即父节点为RED

接下来修复性质4 -LL（右旋）\RR（左旋）

• 判定条件：叔父节点 为黑色空节点

1. 父节点 染成 BLACK， 祖父节点染成 RED
2. 祖父节点进行 单旋 操作

以添加52、60为例子

接下来修复性质4 -LR\RL

• 判定条件：叔父节点为黑色空节点

1. 自己染成 BLACK, 父节点 染成RED
2. 进行双旋转

LR: 父节点先右旋 祖父节点再左旋

RL：父节点先左旋 祖父节点再右旋

修复性质4 - 上溢-LL/RR

• 判定条件：叔父节点是 RED

1. 叔父节点 和 父节点 染成 BLACK
2. 祖父节点向上合并（染成RED）

祖父节点向上合并时，可能会出现上溢情况，

• 如果一直上溢到根节点，则直接染成黑色

修复性质4- 上溢-LR/RL

• 判定条件；叔父节点 为 RED

1. 父节点、祖父节点 染成 BLACK
2. 祖父节点 向上合并（染成黑色）

2.4删除节点

B树中，最后真正被删除的元素都在叶子节点中

2.4.1 删除-RED节点

• 直接删除，不做任何调整

2.4.2 删除-BLACK节点

3种情况

1. 拥有2个RED子节点的BLACK节点

   • 不能直接删除，（找它的子节点代替删除）

2. 拥有1个RED子节点的BLACK节点

3. 为叶子节点

删除-拥有1个RED子节点的BLACK节点

判定条件：用以替代的子节点是RED节点

• 则将替代的子节点 染成 BLACK 即可保持红黑树性质

删除-BLACK为叶子节,兄弟节点为BLACK

• 条件1：如果兄弟节点 至少有一个 RED子节点 （如上图删除 88）

  • 进行旋转操作
  • 旋转后的中心点 继承 父节点的颜色
  • 旋转后左右节点染色为BLACK

• 条件2；如果兄弟节点 没有RED子节点

  • 将兄弟节点染成RED、 父节点染成BLACK(如下图 删除88)

删除-BLACK为叶子节,兄弟节点为RED

• 将兄弟节点染成BLACK，父节点染成RED，进行旋转
• 然后按照兄弟节点为BLACK的操作

红黑树的平衡

那5条性质仅能保证 红黑树 等价于 4阶B树

• 相比AVL树，红黑树的平衡标准比较宽松：没有一条路径会大于其他路径的2倍
  • AVL树：每个左右子树的高度差不超过1
• 红黑树的最大高度为 2*log2(n+1),依然为O(logn) 级别
• 搜索的次数远远大于插入和删除，选择AVL树；搜索、插入、删除次数几乎差不多，选择红黑树
• 相对于AVL树来说，红黑树牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树

红黑树的平衡标准比较宽松：没有一条路径会大于其他路径的2倍

• AVL树：每个左右子树的高度差不超过1
• 红黑树的最大高度为 2*log2(n+1),依然为O(logn) 级别
• 搜索的次数远远大于插入和删除，选择AVL树；搜索、插入、删除次数几乎差不多，选择红黑树
• 相对于AVL树来说，红黑树牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树

红黑树的时间复杂度

搜索：O(logn)

添加：O(logn)，O(1) 次的旋转操作

删除：O(logn)，O(1) 次的旋转操作

AVL树的时间复杂度

搜索、添加、删除都是O(logn) 复杂度，其中添加仅需O(1) 次旋转调整、删除最多需要O(logn) 次旋转调整