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 条评论
下一页