RB-tree
红黑树是 自平衡的 二叉查找树
定义和性质:
- 性质1:节点只有红色和黑色。
- 性质2:根节点是黑色。
- 性质3:每个叶子节点(NIL)都是黑色。
- 性质4:每个红色结点的两个子结点一定都是黑色。
-
性质5:任意一结点到每个叶子结点的路径都包含数量相同的黑结点。
- 推出:性质5.1:如果一个结点存在黑子结点,那么该结点肯定有两个子结点
红黑树的插入节点是红色
左旋:
- 以某个结点作为支点(旋转结点),其右子结点变为旋转结点的父结点,右子结点的左子结点变为旋转结点的右子结点,左子结点保持不变
右旋:
- 以某个结点作为支点(旋转结点),其左子结点变为旋转结点的父结点,左子结点的右子结点变为旋转结点的左子结点,右子结点保持不变。
变色:
- 结点的颜色由红变黑或由黑变红。
插入:
(假设p为父节点,s为叔节点,pp为祖父节点)
1. 插入节点为空树: 插入节点作为,并设置为黑色
2. 插入节点key存在: 更新value为插入的值
3. 插入节点的父节点为黑节点: 直接插入
4. 插入节点的父节点为红节点:
-
4. 1 叔节点存在且为红色:
- 将P和S设置为黑色
- PP设置为红色
- PP设置为当前插入节
-
4. 2 叔节点不存在或为黑节点,且父节点是祖父节点的左子节点
-
4. 2. 1 插入节点是父节点的左子节点:
- P设为黑色
- pp设为红色
- pp进行右旋
-
4. 2. 2 插入节点是父节点的右子节点:
- P进行左旋
- P设置为插入节点,得到4. 2. 1
- 进行4. 2. 1处理
-
4. 2. 1 插入节点是父节点的左子节点:
-
4.3 叔节点不存在或为黑节点,且父节点是祖父节点的右子节点
-
4. 3. 1 插入节点是父节点的右子节点:
- P设为黑色
- pp设为红色
- pp进行左旋
-
4. 3. 2 插入节点是父节点的左子节点:
- P进行左旋
- P设置为插入节点,得到4. 3. 1
- 进行4. 3. 1处理
-
4. 3. 1 插入节点是父节点的右子节点:
删除:
- 删除节点无子节点,红色直接删,黑色需要平衡
- 删除节点有一个子节点,因为删除节点必定是黑色,子节点必定是红色,子节点替换删除节点
- 删除节点有两个子节点,用后继节点替换为删除节点,情形转为1或2处理
后继节点和前继节点都行,习惯上用后继节点;
后继节点:删除节点右子树最左节点;
把二叉树所有结点投射在X轴上,所有结点都是从左到右排好序的,所有目标结点的前后结点就是对应前继和后继结点;
删除结点被替代后,在不考虑结点的键值的情况下,对于树来说,可以认为删除的是替代结点!,基于此,三种场景可相互转化,最后转化为第一种情况。
综上所述,删除操作删除的结点可以看作删除替代结点,而替代结点最后总是在树末。
先看删除节点,再看兄弟节点,再看兄弟节点子节点,再看父节点