红黑树

介绍

红黑树是一种含有红黑节点并能自平衡的二叉查找树，特点就是自平衡。

在进行插入和删除等可能会破会树的平衡的操作时，它需要重新自处理达到平衡状态。

性质

• 根几点是黑色
• 每个节点要么是红色，要么是黑色
• 每个叶子节点是黑色
• 每个红色节点的两个子节点一定都是黑色
• 任意一节点到每个叶子节点的路径都包含数量相同的黑色节点
  • 如果一个节点存在黑色节点，那么该节点肯定有两个子节点

红黑树并不是一个完美平衡二叉查找树，从上图可以看到，根结点P的左子树显然比右子树高，但左子树和右子树的黑结点的层数是相等的，也即任意一个结点到到每个叶子结点的路径都包含数量相同的黑结点(性质5)。所以我们叫红黑树这种平衡为黑色完美平衡。

约定

• 当前节点
  • 正在处理（遍历）的节点
• 兄弟节点
  • 当前节点的父节的另一个子节点
• 父节点
  • 当前节点的父亲
• 祖父节点
  • 当前节点的父亲几点的父亲

操作

左旋

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

右旋

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

变色

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

综合

我们先忽略颜色，可以看到旋转操作不会影响旋转结点的父结点，父结点以上的结构还是保持不变的。

左旋只影响旋转结点和其右子树的结构，把右子树的结点往左子树挪了

右旋只影响旋转结点和其左子树的结构，把左子树的结点往右子树挪了

查找

因为红黑树是一颗二叉平衡树，并且查找不会破坏树的平衡，所以查找跟二叉平衡树的查找无异：

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

插入后自平衡

插入位置已经找到，把插入结点放到正确的位置就可以啦，但插入结点是应该是什么颜色呢？答案是红色。理由很简单，红色在父结点（如果存在）为黑色结点时，红黑树的黑色平衡没被破坏，不需要做自平衡操作。但如果插入结点是黑色，那么插入位置所在的子树黑色结点总是多1，必须做自平衡

插入情况