【数据结构进阶】红黑树超详解 + 实现（附源码）

🌟🌟作者主页：ephemerals__

🌟🌟所属专栏：数据结构

前言

一、红黑树介绍

二、红黑树原理详解

三、红黑树的实现

1. 节点定义

2. 红黑树类型定义及接口声明

3. 红黑树的插入（重点）

颜色设置

平衡调整

总代码

4. 红黑树的查找

5. 中序遍历、拷贝构造和析构

6. 检查红黑树是否合法

7. 程序全部代码

总结

前言

在传统二叉搜索树的基础上，我们学习了AVL树，它通过独特的平衡机制，确保了稳定高效的插入、查找和删除操作。然而，由于其频繁的平衡调整，可能使性能收到一定影响。因此，另一种自平衡二叉搜索树——红黑树应运而生。本篇文章，我们将深入探讨红黑树的实现原理，带你解开其简洁而深邃的设计之美。

与AVL树相同，之后的红黑树实现当中，我们会将键值对(pair)作为节点数据域。

如果你不是很了解二叉搜索树、AVL树或pair，可以参阅这两篇文章：

【数据结构】二叉搜索树（二叉排序树）-CSDN博客

【数据结构进阶】AVL树深度剖析 + 实现（附源码）-CSDN博客

注：若无特殊说明，本文所提到的所有“路径”都指根节点到NULL的路径。

一、红黑树介绍

红黑树（Red-Black-Tree）是一种自平衡二叉搜索树，但它并非像AVL树那样“严格平衡”，而是允许一定的不平衡存在，在保证增删查改效率没有太大影响的情况下，显著减少了平衡调整的次数，提升总体效率。

AVL树一般通过节点的“平衡因子”来维持平衡，而红黑树通过给节点“着色”，确保其高效性。

在非空情况下，红黑树的性质（约束条件）如下：

1. 它是一棵二叉搜索树

2. 每一个节点都会被着色，不是黑色就是红色

3. 根节点必须为黑色

4. 对于一个红色节点，它的孩子或为空，或是黑色。也就是说路径上不能有连续红色节点

5. 从根节点到NULL节点的所有路径上，黑色节点的数量都相同

有了以上约束条件，就可确保其没有一条路径长度能够超出其他路径的2倍，从而保证高效操作。

如上图，每一条路径上都有相同数量的黑色节点。

假设一棵红黑树的一条路径上有n个黑色节点，那么由于其所有路径上的黑色节点数量是相同的，所以其所有路径上都一定有n个黑色节点。对于这棵树，最长的可能路径上的节点就是一黑一红一黑一红（要确保无连续红色节点）......一共有2n个节点；最短的可能路径上的节点是全黑的，一共有n个节点。那么其他可能的路径长度都在n~2n之间。所以说没有一条路径长度能够超出其他路径长度的两倍，也就确保了根节点左右子树的高度比一定在1~2之间。

接下来，我们分析一下红黑树的效率。

设一棵红黑树一共有N个节点，它的最短可能路径的长度为h，由于可能的路径长度都在h~2h之间，那么节点数N就满足 $2^{h}-1\leq N\leq 2^{2h}-1$ 。由此可知，在路径最短情况下，其进行增删查改的时间消耗为O(logN)；路径最长情况下，进行查找的时间消耗为O(2logN)。因此红黑树增删查改的时间复杂度为O(logN)。

红黑树的平衡控制相对AVL树较为抽象，但由于那几点约束条件，控制了最长路径和最短路径之比，间接地使红黑树达到了“近似平衡”，增删查改地时间消耗不会过大，并且相比AVL树，旋转调整次数会更少。

三、红黑树的实现

1. 节点定义

红黑树节点及其颜色定义如下：

enum Color//枚举值表示颜色
{RED,BLACK
};//节点
template<class K, class V>
struct RBTreeNode
{pair<K, V> _kv;//数据域RBTreeNode<K, V>* _left;//指向左孩子的指针RBTreeNode<K, V>* _right;//指向右孩子的指针RBTreeNode<K, V>* _parent;//指向父亲的指针Color _col;//颜色RBTreeNode(const pair<K, V>& kv)//节点构造:_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr){}
};

与AVL树相同，红黑树也采用三叉链表结构，更有利于节点之间的控制访问。

在节点构造当中，我们并没有设置节点的初始颜色，之后在实现节点插入的实现当中，我们会重点讨论初始颜色的问题。

2. 红黑树类型定义及接口声明

我们需要实现的接口如下：

//红黑树类
template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public://强制生成无参构造RBTree() = default;//拷贝构造RBTree(const RBTree<K, V>& t);//析构函数~RBTree();//插入bool Insert(const pair<K, V>& kv);//查找Node* Find(const K& key);//中序遍历void Inorder();//判断是否为合法红黑树bool IsValidRBTree();
private:Node* _root = nullptr;//根节点指针
};

3. 红黑树的插入（重点）

为了保持红黑树增删查改的高效性，插入操作要保证满足红黑树的性质。

红黑树的插入过程大致如下：

1. 首先按照二叉搜索树的插入规则确定插入节点的位置。

2. 插入新节点，并确定新节点的颜色。

3. 为保持红黑树的性质，需要对原有树结构进行平衡调整。

颜色设置

我们首先来探讨新节点的颜色设置问题。

如果新插入的节点是根节点（树为空），毋庸置疑，为黑色。并且此时整个结构已经满足红黑树性质，插入完成。

如果新插入的节点不是根节点，那么能否设置初始颜色为黑色呢？我们假设新插入的节点为黑色：

不难发现，插入节点4之后，已经不满足红黑树性质：5->2->4->NULL这条路径上有3个黑色节点，而5->7->6->NULL这条路径上有2个黑色节点。实际上，如果插入黑色节点，不管插入到什么位置，该条路径上的黑色节点数都会增加，而其他路径上的黑色节点数不变，此时一定会违反红黑树的约束条件。

那么，我们插入一个红色节点：

此时可以看到，插入之后，整个结构依然满足红黑树的性质。当然，这是因为节点2是黑色节点，此时插入结束。若一个红色节点插入在红色节点的下方，出现连续红色节点，那么也会违反约束条件。

总之，若插入黑色节点，一定违反红黑树规则，而插入红色节点，可能违反红黑树规则。所以我们退而求其次，将新节点（除根节点外）设置为红色。

平衡调整

确定了新节点颜色之后，我们探讨平衡调整的问题。

之前已经提到，我们如果将新节点插入在红色节点的下方，就需要进行平衡调整。有两种情况需要分别讨论。

情况1：仅变色

如上图所示， parent和uncle都是红色，grandfather为黑色，此时插入新节点cur，出现连续红色节点。这种情况下，将parent和uncle变黑，grandfather变红，整个结构就满足了红黑树的性质。

但上图是一种具体情况，如果整棵树是另一棵树的子树，且节点4是红色的，那么变色之后就会再次出现连续的红色节点（节点2和节点4），此时就需要继续向上调整：将grandfather作为新的cur，然后找到新的parent和uncle，进行变色或做其他调整（之后会讲解），然后再向上检查，直到遇到根节点或者无连续红色节点为止。

通过观察上图，不难发现：针对需要进行平衡调整的情况，新节点插入之后，parent一定为红，否则无需调整；grandfather一定为黑，否则未插入节点时就已经出现连续红色节点，红黑树原本就有问题。那么，重要变量就是uncle节点。

总结：当uncle为红时，仅需变色：将parent和uncle变黑，grandfather变红。然后将grandfather作为新的cur，找到新的parent和uncle，继续判断、调整，直到遇到根节点或无连续红色节点。

情况2：旋转+变色

刚才提到uncle是重要变量，那么我们就给出uncle的其他可能情况（不存在或为黑），进而分析各种调整场景。

分类讨论之前，我们首先需要明确需要进行平衡调整的情况下，uncle和cur的关系。

一个节点被标记为cur（确定插入位置之后），仅有两种情况：

1. 它是新增节点；2. 它是场景1向上调整时标记的节点。

当uncle不存在时，cur一定是新增节点。原因：若cur不是新增节点，则其必然是向上调整时标记的节点，那么一定发生了变色，也就是说cur所在的某条路径A上至少有两个黑色节点（包括一个根节点）。而uncle不存在，则从根节点到uncle（NULL）位置的路径上的黑色节点数一定少于路径A，两条路径黑色节点数量不一致，不满足红黑树性质。

当uncle为黑时，cur一定时向上调整时标记的节点。原因：uncle为黑，则从根节点到uncle的路径B上至少有两个黑色节点。如果cur是新增节点，那么从根节点到cur的路径上的黑色节点数一定少于路径B，两条路径黑色节点数量不一致，不满足红黑树性质。

uncle不存在：

这种情况下，如果只是改变parent和grandfather的颜色，并不能解决问题：变色之后路径4->2->1->NULL上有1个黑色节点，而路径4->NULL上没有黑色节点，不满足红黑树性质。

此时就要配合旋转操作来解决问题。根据三个节点的相对位置，需要我们分情况进行单旋或双旋，从而调整树的结构：

单旋+变色：

可以看到，我们以grandfather为旋转点，进行右/左单旋，然后将parent变黑，grandfather变红，整个结构满足红黑树性质，并且该部分的根已经变成黑色，无需继续向上调整，插入结束。

双旋+变色：

双旋完成后，将cur变黑，grandfather变红，整个结构满足红黑树，并且该部分的根已经变成黑色，无需继续向上调整，插入结束。

总结：当uncle不存在时，需要根据实际情况进行旋转+变色。单旋完成后要将parent变黑，grandfather变红；双旋完成后要将cur变黑，grandfather变红。操作结束后，该部分的根成为黑色，不会出现连续红色节点，无需再向上调整。

uncle为黑：

刚才已经提到，uncle为黑时，cur一定是向上调整时标记的节点。所以我们使用抽象图来表示插入状况：

如图所示， a、b、c、d、e分别表示相应黑色节点数量的子树，当a、b的黑色节点数由n-1变为n时，说明发生了变色，使得cur变为红色。此时由于uncle是黑色，如果直接将parent变黑，grandfather变红，那么根节点到a、b、c路径上的黑色节点数与到d、e的路径不相等，不满足红黑树的性质。所以要以grandfather为旋转点，分情况进行旋转再变色。

不难发现，uncle为黑时的旋转、变色逻辑与uncle不存在时完全相同，这里博主就不再一一列举各种旋转情况。总结：当uncle为黑时，需要根据实际情况进行旋转+变色。单旋完成后要将parent变黑，grandfather变红；双旋完成后要将cur变黑，grandfather变红。操作结束后，该部分的根成为黑色，不会出现连续红色节点，无需再向上调整。

注意：平衡调整完成之后，整棵树的根节点可能变为红色。所以平衡调整结束后，一定要将根节点设置为黑色。

红黑树插入的总体过程：

总代码

红黑树插入代码实现：

//插入
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 (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(kv);cur->_col = RED;//插入红色节点if (kv.first < parent->_kv.first){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;//parent为红，进行平衡调整while (parent && parent->_col == RED){//确定grandfatherNode* grandfather = parent->_parent;if (parent == grandfather->_left){//确定uncleNode* uncle = grandfather->_right;if (uncle && uncle->_col == RED)//uncle为红，仅变色{parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续向上判断cur = grandfather;parent = cur->_parent;}else//uncle为黑或不存在，旋转+变色{if (cur == parent->_left)//右单旋{RotateR(grandfather);//变色parent->_col = BLACK;grandfather->_col = RED;}else//左右双旋{RotateL(parent);RotateR(grandfather);//变色cur->_col = BLACK;grandfather->_col = RED;}break;//旋转完成，直接跳出循环}}else{//确定uncleNode* uncle = grandfather->_left;if (uncle && uncle->_col == RED)//uncle为红，仅变色{parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续向上判断cur = grandfather;parent = cur->_parent;}else//uncle为黑或不存在，旋转+变色{if (cur == parent->_right)//左单旋{RotateL(grandfather);//变色parent->_col = BLACK;grandfather->_col = RED;}else//右左双旋{RotateR(parent);RotateL(grandfather);//变色cur->_col = BLACK;grandfather->_col = RED;}break;//旋转完成，直接跳出循环}}}//最后将根节点设置为黑色_root->_col = BLACK;return true;
}//右单旋
void RotateR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR) subLR->_parent = parent;Node* ppNode = parent->_parent;subL->_right = parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (ppNode->_left == parent) ppNode->_left = subL;else ppNode->_right = subL;subL->_parent = ppNode;}
}//左单旋
void RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL) subRL->_parent = parent;Node* ppNode = parent->_parent;subR->_left = parent;parent->_parent = subR;if (parent == _root){_root = subR;subR->_parent = nullptr;}else{if (ppNode->_left == parent) ppNode->_left = subR;else ppNode->_right = subR;subR->_parent = ppNode;}
}

4. 红黑树的查找

红黑树的查找逻辑与传统二叉搜索树相同，注意按照键查找。

代码如下：

//查找
Node* Find(const K& key)
{Node* cur = _root;while (cur){if (key < cur->_kv.first){cur = cur->_left;//小了往左走}else if (key > cur->_kv.first){cur = cur->_right;//大了往右走}else{return cur;//找到了，返回}}return nullptr;//没找到，返回空指针
}

5. 中序遍历、拷贝构造和析构

三个函数的实现逻辑与AVL树完全相同。注意拷贝时不要忘记parent指针。

代码如下：

//中序遍历
void Inorder()
{_Inorder(_root);
}
void _Inorder(Node* root)
{if (root == nullptr) return;_Inorder(root->_left);cout << root->_kv.first << ' ' << root->_kv.second << endl;_Inorder(root->_right);
}

//拷贝构造
RBTree(const RBTree<K, V>& t)
{_root = _Copy(t._root);
}
Node* _Copy(Node* root, Node* parent = nullptr)
{if (root == nullptr) return nullptr;Node* NewRoot = new Node(root->_kv);NewRoot->_col = root->_col;//复制颜色NewRoot->_parent = parent;//设置父指针//递归拷贝左子树和右子树NewRoot->_left = _Copy(root->_left, NewRoot);NewRoot->_right = _Copy(root->_right, NewRoot);return NewRoot;
}

//析构函数
~RBTree()
{_Destroy(_root);
}
void _Destroy(Node* root)
{if (root == nullptr) return;_Destroy(root->_left);_Destroy(root->_right);delete root;
}

6. 检查红黑树是否合法

判断一棵红黑树是否合法，就要判断它是否满足红黑树的性质。可以从以下几点入手：

1. 检查根节点是否为黑色。

2. 当一个节点为红色时，判断其父亲是否是黑色。

3. 检查各个路径上的黑色节点数是否相等。

对于第三点，可以先遍历一条路径（可以选择走最左路径，避免递归），记录路径上的黑色节点个数，然后再判断其他所有路径上的黑色节点个数是否与之一致。

代码实现：

//判断是否为合法红黑树
bool IsValidRBTree()
{//空树，合法if (_root == nullptr) return true;//根节点为红，非法if (_root->_col == RED){cout << "根节点为红" << endl;return false;}int refNum = 0;//记录黑色节点个数Node* cur = _root;while (cur){if (cur->_col == BLACK) refNum++;cur = cur->_left;}//递归检查所有路径return _Check(_root, 0, refNum);
}//路径检查
bool _Check(Node* root, int num, const int refNum)
{if (root == nullptr){//遍历到空，进行黑色节点比较if (num != refNum){cout << "黑色节点数量不相等" << endl;return false;}return true;}//检查是否有连续红色节点if (root->_col == RED && root->_parent->_col == RED){cout << "有连续红色节点" << endl;return false;}//记录当前路径的黑色节点数if (root->_col == BLACK) num++;//递归检查左子树和右子树return _Check(root->_left, num, refNum) && _Check(root->_right, num, refNum);
}

接下来我们写一段代码，插入一组数据，验证红黑树的合法性：

int main()
{RBTree<int, int> t;int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto& e : a){t.Insert({ e,e });}t.Inorder();cout << t.IsValidRBTree() << endl;return 0;
}

运行结果：

7. 程序全部代码

红黑树实现全部代码如下：

#include <iostream>
#include <utility>
using namespace std;enum Color//枚举值表示颜色
{RED,BLACK
};//节点
template<class K, class V>
struct RBTreeNode
{pair<K, V> _kv;//数据域RBTreeNode<K, V>* _left;//指向左孩子的指针RBTreeNode<K, V>* _right;//指向右孩子的指针RBTreeNode<K, V>* _parent;//指向父亲的指针Color _col;//颜色RBTreeNode(const pair<K, V>& kv)//节点构造:_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED){}
};//红黑树类
template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public://强制生成无参构造RBTree() = default;//拷贝构造RBTree(const RBTree<K, V>& t){_root = _Copy(t._root);}//析构函数~RBTree(){_Destroy(_root);}//插入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 (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(kv);if (kv.first < parent->_kv.first){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;//parent为红，进行平衡调整while (parent && parent->_col == RED){//确定grandfatherNode* grandfather = parent->_parent;if (parent == grandfather->_left){//确定uncleNode* uncle = grandfather->_right;if (uncle && uncle->_col == RED)//uncle为红，仅变色{parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续向上判断cur = grandfather;parent = cur->_parent;}else//uncle为黑或不存在，旋转+变色{if (cur == parent->_left)//右单旋{RotateR(grandfather);//变色parent->_col = BLACK;grandfather->_col = RED;}else//左右双旋{RotateL(parent);RotateR(grandfather);//变色cur->_col = BLACK;grandfather->_col = RED;}break;//旋转完成，直接跳出循环}}else{//确定uncleNode* uncle = grandfather->_left;if (uncle && uncle->_col == RED)//uncle为红，仅变色{parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续向上判断cur = grandfather;parent = cur->_parent;}else//uncle为黑或不存在，旋转+变色{if (cur == parent->_right)//左单旋{RotateL(grandfather);//变色parent->_col = BLACK;grandfather->_col = RED;}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 (key < cur->_kv.first){cur = cur->_left;//小了往左走}else if (key > cur->_kv.first){cur = cur->_right;//大了往右走}else{return cur;//找到了，返回}}return nullptr;//没找到，返回空指针}//中序遍历void Inorder(){_Inorder(_root);}//判断是否为合法红黑树bool IsValidRBTree(){//空树，合法if (_root == nullptr) return true;//根节点为红，非法if (_root->_col == RED){cout << "根节点为红" << endl;return false;}int refNum = 0;//记录黑色节点个数Node* cur = _root;while (cur){if (cur->_col == BLACK) refNum++;cur = cur->_left;}//递归检查所有路径return _Check(_root, 0, refNum);}
private://右单旋void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR) subLR->_parent = parent;Node* ppNode = parent->_parent;subL->_right = parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (ppNode->_left == parent) ppNode->_left = subL;else ppNode->_right = subL;subL->_parent = ppNode;}}//左单旋void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL) subRL->_parent = parent;Node* ppNode = parent->_parent;subR->_left = parent;parent->_parent = subR;if (parent == _root){_root = subR;subR->_parent = nullptr;}else{if (ppNode->_left == parent) ppNode->_left = subR;else ppNode->_right = subR;subR->_parent = ppNode;}}//中序遍历void _Inorder(Node* root){if (root == nullptr) return;_Inorder(root->_left);cout << root->_kv.first << ' ' << root->_kv.second << endl;_Inorder(root->_right);}//拷贝构造Node* _Copy(Node* root, Node* parent = nullptr){if (root == nullptr) return nullptr;Node* NewRoot = new Node(root->_kv);NewRoot->_col = root->_col;//复制颜色NewRoot->_parent = parent;//设置父指针//递归拷贝左子树和右子树NewRoot->_left = _Copy(root->_left, NewRoot);NewRoot->_right = _Copy(root->_right, NewRoot);return NewRoot;}//销毁void _Destroy(Node* root){if (root == nullptr) return;_Destroy(root->_left);_Destroy(root->_right);delete root;}//路径检查bool _Check(Node* root, int num, const int refNum){if (root == nullptr){//遍历到空，进行黑色节点比较if (num != refNum){cout << "黑色节点数量不相等" << endl;return false;}return true;}//检查是否有连续红色节点if (root->_col == RED && root->_parent->_col == RED){cout << "有连续红色节点" << endl;return false;}//记录当前路径的黑色节点数if (root->_col == BLACK) num++;//递归检查左子树和右子树return _Check(root->_left, num, refNum) && _Check(root->_right, num, refNum);}Node* _root = nullptr;//根节点指针
};int main()
{RBTree<int, int> t;int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto& e : a){t.Insert({ e,e });}t.Inorder();cout << t.IsValidRBTree() << endl;return 0;
}

总结

红黑树通过引入节点颜色和一系列平衡规则，在保持高效查询性能的同时，优化了插入和删除操作的复杂度。与AVL树相比，红黑树对平衡的要求较为宽松，避免了频繁的旋转调整，从而提升了动态操作的效率。尽管红黑树的结构较为复杂，但它通过颜色标记、旋转操作以及路径黑色节点数量的控制，成功实现了查找、插入和删除操作的平衡。在实际应用中，红黑树被广泛用于操作系统、数据库等领域，发挥着其重要的作用。如果你觉得博主讲的还不错，就请留下一个小小的赞在走哦，感谢大家的支持❤❤❤