数据结构:Red_Black_Tree

红黑树(Red Black Tree)

也称做Symmetric Binary B-tree

1.节点是red或者black

2.根节点是black

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

截屏2022-01-19 下午12.51.26

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

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

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

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

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

B树的阶数(n>=):B树的某个节点最多拥有n个子节点

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

特点:

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

  2. 拥有BST的性质

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

  4. 比较矮

    截屏2022-01-20 下午8.28.25

floor:向下取整

Ceiling:向上取整

m为B树的阶树

截屏2022-01-20 下午8.41.13

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

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

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

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

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

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

截屏2022-02-09 下午9.08.58

https://cdn.jsdelivr.net/gh/Nngxu/ImgHosting/PicGo/%E6%88%AA%E5%B1%8F2022-01-20%20%E4%B8%8B%E5%8D%889.41.28.png

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

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

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

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

截屏2022-01-20 下午9.41.54

https://cdn.jsdelivr.net/gh/Nngxu/ImgHosting/PicGo/%E6%88%AA%E5%B1%8F2022-01-20%20%E4%B8%8B%E5%8D%889.48.21.png

https://cdn.jsdelivr.net/gh/Nngxu/ImgHosting/PicGo/%E6%88%AA%E5%B1%8F2022-01-20%20%E4%B8%8B%E5%8D%889.49.00.png

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

截屏2022-01-20 下午9.50.59

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

截屏2022-01-20 下午9.51.12 截屏2022-01-20 下午9.54.01

注意d的处理(和AVL处理类似)

截屏2022-01-20 下午9.54.15 截屏2022-01-20 下午9.54.58

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

截屏2022-01-20 下午10.03.19

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

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

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

https://cdn.jsdelivr.net/gh/Nngxu/ImgHosting/PicGo/%E6%88%AA%E5%B1%8F2022-01-22%20%E4%B8%8B%E5%8D%8810.35.31.png

截屏2022-01-18 上午10.08.39

1.Node要有颜色

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

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

截屏2022-01-22 下午10.39.03截屏2022-01-22 下午10.39.30

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

https://cdn.jsdelivr.net/gh/Nngxu/ImgHosting/PicGo/%E6%88%AA%E5%B1%8F2022-01-22%20%E4%B8%8B%E5%8D%8810.45.04.png

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

https://cdn.jsdelivr.net/gh/Nngxu/ImgHosting/PicGo/%E6%88%AA%E5%B1%8F2022-01-22%20%E4%B8%8B%E5%8D%8810.53.23.png

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

https://cdn.jsdelivr.net/gh/Nngxu/ImgHosting/PicGo/%E6%88%AA%E5%B1%8F2022-01-22%20%E4%B8%8B%E5%8D%8810.55.41.png

情况二:

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

https://cdn.jsdelivr.net/gh/Nngxu/ImgHosting/PicGo/%E6%88%AA%E5%B1%8F2022-01-22%20%E4%B8%8B%E5%8D%8811.05.25.png

修复1:LL\RR(uncle不是red 是空节点是black)

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

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

https://cdn.jsdelivr.net/gh/Nngxu/ImgHosting/PicGo/%E6%88%AA%E5%B1%8F2022-01-22%20%E4%B8%8B%E5%8D%8811.10.04.png

https://cdn.jsdelivr.net/gh/Nngxu/ImgHosting/PicGo/%E6%88%AA%E5%B1%8F2022-01-22%20%E4%B8%8B%E5%8D%8811.19.34.png

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

修复2:LR\RL(uncle不是red 是空节点是black)

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

https://cdn.jsdelivr.net/gh/Nngxu/ImgHosting/PicGo/%E6%88%AA%E5%B1%8F2022-01-22%20%E4%B8%8B%E5%8D%8811.22.21.png

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

修复3:上溢(叔父节点是红色)

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

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

https://cdn.jsdelivr.net/gh/Nngxu/ImgHosting/PicGo/%E6%88%AA%E5%B1%8F2022-01-22%20%E4%B8%8B%E5%8D%8811.44.40.png

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

https://cdn.jsdelivr.net/gh/Nngxu/ImgHosting/PicGo/%E6%88%AA%E5%B1%8F2022-01-22%20%E4%B8%8B%E5%8D%8811.53.16.png修复4:上溢 - RR(叔父节点是红色)