红黑树

首先要理解二叉查找树

二叉查找树（BST）具备什么特性呢？

1. 左子树上所有结点的值均小于或等于它的根结点的值。

2. 右子树上所有结点的值均大于或等于它的根结点的值。

3. 左、右子树也分别为二叉排序树。

• 二叉查找树是二分查找的思想，查找所需的最大次数等同于二叉树的高度。
• 在插入节点的时候也是利用类似的方法，一层一层比较大小，找到合适的插入位置。
• 如右图，这样虽然满足了二叉查找树的条件，但是这个是瘸腿的二叉查找树，就和链表没有区别了。这是二叉查找树的缺点

• 解决二叉查找树多次插入新节点而导致的不平衡的方法，就是使用红黑树。
• 红黑树是一种自平衡的二叉查找树。除了符合二叉查找树的基本特性外，还具有下列的附加特性：
  1. 节点是红色或黑色。
  2. 根节点是黑色。
  3. 每个叶子节点都是黑色的空节点（NIL节点）。
  4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
  5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

• 上面一系列的规则，保证了红黑树的自平衡。红黑树从根到叶子的最长路径不会超过最短路径的2倍
• 当插入或删除节点的时候，红黑树的规则有可能被打破，这个时候需要进行调整来维持红黑树的规则。

如下图，如果向原红黑树插入值为21的新节点，由于父节点22是红色节点，因此这种情况打破了红黑树的规则4（每个红色节点的两个子节点都是黑色），必须进行调整，使之重新符合红黑树的规则。

• 调整的方法有两种：
  1. 变色：红变黑，黑变红
  2. 旋转：左旋转和右旋转

变换规则

• 旋转和颜色变换规则：所有插入的点默认为红色

1. 变颜色的情况：当前结点的父亲是红色，且它的祖父结点的另一个子结点也是红色（叔叔结点）：

   （1）把父节点设为黑色

   （2）把叔叔也设为黑色

   （3）把祖父也就是父亲的父亲设为红色（爷爷）

   （4）把指针定义到祖父结点设为当前要操作的（爷爷）分析的点变换的规则

2. 左旋：当前父结点是红色，叔叔是黑色的时候，且当前的结点是右子树。左旋以父节点作为左旋

3. 右旋：当前父结点是红色，叔叔是黑色的时候，且当前的结点是左子树。右旋

   （1）把父节点变为黑色

   （2）把祖父结点变为红色（爷爷）

   （3）把祖父结点旋转（爷爷）

变色

为了重新符合红黑树的规则，尝试把红色节点变为黑色，或者把黑色节点变为红色。

• 下图所表示的是红黑树的一部分，需要注意节点25并非根节点。因为节点21和节点22连续出现了红色，不符合规则4，所以把节点22从红色变成黑色：

  

• 但这样并不算完，因为凭空多出的黑色节点打破了规则5，所以发生连锁反应，需要继续把节点25从黑色变成红色：

  

• 此时仍然没有结束，因为节点25和节点27又形成了两个连续的红色节点，需要继续把节点27从红色变成黑色：

  

左旋转

• 左旋转，就是将S点旋转到根节点，S节点的左边都挂到E节点的右边
• 就是将要旋转的子结点的左边挂到之前节点E的右边

右旋转

将要旋转的子结点的右边移到之前结点E的左边

举例说明

1. 首先我们要插入结点6，按照二叉查找树放在如下位置。

1. 我们发现结点6和结点7是红色的，不满足规则，下一步要判断是变色还是旋转

   当前结点的父亲是红色，且它的祖父结点的另一个子结点也是红色，我们要进行的是变色。把父节点和叔叔设为黑色，把祖父也就是父亲的父亲设为红色（爷爷）

   

2. 我们发现结点5和结点12还是不满足规则。变色是说父亲结点和叔叔结点都是红色。不满足，我们用旋转。结点12位于结点5的右子树上。用左旋。

   [图片上传失败...(image-b433f8-1585661664741)]

3. 对结点5还要进行右旋。

   （1）把父节点变为黑色

   （2）把祖父结点变为红色（爷爷）

   （3）以爷爷结点旋转

   

4. 以上。上面的红黑树就没有问题了