红黑树的实现

目录

红黑树的概念

红黑树的规则

红黑树的效率

红黑树的实现

红黑树的插入

情况1：变色

情况2：单旋+变色

情况2：双旋+变色

为什么这三种情况能覆盖所有插入场景？

步骤 1：确定基础前提（插入前树是合法的）

步骤 2：按u的颜色划分第一层级场景

步骤 3：证明无遗漏场景

补充：向上迭代的终止条件（保证调整最终完成）

红黑树的插⼊代码实现

红黑树的查找

红黑树的验证

红黑树的概念

红黑树是⼀棵二叉搜索树，他的每个结点增加⼀个存储位来表示结点的颜色，可以是红色或者黑色。 通过对任何⼀条从根到叶子的路径上各个结点的颜色进行约束，红黑树确保没有⼀条路径会比其他路径长出2倍，因而是接近平衡的。

红黑树的规则

1. 树中每一个节点的颜色，要么是红色，要么是黑色。
2. 树的根节点必须是黑色。
3. 如果一个节点是红色，那么它的两个子节点必须都是黑色，即树中不存在连续的红色节点。
4. 从任意一个节点出发，到它所有的空（NULL）子节点的简单路径上，包含的黑色节点数量都相同。

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

• 根据红黑树的规则 4 可以推出：从根节点到任意空（NULL）节点的路径，包含的黑色节点数量都是相同的。因此在极端情况下，最短路径就是全部由黑色节点构成的路径，我们将这个最短路径的长度记为bh（即黑高）。
• 结合规则 2（根节点为黑色）和规则 3（不存在连续的红色节点）可以推出：极端情况下，最长路径会由黑色节点和红色节点交替组成，这条最长路径的长度就是2*bh。
• 需要注意的是，这种全黑的最短路径、以及一黑一红交替的最长路径，并不是每一棵红黑树都会同时存在的。如果设从根节点到任意空节点的某条路径长度为x，那么路径长度x会满足这样的范围：bh ≤ x ≤ 2*bh

红黑树的效率

假设红黑树的节点总数为 N，最短路径的长度为 h（即黑高 bh），那么 h 约等于 logN。

红黑树中任意一条路径的长度都满足 h≤x≤2h，这意味着红黑树的增删查改操作，最坏情况下也只需要遍历最长路径，对应的时间复杂度为 O(logN)。从节点数量的范围来看，满足 2h−1≤N<22h−1，由此也能推导出红黑树的时间复杂度为 O(logN)。

红黑树的平衡逻辑相比 AVL 树要更抽象一些：AVL 树是通过严格控制左右子树的高度差来直接维持平衡；而红黑树则是通过四条颜色规则的约束，间接实现近似平衡。两者的时间复杂度处于同一档次，但在插入相同数量的节点时，红黑树的旋转次数更少 —— 因为它对平衡的要求没有 AVL 树那么严格。

红黑树的实现

// 枚举值表示颜色 enum Colour { RED, BLACK }; 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. 若插入前树非空，新增节点的颜色必须设为红色。这是因为如果设为黑色，会直接破坏红黑树的规则 4（任意节点到其 NULL 子节点的路径上黑节点数量相同），而规则 4 的维护成本极高。
3. 非空树插入红色新节点后，分两种情况判断：
   • 若新节点的父节点颜色为黑色，此时没有违反任何红黑树规则，插入操作直接结束。
   • 若新节点的父节点颜色为红色，则违反了规则 3（不存在连续的红色节点）。此时可以确定三个节点的颜色：新节点c（cur）为红、父节点p（parent）为红、祖父节点g（grandfather）必为黑。后续的调整策略，关键取决于父节点的兄弟节点u（uncle）的颜色，需要分情况处理。

情况1：变色

触发条件（核心是 “叔叔节点 u 为红”）

当新增节点c为红色、父节点p为红色、祖父节点g为黑色，且叔叔节点u存在且为红色时，调整规则如下：

1. 变色操作：将父节点p和叔叔节点u的颜色改为黑色，将祖父节点g的颜色改为红色。
2. 向上迭代检查：把祖父节点g当作新的当前节点c，继续向上层（g的父节点、祖父节点层级）检查是否违反红黑树规则。

调整逻辑分析：

• 原本p和u是红色、g是黑色，将p和u变黑后，g左右子树的路径上各增加了一个黑色节点；再将g变红，整体上保证了g所在子树的所有路径的黑色节点数量不变。
• 这一步同时解决了c和p连续红色的问题，但因为g被改为红色，需要继续向上检查：
  • 如果g的父节点是黑色，调整结束；
  • 如果g的父节点是红色，则重复上述或其他对应情况的调整流程；
  • 如果g已经是整棵树的根节点，直接将g改回黑色即可。

注意：这种情况只需要变色，不需要旋转，无论c是p的左孩子还是右孩子，也无论p是g的左孩子还是右孩子，处理方式完全相同。

图0

图1

图2

跟AVL树类似，图0我们展示了⼀种具体情况，但是实际中需要这样处理的有很多种情况。

图1将以上类似的处理进行了抽象表达，d/e/f代表每条路径拥有hb个黑色结点的子树，a/b代表每 条路径拥有hb-1个黑色结点的根为红的子树，hb>=0。

图2，展示了hb==3的具体情况组合分析，当hb等于2时，这里组合情况上百亿种，这些样例是帮助我们理解，不论情况多少种，多么复杂，处理方式⼀样的，变色再继续往上处理即可，所以我们只需要看抽象图即可。

情况2：单旋+变色

触发条件（核心是 “叔叔节点 u 为黑 / 不存在，且 c 与 p 同方向”）

当新增节点c为红色、父节点p为红色、祖父节点g为黑色，且叔叔节点u不存在，或存在但为黑色时，需先明确节点背景：

• 若u不存在：c是刚插入的新节点；
• 若u存在且为黑色：c不是新节点，它原本是黑色，是因为其下方子树插入节点后，经过 “情况 1（变色）” 调整，才被改为红色并向上更新到当前层级的。如下图

这种场景下，仅靠变色无法解决问题（会破坏黑节点数量平衡），必须结合旋转 + 变色处理，分两种子情况：

g

p u

c

子情况 1：p是g的左孩子，c是p的左孩子

1. 旋转操作：以祖父节点g为旋转点，执行右单旋；
2. 变色操作：将父节点p改为黑色，将祖父节点g改为红色；
3. 调整后，p成为这棵子树的新根。此时子树的黑节点数量保持不变，也不存在连续红色节点，且无需向上更新（因为新根p的父节点无论颜色，都不会违反红黑树规则）。

g

u p

c

子情况 2：p是g的右孩子，c是p的右孩子

1. 旋转操作：以祖父节点g为旋转点，执行左单旋；
2. 变色操作：将父节点p改为黑色，将祖父节点g改为红色；
3. 调整后，p成为这棵子树的新根。同样，子树的黑节点数量、红节点连续性都符合规则，无需向上更新。

情况2：双旋+变色

触发条件（核心是 “叔叔节点 u 为黑 / 不存在，且 c 与 p 反方向”）

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

分析：p 必须变黑，才能解决，连续红色结点的问题，u 不存在或者是黑色的，这里单纯的变色无法解决问题，需要旋转 + 变色。

g

p u

c

如果 p 是 g 的左，c 是 p 的右，那么先以 p 为旋转点进行左单旋，再以 g 为旋转点进行右单旋，再把 c 变黑，g 变红即可。c 变成了这颗树新的根，这样子树黑色结点的数量不变，没有连续的红色结点了，且不需要往上更新，因为 c 的父亲是黑色还是红色或者空都不违反规则。（图3）

g

u p

c

如果 p 是 g 的右，c 是 p 的左，那么先以 p 为旋转点进行右单旋，再以 g 为旋转点进行左单旋，再把 c 变黑，g 变红即可。c 变成了这颗树新的根，这样子树黑色结点的数量不变，没有连续的红色结点了，且不需要往上更新，因为 c 的父亲是黑色还是红色或者空都不违反规则。

图3

为什么这三种情况能覆盖所有插入场景？

插入新节点后，仅可能出现连续红节点的违规（因为新节点为红色，其他规则均未被破坏），而连续红节点的根源是c（红）→ p（红），我们可以通过穷举所有可能的场景，证明这三种情况已覆盖全部可能性：

步骤 1：确定基础前提（插入前树是合法的）

插入前红黑树是合法的，因此：

• 若p为红色，则p的父节点g必为黑色（否则p与g已连续红，违反规则）；
• g必存在（若p是根节点，则p必为黑色，与p为红矛盾，因此p不可能是根，g一定存在）；
• 叔叔节点u是g的子节点，只有两种可能：红色或黑色（包括不存在，即 NIL）。

步骤 2：按u的颜色划分第一层级场景

场景 1：u为红色 → 触发 “只变色”

这是第一个明确的分支，无其他子情况（无论c是p的左 / 右孩子，p是g的左 / 右孩子，处理方式完全相同，因为u为红时，g的左右子树对称，变色后黑节点数量仍平衡）。

场景 2：u为黑色（含不存在） → 需进一步按位置划分

此时仅靠变色无法解决问题（若将p改为黑色，g的左子树黑节点数量会增加 1，而右子树（u为黑）数量不变，破坏黑节点平衡；若将g改为红色，又会引发上层连续红节点，且仍无法解决当前连续红节点问题），因此必须结合旋转，而旋转的方式由c与p、p与g的位置关系决定：

• 子场景 2.1：c与p同方向（左左 / 右右）→ 触发 “单旋 + 变色”；
• 子场景 2.2：c与p反方向（左右 / 右左）→ 触发 “双旋 + 变色”。

步骤 3：证明无遗漏场景

上述划分是互斥且穷尽的：

1. 互斥性：u的颜色只能是红或黑，位置关系只能是同方向或反方向，三种情况不会重叠；
2. 穷尽性：所有可能的违规场景都被包含在 “u为红”“u为黑且同方向”“u为黑且反方向” 中，无其他可能性。

补充：向上迭代的终止条件（保证调整最终完成）

在 “只变色” 的场景中，需要将g作为新的c向上检查，但这个过程不会无限循环，因为：

1. 若新的c（g）的父节点为黑色 → 无连续红节点，调整终止；
2. 若新的c是根节点 → 直接将其改为黑色（满足根为黑的规则），调整终止；
3. 若新的c的父节点为红色 → 重复上述三种情况的判断（此时新的c成为下一层的p，新的祖父节点为原g的父节点，叔叔节点为原g的兄弟节点），最终会收敛到根节点或黑色父节点。

红黑树的插⼊代码实现

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 (grandfather->_left == parent) { // g // p u // Node* uncle = grandfather->_right; // uncle存在且为红 if (uncle && uncle->_col == RED) { // 变色 parent->_col = uncle->_col = BLACK; grandfather->_col = RED; // 继续往上处理 cur = grandfather; parent = cur->_parent; } else // uncle不存在，或者存在且为黑 { if (cur == parent->_left) { // 旋转+变色 // g // p u //c RotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else { // 旋转+变色 // g // p u // c RotateL(parent); RotateR(grandfather); cur->_col = BLACK; grandfather->_col = RED; } break; } } else { // g // u p Node* uncle = grandfather->_left; // 叔叔存在且为红，->变色即可 if (uncle && uncle->_col == RED) { parent->_col = uncle->_col = BLACK; grandfather->_col = RED; // 继续往上处理 cur = grandfather; parent = cur->_parent; } else // 叔叔不存在，或者存在且为黑 { // 情况二：叔叔不存在或者存在且为黑 // 旋转+变色 // g // u p // c if (cur == parent->_right) { RotateL(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else { // g // u p // c 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; }

红黑树的验证

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

1. 规则 1 枚举颜色类型，天然实现保证了颜色不是黑色就是红色。
2. 规则 2 直接检查根即可
3. 规则 3 前序遍历检查，遇到红色结点查孩子不太方便，因为孩子有两个，且不一定存在，反过来检查父亲的颜色就方便多了。
4. 规则 4 前序遍历，遍历过程中用形参记录根到当前结点的 blackNum (黑色结点数量)，前序遍历遇到黑色结点就 ++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); }