【C++】--红黑树的概念和实现

前言：

在计算机科学的浩瀚领域中，数据结构是构建高效算法的基石，而树结构因其出色的层次性和查找效率，成为处理动态数据集合的核心选择。二叉搜索树作为基础的树结构，虽能实现快速的插入、删除与查找操作，但在极端情况下（如数据有序插入）会退化为线性结构，导致时间复杂度骤升至O(n)，难以满足大规模数据处理的性能需求。为解决这一痛点，平衡二叉树应运而生，而红黑树作为平衡二叉树的经典实现之一，凭借其精妙的着色规则与旋转机制，在保证树结构相对平衡的同时，将各项操作的时间复杂度稳定在O(log n)，成为众多底层系统的优选数据结构。

从C++ STL中的set、map容器实现，到Linux内核的进程调度，再到数据库的索引模块，红黑树的身影无处不在。它既兼顾了平衡二叉树的高效性能，又通过简化的平衡维护规则，降低了实现难度，实现了性能与复杂度的优雅平衡。然而，红黑树的着色规则、旋转策略以及平衡维护逻辑，对初学者而言往往具有一定的理解门槛，尤其在C++手动实现场景中，容易在复杂的节点操作与指针管理中陷入困惑。

本文旨在打破这种认知壁垒，从红黑树的基本定义与核心性质出发，逐步拆解其插入操作中的平衡维护机制，深入剖析旋转操作的原理与应用场景，并结合实例帮助读者直观理解各项规则的设计初衷。无论你是刚接触平衡二叉树的初学者，还是希望夯实底层基础的开发人员，相信通过本文的系统梳理，都能对红黑树形成清晰、完整的认知，进而掌握这一高效数据结构的核心逻辑与应用价值。接下来，就让我们一同走进红黑树的世界，探寻其平衡之美的底层密码。

一、红黑树的概念

1、概念

红黑树和前面我们学习的AVL树一样也是一种自平衡二叉搜索树，其每个结点会额外再带一个代表颜色的数据，然后其通过控制结点的颜色来对我们的树结构进行控制，使高度近似平衡，从而保持我们的插入、查找、删除操作的时间复杂度稳定在O(logN)。

如上图就是我们的红黑树了。

2、规则

• 每个结点不是红色就是黑色
• 根结点是黑色的
• 如果一个节点是红色的，则它的两个孩子节点 必须是黑色的
• 每个节点到其NULL节点的简单路径上，均包含相同数量的黑色节点

那么对于上面的四个规则我们如何理解呢？

1、红黑树中每个节点都有颜色的属性，且只又红和黑两种，不会出现其他的。

2、整棵树的根节点必须是黑色的

3、不能出现连续的两个红色的节点

4、简单路径：不重复经过节点的路径。

3、红黑树控制平衡结构的原理

前面我们的AVL树是通过控制左右子树之间的高度差，然后控制树的平衡的，那么我们的红黑树是如何通过控制节点之间的颜色，然后达到控制树的平衡的呢？

首先由规则4，我们可以得知，从根节点到NULL节点的每条路径都有相同的黑色节点，所以极端情况下，最短路径就是全是黑色节点的情况，那么我们设最短路径长度为bh。

然后由规则2和规则3可知，任意一条路径都不会有连续的红色节点，那么极端情况下，最长路径就是一黑一红的情况，那么最长路径就是2hb的情况了。

那么结合上面的情况，我们假设任意一个从根节点到NULL的简单路径的长度为x，那么x的长度就在hb和2hb之间。

例如下面这种情况：

我们从根节点到NULL节点的任意一条简单路径都满足上面的要求。

4、红黑树的效率

假设N是红黑树中节点的数量，h是最短路径的长度，那么2^h-1<=N<2^2*h-1，那么由此可以推出h约等于logN，那么最长路径为2*logN，所以红黑树的时间复杂度还是为O(logN)。

那么红黑树和AVL树之间有啥不一样的呢？

红黑树的表达要比AVL树要抽象很多，AVL树通过控制高度差更加直观的控制了树的平衡。而红黑树通过4条规则来控制，间接的使得树平衡，其两个的时间效率是一样的，但是对于数据的插入来说，插入相同数量的节点，红黑树的旋转次数要少一点，其对于平衡的控制就没有这么的严格。

二、 红黑树的实现

1、红黑树的节点结构

其结构和AVL树的结构差不多，就是其不需要平衡因子了，然后要加一个颜色，然后颜色中我们使用一个枚举，枚举中为红色和黑色。

上面就是我们的节点结构，可以发现我们对于节点的颜色的初始化默认是Red，至于为啥我们后面来看。

2、insert红黑树的插入

红黑树节点的插入的位置，其和二叉搜索树的插入是一样的，所以我们不进行详细讲解了。

然后当树初始为空的时候，那么插入的节点就为根节点，然后要注意的是将根节点的颜色变为黑的。

下面就是其他位置进行插入：

那么我们插入一个节点后，要如何保持树的平衡呢？

要是非空树插入，那么新增节点必须是红色的，这是因为非空树插入，那么新增节点要是为黑色的话，就违反了规则4。、

然后要是父亲节点是黑色的话，那么就不会违反规则，此时插入就可以结束了。

要是父亲节点是红色的，那么此时就违反了规则3，那么就要进一步分析了，新插入节点cur是红，然后父亲节点parent是红的，然后父亲节点的父亲节点是黑色的，那么就是父亲节点的兄弟节点还没定。

根据父亲节点的兄弟的情况分为下面几种情况进行处理：

情况1：uncle存在且是红色的

这种情况就是uncle存在且为红色，那么我们如何进行调整呢？

首先就是我们将爷爷节点变成红，然后父亲节点和uncle节点都变黑，那么两个子树的简单路径的黑色节点数量都没变，满足规则4。然后我们此时调整还没完成，要防止出现连续的两个红色节点呢，那么我们继续向上调整，检查到我们的爷爷节点变成红色，会不会和爷爷节点的父亲节点形成连续的红色节点，要是没有，也就是爷爷节点的父亲节点是黑色的，那么我们的调整就可以结束了。

代码如下：

情况2：uncle存在且为黑或者uncle不存在

上面这种情况就是使用我们的单旋+变色处理，

然后要是插入在a这个位置，那么我们就需要进行双旋+变色处理了。

代码如下：

完整的插入代码：

bool Insert(const pair<K, V>& kv) { //树为空，直接为根节点，颜色要变为黑 if (_root==nullptr) { _root = new Node(kv); _root->_co = Black; return true; } //树不为空，找到合适位置插入 Node* cur = _root; Node* parent = nullptr; while (cur) { parent = cur; if (cur->_kv.first>kv.first) { cur = cur->_left; } else if (cur->_kv.first < kv.first) { cur = cur->_roght; } else { //不支持相同数据插入 return false; } } //循环结束，将新增结点和树进行链接 cur = new Node(kv); if (parent->_kv.first<kv.first) { parent->_right = cur; } else { parent->_left = cur; } cur->_parent = parent; while (parent && parent->_co == Red) { Node* grandfather = parent->_parent; if (grandfather->_left==parent) { Node* uncle = grandfather->_right; //叔叔存在且为红 if (uncle&&uncle->_co==Red) { parent->_co = Black; uncle->_co = Black; grandfather->_co = Red; cur = grandfather; parent = cur->_parent; grandfather = parent->_parent; } else // 叔叔不存在，或者叔叔存在且为黑->旋转+变色 { 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 // grandfather->_right == parent { // 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->_co = Black; return true; }

下面是在红黑树中的旋转代码，其和AVL树都是一样的，就是不需要对平衡因子进行修改。

代码如下：

void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; if (subLR) subLR->_parent = parent; Node* parentParent = parent->_parent; subL->_right = parent; parent->_parent = subL; if (parent == _root) { _root = subL; subL->_parent = nullptr; } else { if (parentParent->_left == parent) { parentParent->_left = subL; } else { parentParent->_right = subL; } subL->_parent = parentParent; } } void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL; if (subRL) subRL->_parent = parent; Node* parentParent = parent->_parent; subR->_left = parent; parent->_parent = subR; if (parent == _root) { _root = subR; subR->_parent = nullptr; } else { if (parentParent->_left == parent) { parentParent->_left = subR; } else { parentParent->_right = subR; } subR->_parent = parentParent; } }

3、红黑树的判断

那么我们如何判断一棵树符合红黑树的结构呢？

我们可以看红黑树的规则，首先就是要保证根节点是黑色节点，那么我们可以判断当前根节点是否为红色，要是红色的，那么我们就直接返回false。

为啥不去判断其是否为黑色呢？

这是因为我们还要规则3和规则4要符合。

然后我们再去判断规则3，其是否存在连续的两个红色节点，要是存在，那么就也是返回false。

最后我们再去判断规则4，我们可以遍历整个树，然后使用容器，将到每个NULL节点的黑色节点数量使用容器记录下来，比如我们可以使用set容器，然后要是容器中不止一个数据，那么我们的树结构就不符合，这个方式简单，就是效率不是很高，那么我们还可以先记录一个路径的黑色节点数量，然后再将这个数据和任意路径的黑色节点数量进行比较，看看其是否相等。

代码如下：

4、红黑树的前序遍历

这个和我们前面学习二叉树是一样的。

代码如下：

5、查找find

这个和二叉搜索树是一样的

代码如下：

三、完整代码

#pragma once #include<iostream> using namespace std; //枚举 enum color { Red, Black }; //红黑树节点 template<class K,class V> struct BRNode { BRNode(const pair<K,V>kv) :_kv(kv), _parent(nullptr), _left(nullptr), _right(nullptr), _co(Red) { } pair<K, V> _kv; BRNode<K, V>* _parent; BRNode<K, V>* _left; BRNode<K, V>* _right; enum color _co; }; template<class K,class V> class RBTree { typedef BRNode<K, V>* Node; public: bool Insert(const pair<K, V>& kv) { //树为空，直接为根节点，颜色要变为黑 if (_root==nullptr) { _root = new Node(kv); _root->_co = Black; return true; } //树不为空，找到合适位置插入 Node* cur = _root; Node* parent = nullptr; while (cur) { parent = cur; if (cur->_kv.first>kv.first) { cur = cur->_left; } else if (cur->_kv.first < kv.first) { cur = cur->_roght; } else { //不支持相同数据插入 return false; } } //循环结束，将新增结点和树进行链接 cur = new Node(kv); if (parent->_kv.first<kv.first) { parent->_right = cur; } else { parent->_left = cur; } cur->_parent = parent; while (parent && parent->_co == Red) { Node* grandfather = parent->_parent; if (grandfather->_left==parent) { Node* uncle = grandfather->_right; //叔叔存在且为红 if (uncle&&uncle->_co==Red) { parent->_co = Black; uncle->_co = Black; grandfather->_co = Red; cur = grandfather; parent = cur->_parent; grandfather = parent->_parent; } else // 叔叔不存在，或者叔叔存在且为黑->旋转+变色 { 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 // grandfather->_right == parent { // 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->_co = Black; return true; } bool IsBalance() { if (_root == nullptr) return true; if (_root->_col == RED) return false; // 黑色节点数量参考值 Node* leftMost = _root; int blackRef = 0; while (leftMost) { if (leftMost->_col == BLACK) ++blackRef; leftMost = leftMost->_left; } return Check(_root, 0, blackRef); } void InOrder() { _InOrder(_root); cout << endl; } 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; } private: void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; if (subLR) subLR->_parent = parent; Node* parentParent = parent->_parent; subL->_right = parent; parent->_parent = subL; if (parent == _root) { _root = subL; subL->_parent = nullptr; } else { if (parentParent->_left == parent) { parentParent->_left = subL; } else { parentParent->_right = subL; } subL->_parent = parentParent; } } void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL; if (subRL) subRL->_parent = parent; Node* parentParent = parent->_parent; subR->_left = parent; parent->_parent = subR; if (parent == _root) { _root = subR; subR->_parent = nullptr; } else { if (parentParent->_left == parent) { parentParent->_left = subR; } else { parentParent->_right = subR; } subR->_parent = parentParent; } } bool Check(Node* cur, int blackNum, const int blackNumRef) { if (cur == nullptr) { if (blackNum != blackNumRef) { cout << "黑色节点的数量不相等" << endl; return false; } return true; } if (cur->_col == RED && cur->_parent && cur->_parent->_col == RED) { cout << cur->_kv.first << "->" << "连续的红色节点" << endl; return false; } if (cur->_col == BLACK) ++blackNum; return Check(cur->_left, blackNum, blackNumRef) && Check(cur->_right, blackNum, blackNumRef); } void _InOrder(Node* root) { if (root == nullptr) return; _InOrder(root->_left); cout << root->_kv.first << " "; _InOrder(root->_right); } private: Node* _root=nullptr; };