红黑树（Red-Black Tree）

一、概念

        红黑树（Red Black Tree）是一种自平衡的二叉搜索树，通过添加颜色信息来确保在进行插入和删除操作时，树的高度保持在对数级别，从而保证了查找、插入和删除操作的时间复杂度为 O(log n)。这种树可以很好地解决普通二叉搜索树可能退化为链表的问题。

        在此文中会时不时用红黑树和AVL树作类比，朋友们可以查阅了解AVL树相关内容：AVL 树-CSDN博客

        红黑树和AVL树有一些共同点：

                1.平衡二叉搜索树

                2.解决普通二叉搜索树在特殊情况退化为类似链表的问题

1.1红黑树的规则:

1. 每个结点不是红色就是黑色
2. 根结点是黑色的
3. 如果一个结点是红色的，则它的两个孩子结点必须是黑色的，也就是说任意一条路径不会有连续的红色结点。
4. 对于任意一个结点，从该结点到其所有NULL结点的简单路径上，均包含相同数量的黑色结点 

为了大家能更快的认识和理解红黑树，看看以下的树，都是红黑树结构：

上面4棵树均是符合黑红色树规则的树。

1.2 推理

        由上面4点规则推理：最长路径不超过最短路径的2倍

思考：红黑树如何确保最长路径不超过最短路径的2倍？

•         根据规则4，从根到NULL节点的每条路径都有相同数量的黑色节点。所以，在极端情况下，最短路径是全由黑色节点组成的路径，假设最短路径长度为bh（black height）。
•         根据规则2和规则3，任意一条路径不会有连续的红色节点。因此，极端情况下，最长的路径是由一黑一红交替组成的，那么最长路径的长度为2*bh。
•         结合红黑树的4点规则，理论上的全黑最短路径和一黑一红的最长路径并不会在每棵红黑树中都存在。假设任意一条从根到NULL节点的路径长度为x，那么bh ≤ h ≤ 2*bh。

说明

        《算法导论》等书籍补充了一条规则，即每个叶子节点（NIL）都是黑色的。这里所指的叶子节点不是传统意义上的叶子节点，而是我们所说的空节点。一些书籍中也把NIL称为外部节点。NIL的作用是方便准确地标识所有路径。《算法导论》在后续讲解实现细节时忽略了NIL节点，因此我们只需了解这个概念即可。

1.3 红黑树的效率

        假设N是红黑树中节点的数量，h是最短路径的长度，那么 2^h−1 ≤ N<2^2h−1 。由此推出 h ≈ log⁡N 。这意味着红黑树在增删查改操作中，最坏情况下也只是走最长路径 2log⁡N ，因此时间复杂度依然是 O(log⁡N) 。

        红黑树相对于AVL树表达更为抽象一些，AVL树通过高度差直接控制平衡。而红黑树通过四条颜色约束规则间接实现了近似平衡。虽然两者的效率同属一个档次，但在插入相同数量的节点时，红黑树的旋转次数更少，因为它对平衡的控制没那么严格。

 二、红黑树节点增加与查找

2.1 红黑树插入一个值的大概过程

1. 插入一个值：按二叉搜索树规则进行插入。插入后需要观察是否符合红黑树的4条规则。

2. 空树插入：

   • 新增结点是黑色结点。（根节点必须是黑色）

3. 非空树插入：

   • 新增结点必须是红色结点，因为插入黑色结点会破坏规则4（很难维护）。

   • 如果父亲结点是黑色的，则没有违反任何规则，插入结束。

   • 如果父亲结点是红色的，则违反规则2，进一步处理。

4. 处理违反规则3：

   • c是红色，p为红，g必为黑。

   • 关键看叔叔u的情况，需要根据u分为以下几种情况分别处理。

【说明】

        下图中假设我们把新增结点标识为 (curr)，c的父亲标识为 p(parent)，p的父亲标识为 g(grandfather)，p的兄弟标识为 u(uncle)。 

---

 情况1【变色】

• 初始状态：c为红，p为红，g为黑，u存在且为红。

• 操作：将p和u变黑，g变红。在g当做新的c，继续往上更新。

分析：

• 因为p和u都是红色，g是黑色。把p和u变黑，左边子树路径各增加一个黑色结点。

• g再变红，相当于保持g所在子树的黑色结点的数量不变，同时解决了c和p连续红色结点的问题。

• 需要继续往上更新是因为  1）g是红色。如果g的父亲还是红色，那么就还需要继续处理；2）如果g的父亲是黑色，则处理结束了；3）如果g就是整棵树的根，再把g变回黑色。

• 情况1只变色，不旋转。所以无论c是p的左还是右，p是g的左还是右，都是上面的变色处理方式。

【图解】 

 

---

可以把总的情况做成抽象图：

对照抽象图下面还有一个例子供给大家参考，可以更具象地理解向上更新的过程：

---

 情况2【单旋 + 变色】

• 初始状态:  c 为红，p 为红，g 为黑。u 不存在或者存在且为黑。

• 如果 u 不存在，则 c 一定是新增结点。如果 u 存在且为黑，则 c 一定不是新增结点，c 之前是黑色，是在 c 的子树中插入，符合情况1，变色将 c 从黑色变成红色，更新上来的。

如图：

分析：

• p 必须变黑，才能解决连续红色结点的问题。

• u 不存在或者是黑色的，这里单纯的变色无法解决问题，需要旋转 + 变色。

旋转 + 变色（操作）：

• 如果 p 是 g 的左，c 是 p 的左

1. 以 g 为旋转点进行右单旋。（和旋转的操作和搜索二叉树里的旋转是一样的）
2. 再把 p 变黑，g 变红即可。
3. p 变成这颗树新的根，这样子树黑色结点的数量不变，没有连续的红色结点，且不需要往上更新，因为 p 的父亲是黑色、红色或空都不违反规则。

• 如果 p 是 g 的右，c 是 p 的右

1. 以 g 为旋转点进行左单旋。

2. 再把 p 变黑，g 变红即可。

3. p 变成这颗树新的根，这样子树黑色结点的数量不变，没有连续的红色结点，且不需要往上更新，因为 p 的父亲是黑色、红色或空都不违反规则。

---

        （其实无论左边或右边操作都思路都是一种思路，这里通过文字描述给大家做参考，如果不太喜欢文字叙述可以直接看图解）

【图解】 （对应上面举例）

 情况3 【双旋 + 变色】

 初始状态：c 为红，p 为红，g 为黑，u 不存在或为黑色

 

条件分析：

       如果 u 不存在 或u 存在且为黑色（与需要单旋加变色的情况二相同）

【双旋＋变色】 与 【单旋＋变色】对比：

双旋转 + 变色（操作）：

  情况1：p 是 g 的左子节点，c 是 p 的右子节点（左-右双旋）

1. 以p为旋转点，左单旋 

2. 以g为旋转点，右单旋 

3. 变色：p 和 g 变红，将 c 变黑。

  情况2：p 是 g 的右子节点，c 是 p 的左子节点（右-左双旋）

1. 以p为旋转点，右单旋 

2. 以g为旋转点，左单旋 

3. 变色：p 和 g 变红，将 c 变黑。

        

【图解】 （对应上面举例） 

 抽象图讨论由子树更新上来的情况：

2.2红黑树节点查找

        红黑树的查找操作与普通的二叉搜索树的查找操作非常相似。

        都遵循相同的查找规则，即在每个节点比较查找键值和当前节点的键值，根据比较结果选择继续在左子树或右子树中查找。 

【步骤】 

1. 从根节点开始：查找从树的根节点开始。

2. 比较键值：将查找键与当前节点的键进行比较。

   • 如果查找键小于当前节点的键，则继续在左子树中查找。

   • 如果查找键大于当前节点的键，则继续在右子树中查找。

   • 如果查找键等于当前节点的键，则查找成功，返回该节点。