上文链接

• 【C++】AVL树（详解）

一、什么是红黑树

我们之前学习过了二叉搜索树和 AVL 树，红黑树和 AVL 树一样，也是一棵自平衡的二叉搜索树，AVL 树是通过控制左右子树的高度差不超过 1 来保持平衡，而红黑树则是为每个结点增加一个存储位来表示结点的颜色，可以是红色或者黑色。 通过对任何一条从根到叶子的路径上各个结点的颜色进行约束来保持树的左右两边的相对平衡。红黑树确保没有一条路径会比其他路径长出 2 倍，即 2 * 最短路径 >= 最长路径，因而是接近平衡的。

如下图所示就是一棵红黑树：

---

二、红黑树的性质

1. 颜色规则

红黑树为何能够确保没有一条路径会比其他路径长出 2 倍呢？是因为它有如下四个规则：

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

说明：《算法导论》等书籍上补充了一条每个叶子结点 (NIL) 都是黑色的规则。他这里所指的叶子结点不是传统的意义上的叶子结点，而是我们说的空结点，有些书籍上也把 NIL 叫做外部结点。NIL 是为了方便准确的标识出所有路径，《算法导论》在后续讲解实现的细节中也忽略了 NIL 结点，所以我们知道一下这个概念即可。

有了上面的描述，我们可以总结出红黑树的性质：

• 左根右：由于它是二叉搜索树，所以左子树的值 < 根 < 右子树的值；
• 根叶黑：根节点和叶子节点 (NIL) 都是黑色的；
• 不红红：一条路径上不会出现两个连续的红色节点；
• 黑路同：任意两条路径上的黑色节点个数相同。

因此，红黑树的性质可以简记为：左根右，根叶黑，不红红，黑路同。

---

2. 红黑树的规则为什么可以控制平衡

为什么有了上面四条规则就可以确保红黑树中没有一条路径会比其他路径长出 2 倍呢？

由黑路同可知，从根到空结点的每条路径都有相同数量的黑色结点，所以极端场景下，最短路径就是全为黑色结点的路径，假设最短路径长度为 h。

又由不红红可知，任意一条路径不会有连续的红色结点，所以极端场景下，最长的路径就是一黑一红间隔组成，那么最长路径的长度就为 2 * h。

综上所述，在最极端的情况下，红黑树中的最长路径也才刚好是最短路径的两倍，所以对于任意一棵红黑树来说 2 * 最短路径 >= 最长路径，因此没有一条路径会比其他路径长出 2 倍。

---

3. 红黑树的效率

红
黑树与 AVL 树的增删查改的效率都是在同一个档次，时间复杂度都是 $O(\log N)$。

在插入和删除方面，由于 AVL 树的平衡条件相对严格一些，因此需要频繁地进行旋转操作，效率比红黑树略低；

在查找方面，红黑树不像 AVL 树那样保持严格的平衡，因此在查找时的效率会比 AVL 树略低。

---

三、红黑树的整体结构

#pragma once
// 枚举值表示颜色 
enum Colour
{RED,BLACK
};// 这里我们默认按 key-value 结构实现
template<class K, class V>
struct RBTreeNode
{// 这里更新控制平衡也要加入 parent 指针 pair<K, V> _kv;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Colour _col;RBTreeNode(const pair<K, V>& kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr){}
};template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:// ...private:Node* _root = nullptr;
};

---

四、红黑树的插入

1. 空树的插入

当我们对一棵空的红黑树进行插入时，直接插入并把其颜色设置为黑色即可。

（下面所讨论的插入操作都是建立在树非空的情况之上）

---

2. 插入节点的父亲为黑色

首先我们需要明确一点，在红黑树非空的情况下，我们插入一个节点的颜色必定是红色。

这是因为如果我们把插入节点的颜色设置为黑色的话，那么此时这棵红黑树就必然会违反黑路同的性质，之后想要把每条路上的黑色节点数量调整为一样多的话就会非常麻烦。所以从这个角度来看，树非空的情况下我们插入的节点都设置为红色。

此时如果它的父亲是黑色，那么将不会违反红黑树的任何一条性质，那么插入结束。

---

3. 插入节点的父亲为红色

(1) 叔叔为红色：变色

我们插入的节点为红色，此时如果它的父亲也为红色，那么就会违反不红红的性质，那么此时必然我们会让父亲变为黑色，但这也意味着父亲这条路上多了一个黑色节点，违反了黑路同，我们需要调节黑色节点的数量。此时我们可以让父亲的父亲 (爷爷) 变为红色 (由于父亲为红，所以爷爷变之前必然为黑)，再让叔叔节点变为黑色，这样一来，我们就可以满足不红红和黑路同两个性质了。

但是，此时由于爷爷变红，可能又会导致出现两个红色节点相邻的情况，因为爷爷的父亲可能为红色。此时我们只需要把爷爷当作新插入的节点，重复上面的操作即可。下面是图片演示：

注：下图中用 c (cur) 表示插入节点，用 p (parent) 表示父节点，用 g (grandparent) 表示爷爷节点，用 u (uncle) 表示叔叔节点。

一直重复这样的操作，直到不违反红黑树的性质或者到根为止。注意到根的时候需要把根变为黑色。

---

(2) 叔叔为空或为黑色：旋转 + 变色

① LL 型：右单旋 + 变色

父亲节点为红色，叔叔节点为空或为黑色时，我们需要先进行旋转操作。注意前面我们说过空节点 (NIL) 一定是黑色，所以为空或者为黑色其实是一种情况。具体怎么旋转呢？

如果此时插入节点的父亲节点在爷爷节点的左边 (left)，插入节点在父亲节点的左边 (left)，那么我们把这种情况成为 LL 型。如果是 LL 型，那么需要将以爷爷节点为根的子树进行右单旋操作，旋转之后将爷爷和父亲节点进行变色 (红变黑，黑变红)。这样操作之后，将不会违反红黑树的性质，插入结束。

这种旋转 + 变色的操作不仅会出现在单纯的插入过程中，也有可能出现在我们上面讲的情况 (1) 的过程中。即在情况 (1) 的向上变色更新过程中发现 cur 的叔叔颜色为黑就需要进行旋转 + 变色。

---

② RR 型：左单旋 + 变色

如果此时插入节点的父亲节点在爷爷节点的右边 (right)，插入节点在父亲节点的右边 (right)，那么我们把这种情况成为 RR 型。如果是 RR 型，那么需要将以爷爷节点为根的子树进行左单旋操作，旋转之后将爷爷和父亲节点进行变色 (红变黑，黑变红)。这样操作之后，将不会违反红黑树的性质，插入结束。

可以看到这种情况与上面的 LL 型几乎一样，就是一个对称的关系，这里就不画图演示了。

---

③ LR 型：左右双旋 + 变色

如果此时插入节点的父亲节点在爷爷节点的左边 (left)，插入节点在父亲节点的右边 (right)，那么我们把这种情况成为 LR 型。如果是 LR 型，那么需要将以爷爷节点为根的子树进行左右双旋操作，旋转之后将 cur 和爷爷节点进行变色，插入结束。

---

④ RL 型：右左双旋 + 变色

如果此时插入节点的父亲节点在爷爷节点的右边 (right)，插入节点在父亲节点的左边 (left)，那么我们把这种情况成为 RL 型。如果是 RL 型，那么需要将以爷爷节点为根的子树进行右左双旋操作，旋转之后将 cur 和爷爷节点进行变色，插入结束。

这种情况与 LR 型完全对称。

---

4. 代码部分

// 旋转代码的实现跟 AVL 树非常类似的，只是不需要更新平衡因子
bool Insert(const pair<K, V>& kv)
{// 如果是空树那么直接让插入节点变为黑if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}Node* parent = nullptr;Node* cur = _root;// 走正常二叉搜索树的插入逻辑，找到插入位置while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else return false;}cur = new Node(kv);// 新增结点颜色给红色 cur->_col = RED;if (parent->_kv.first < kv.first) parent->_right = cur;else parent->_left = cur;cur->_parent = parent;// 如果新增节点的父亲为红色，那么需要进行平衡调整// 直到调整到根或者父亲为黑色为止，因为判断条件有两个while (parent && parent->_col == RED){Node* grandfather = parent->_parent;// 如果此时父亲节点在爷爷节点的左边if (parent == grandfather->_left){Node* uncle = grandfather->_right;// 如果叔叔节点为红色，那么进行变色处理if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;  // 更新 cur 继续向上处理parent = cur->_parent;}// 如果叔叔为黑色或者为空，那么需要旋转 + 变色else{// 如果插入在父亲节点的左边，此时为 LL 型if (cur == parent->_left){// 右单旋 + 变色RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}// LR 型else{// 左右双旋 + 变色RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}// 旋转 + 变色操作完是一定符合红黑树的性质的，因此直接结束更新break;}}// 父亲节点在爷爷节点的右边else{Node* uncle = grandfather->_left;// 叔叔节点为红色，变色即可if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续往上处理 cur = grandfather;parent = cur->_parent;}// 叔叔为黑色或为空else{// RR 型if (cur == parent->_right){// 左单旋 + 变色RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}// RL 型else{// 右左双旋 + 变色RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}// 停止更新break;}}}// 变色更新到根节点时有可能根为红色，需要将根变为黑色_root->_col = BLACK;return true;
}

---

五、红黑树的查找与删除

红黑树的查找与正常二叉搜索树的查找逻辑一样。

Node* Find(const K& key)
{Node* cur = _root;while (cur){if (cur->_kv.first < key) cur = cur->_right;else if (cur->_kv.first > key) cur = cur->_left;else return cur;}return nullptr;
}

红黑树的删除操作这里不做重点讲解，这个操作会比插入稍复杂一些，具体操作可以参考《算法导论》或者《STL源码剖析》中的讲解。

---

六、红黑树的平衡验证

如何判断一棵红黑树是否合格呢？这里获取最长路径和最短路径，检查最长路径不超过最短路径的 2 倍是不可行的，因为就算满足这个条 件，红黑树也可能颜色不满足规则，当前暂时没出问题，后续继续插入还是会出问题的。所以我们还是去检查 4 点规则，满足这 4 点规则，一定能保证最长路径不超过最短路径的 2 倍。

1. 枚举颜色类型，保证颜色不是黑色就是红色；
2. 检查根的颜色是否为黑色即可；
3. 不红红：前序遍历检查，
   遇到红色结点查孩子是否是红色这样不太方便，因为孩子有两个，且不一定存在，但是反过来检查父亲的颜色就方便多了；
4. 黑路同：前序遍历，遍历过程中用形参记录根到当前节点路径的 blackNum (黑色结点数量)，前序遍历遇到黑色结点就 ++blackNum，走到空就计算出了一条路径的黑色结点数量。再用任意一条路径黑色结点数量作为参考值，依次比较即可。

bool Check(Node* root, int blackNum, const int refNum)
{if (root == nullptr){// 前序遍历走到空时，意味着一条路径走完了 //cout << blackNum << endl;if (refNum != blackNum){cout << "存在黑色结点的数量不相等的路径" << endl;return false;}return true;}// 检查孩子不太⽅便，因为孩子有两个，且不一定存在，反过来检查父亲就方便多了 if (root->_col == RED && root->_parent->_col == RED){cout << root->_kv.first << "存在连续的红色结点" << endl;return false;}if (root->_col == BLACK){blackNum++;}return Check(root->_left, blackNum, refNum)&& Check(root->_right, blackNum, refNum);
}bool IsBalance()
{if (_root == nullptr)return true;if (_root->_col == RED)return false;// 参考值 int refNum = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){++refNum;}cur = cur->_left;}return Check(_root, 0, refNum);
}