红黑树（Red Black Tree）

也称做Symmetric Binary B-tree

1.节点是red或者black

2.根节点是black

3.叶子节点（外部节点或者空节点–假象出来的 ）都是black

4.red节点的子节点都是black

推论1:red节点的父节点都是balck

推论2:从根节点到叶子节点（这里的叶子节点是指空节点）的所有路径上不能有2个连续的red节点

5.从任意节点到叶子节点到所有路径都包含相同数目的black节点

B树

定义：B树是一种平衡的多路搜索树

B树的阶数（n>=）：B树的某个节点最多拥有n个子节点

目的：通过了解B树来更容易的掌握红黑树

特点：

1. 1个节点可以储存超过2个元素，可以拥有超过2个子节点

2. 拥有BST的性质

3. 平衡，每个节点的所有子树高度都一致

4. 比较矮

   

性质：

floor：向下取整

Ceiling:向上取整

m为B树的阶树

B树 VS BST

1.B树和二叉搜索树在逻辑上是等价的

（通过对BST多代和并可以得到超级节点）

2.BST两代合并最多拥有4个子节点

3.三代合并最多拥有8个子节点

4.n代合并最多拥有2^n个子节点

5.m阶B树 做多需要log2m代合并（从根节点开始合并）

搜索：

添加

1.新添加的节点一定是叶子节点：因为B树也是一颗平衡搜索树，所以添加位置一定为叶子节点

2.因为4阶b树的子节点个数最多为3个，假设4阶b树的某节点有4个子节点则4个子节点就可以给出5个分支 – 和4阶b树的定义违背

3.4阶b树很特别：根节点和非根节点个数都可以是1-3

4.上溢到根节点是使得b树增高的唯一途径（见下下下下图）

overflow的解决办法：

删除

1.下溢是使得b树高度变矮的唯一途径

因为非叶子节点一定有前驱或者后继节点在子树中（类似于BST树中度为2的节点的删除）

注意d的处理（和AVL处理类似）

对为什么合并后不超过m-1的数学证明：

红黑树

红黑树与B树

1.添加前将红黑树当作2-3-4树看待（Black节点和它的RED节点融合在一起,形成一个B树节点）

2.红黑树的Black节点个数与4阶B树（每个节点1-3个元素 如果有子节点-每个节点2-4个子节点）的节点总个数相等

3.下图不符合红黑树标准

继承结构

属性字段

1.Node要有颜色

辅助方法

添加

1.建议新添加的节点默认为红色，这样可以更快满足红黑树5条性质中的1 2 3 5

如果是根节点染成红色即可

2.添加的节点一定是叶子节点，且只能是4种情况

3.新添加的节点只可能有12种情况

情况一：新添加的parent节点为BLACK（满足性质1 2 3 4 5）且满足四阶B树的性质（节点的元素个数1-3 节点的子节点个数2-4）不用做任何处理

情况二：

其他8种情况都是double red 要做处理 – 因为都违背了性质四

修复1:LL\RR（uncle不是red 是空节点是black）

对于52的处理，将50染为黑色 46染为红色 并且对46号节点进行左旋转

对于60的处理，将60染为黑色 72染为红色 并且对76号节点进行左旋转

1
2

1.parent染成Black grand染成red
2.grand进行单旋操作

修复2:LR\RL（uncle不是red 是空节点是black）

1.将自己染成BLACK 祖父节点染成RED（目的是让BLACK节点变为子树的根节点 因为B树要求了合并就是让红黑树的BLACK节点和它的红色子节点合并）

1
2

1.将自己染成BLACK grand染成RED
2.进行双旋操作

修复3：上溢（叔父节点是红色）

将25向上合并（17也可以 但是比较麻烦一点）

25左右节点分裂（默认就已经分裂好了）并成为独立节点（将35染成黑色 17染成黑色 这样才能满足红黑树转化为B树的要求 – 黑色节点和它的子节点合并）

1
2
3
4
5

1.parent、uncle染成BLACK
2.grand向上合并
  将grand染成RED，当作是新添加的节点进行处理（相当于递归）
  grand合并时可能会继续发生上溢
  若上溢到根节点，只需根节点染成Black

修复4：上溢 - RR（叔父节点是红色)