请教我学数据结构（二）红黑树

摘要

红黑树是一种特殊的二叉查找树，能够通过操作实现自平衡。

定义和性质

（1）根节点和叶子节点都为黑色

（2）红色节点的子节点都为黑色

（3）任意一个节点到每一个叶子节点的路径所包含的黑色节点树相同。

红黑树的自平衡通过三种操作实现：左旋、右旋和变色

左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。

右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。

变色：结点的颜色由红变黑或由黑变红。

红黑树查找

1. 从根结点开始查找，把根结点设置为当前结点；

2. 若当前结点为空，返回null；

3. 若当前结点不为空，用当前结点的key跟查找key作比较；

4. 若当前结点key等于查找key，那么该key就是查找目标，返回当前结点；

5. 若当前结点key大于查找key，把当前结点的左子结点设置为当前结点，重复步骤2；

6. 若当前结点key小于查找key，把当前结点的右子结点设置为当前结点，重复步骤2；

红黑树插入

插入操作包括两部分工作：一查找插入的位置；二插入后自平衡。查找插入的父结点很简单，跟查找操作区别不大：

1. 从根结点开始查找；
2. 若根结点为空，那么插入结点作为根结点，结束。
3. 若根结点不为空，那么把根结点作为当前结点；
4. 若当前结点为null，返回当前结点的父结点，结束。
5. 若当前结点key等于查找key，那么该key所在结点就是插入结点，更新结点的值，结束。
6. 若当前结点key大于查找key，把当前结点的左子结点设置为当前结点，重复步骤4；
7. 若当前结点key小于查找key，把当前结点的右子结点设置为当前结点，重复步骤4；

插入时包含以下情景

红黑树删除

红黑树的删除操作也包括两部分工作：一查找目标结点；而删除后自平衡。查找目标结点显然可以复用查找操作，当不存在目标结点时，忽略本次操作；当存在目标结点时，删除后就得做自平衡处理了。删除了结点后我们还需要找结点来替代删除结点的位置，不然子树跟父辈结点断开了，除非删除结点刚好没子结点，那么就不需要替代。

二叉树删除结点找替代结点有3种情情景：

• 情景1：若删除结点无子结点，直接删除
• 情景2：若删除结点只有一个子结点，用子结点替换删除结点
• 情景3：若删除结点有两个子结点，用后继结点（大于删除结点的最小结点）替换删除结点