R-B Tree
2020-12-18 18:47:41 0 举报
红黑树
作者其他创作
大纲/内容
AVL树特性：1.左子树上所有结点的值均小于或等于它的根结点的值。右子树上所有结点的值均大于或等于它的根结点的值。2.左、右子树也分别为二叉排序树。3. 左右叶子节点的深度差不会超过1。
Dr
BL
后继节点R替换D
2. 红黑树的插入操作
R
P
N
变色
B
DR
P 左旋转
DL
...
PP
场景2：插入结点的父结点为黑结点
插入节点N
场景5：替换节点是黑节点，替换节点的兄弟节点是黑节点，且有一个左节点（必定是红色，否则无法平衡）
变成和场景4一样
D代替E的位置之后，相当于删除节点D，就是情景1的场景，直接删除即可
BR
1
N2
2
1. 红黑树的诞生
根节点为空树
对父节点Dr进行左旋转
场景3：替换节点是黑节点，替换节点的兄弟节点是黑节点，且没有子节点
D
二叉查找树（BST）特性：1.左子树上所有结点的值均小于或等于它的根结点的值。2.右子树上所有结点的值均大于或等于它的根结点的值。3.左、右子树也分别为二叉排序树。
3
删除节点D
左边黑色节点多，不平衡
C
父节点红色节点，说明一定还有祖父节点
nil
N1
P 右旋转
A
场景2：替换节点是黑节点，替换节点的兄弟节点是红结点，那兄弟节点必然有两个黑色左右节点
H
不考虑N和D的数值区别，实际上是相当于删除了后继节点D的位置
I
旋转：对R的父节点Dr进行左旋
3. 前继节点和后继节点
对兄弟节点B进行右旋旋转，然后回到场景4的第二步的状态，按照场景4继续操作即可。
将R的父节点Dr设为当前递归节点，继续按照第三步进行变色，直到根节点或者遇到红色节点
1. 斜树2. 不稳定
N3
F
左旋转
场景1：红黑树为空树
变色：原来R的兄弟节点变黑，R兄弟的左孩子变红
E
和场景6正好相反
场景4：替换节点是黑节点，替换节点的兄弟节点是黑节点，且有一个右节点（必定是红色，否则无法平衡）
对父节点Dr进行左旋
场景6：插入结点的父结点为红结点，叔叔节点为黑结点或不存在，并且父节点为右子节点。
4. 删除操作思路
J
场景5：插入结点的父结点为红结点，叔叔节点为黑结点或不存在，并且插入节点为右子节点。
和场景4正好相反
前继节点
后继节点
使用后继节点E替代目标节点N，但是E有子节点，此时相当于转化成删除节点E
删除目标节点N，情景3：目标节点有两个子节点
场景6：替换节点是黑节点，替换节点的兄弟节点是黑节点，且有两个子节点（必定是红色，否则无法平衡）
右旋转
父节点为黑色节点
1. 复衡成本高2. 不够稳定
场景4：插入结点的父结点为红结点，叔叔节点为黑结点或不存在，并且插入节点为左子节点。
当前节点
Container
E节点只有一个子节点，相当于情景2，用子节点D代替E节点的位置
场景3：插入结点的父结点为红结点，叔叔节点为红结点
红黑树：性质1：每个节点要么是黑色，要么是红色。性质2：根节点是黑色。性质3：每个叶子节点（NIL）是黑色。性质4：每个红色结点的两个子结点一定都是黑色。性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。
删除节点N
1.将R父节点颜色赋给R的兄弟节点2.将R父节点和兄弟节点的右孩子都设置黑色
1.将父节点的颜色赋给兄弟节点；2.将兄弟节点的右孩子设为黑色；3.将父节点设为黑色；
5. 删除情景的转换关系
1.将兄弟节点的左孩子设置为黑色；2.将兄弟节点设置为红色；
场景1：替换节点是红色节点。可以断定，替换节点没有兄弟节点，或者有一个红色兄弟节点
变色：原R的兄弟改为红色
场景7：插入结点的父结点为右红结点，叔叔节点为黑结点或不存在，并且插入节点为左子节点。
替换节点是左孩子节点
叔叔只有是叶子才能满足黑色平衡，叶子节点就不画出来了
0 条评论
回复 删除
下一页
