【C++】详解红黑树并模拟实现

前言：

       上篇文章我们一起学习了AVL树比模拟实现，我们发现AVL树成功地把时间复杂度降低到了O(logN)。但是同时我们不难发现一个问题，在构建AVL树中我们也付出了不小的代价，频繁的旋转操作导致效率变低。为了解决这个问题，我们本章将迎来更为实用的红黑树，他在提高查找效率的同时也相对AVL树提高了构建树的效率，他的应用将更加广泛（比如map、set的底层实现就是红黑树）！

目录

（一）红黑树的概念

1、概念

2、特性

（二）红黑树的模拟实现

1、结点的定义

2、结点的查找实现（Find）

3、结点的插入实现（Insert）*重点

3.1前序问题

3.2具体流程

情况一：叔叔存在且为红——变色处理

情况二：叔叔不存在or叔叔存在且为黑——旋转+变色

 情况三：叔叔不存在or叔叔存在且为黑——双旋+变色（区别于情况二）

4、具体代码（Find+Insert）

（三）验证红黑树

1、中序遍历

2、验证红黑树几大特性

3、测试用例

（四）项目完整代码

---

（一）红黑树的概念

1、概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black，所以叫红黑树。

通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。

2、特性

• 每个结点不是红色就是黑色
• 根节点是黑色的 
• 如果一个节点是红色的，则它的两个孩子结点是黑色的 
• 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点 
• 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

思考：

为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点

个数的两倍？

这里我们从路径最短的情况和最长的情况分析：

我们假设该红黑树每条路径黑色结点数是3

路径最短的情况：

这条路径没有红色结点，如下图：

路径最长的情况：
这条路径一个黑色节点接着一个红色节点，交相出现：

这时我们发现最短路径时，一条路径上有三个结点(情况一)；最长路径时，一条路径上有五个节点（情况二）。所以可以保证其最长路径中节点个数不会超过最短路径节点个数的两倍。

（二）红黑树的模拟实现

1、结点的定义

我们还是沿用AVL树节点的三叉链定义方法，颜色我们用枚举来实现：

ps：这里一开始结点定义为红色的原因，我们在后文插入的时候会详细讲解。

2、结点的查找实现（Find）

在红黑树中的Find（查找）操作和之前二叉搜索树和AVL树实现方法一样，这里我们简单带过。

结点存的值比当前结点小就向左找，比当前结点大就向右找，最后遇到空节点表示没找到。

3、结点的插入实现（Insert）*重点

3.1前序问题

首先，我们解答上面留下的那个问题，

为什么新插入的结点要默认给红色的？

• 假设我们默认给新增的结点黑色，那么一定违反上面红黑树的特性4（对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点 ）。这样我们还要对其他路径进行修改黑色结点的数量。
• 但是如果默认给红色，我们则是可能违反特性3（如果一个节点是红色的，则它的两个孩子结点是黑色的 ）。为什么说是可能，因为如果他的父亲节点是黑色则不违反。就算违反了。每条路径黑色结点的数量还是一样的，我们只需要调整所在的那一条路径即可，代价相对小了许多。

3.2具体流程

约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

（分别对应parent，grandfather，uncle的意思）

插入几大流程：

• 按照搜索二叉树的查找方法，找到要插入的位置
• 将新增结点插入到待插入位置
• 如果需要调整则调整红黑树

其中需不需要调整主要是看叔叔颜色的情况。

下面具体分析：

我们先给出一个基本的图示

这里的三角形就相当于AVL树中的小长方形，代表了一部分子树。

情况一：叔叔存在且为红——变色处理

• cur为红，p为红，g为黑, u存在且为红

解决方式:将p，u改为黑，g改为红，然后把g当成cur，继续向上调整。

首先我们知道，红黑树调整主要看叔叔，第一步我们将父亲变成黑色，为了维护性质4，我们也要将叔叔的颜色变成黑色，同时也要将祖父结点的颜色变成红色，因为我们此时处理的不一定是整棵树，有可能是某个子树，如果此时不是子树，就需要将根节点变成黑色。这样我们就在局部调整颜色并保证了不破坏规则。

 

调整的部分可能是一整棵树，也可能是某一棵子树

• 如果g是根节点，调整完成后，需要将g改为黑色
• 如果g是子树，g一定有双亲，且g的双亲如果是红色，需要继续向上调整

 

情况一的情景下，我们只关心颜色的调整就可以在不破坏规则的情况下插入结点！

---

情况二：叔叔不存在or叔叔存在且为黑——旋转+变色

情况二可能就是从情况一调整变化得到的情况。

具体情况 1

当叔叔不存在时：

我们调整颜色总会破坏规则，此时结合上面长路径不会超过短路径二倍的特性我们分析，英爱使用到了和AVL树相似的旋转处理。

• 此时是左边高了，我们对图示树进行右单旋，这里的旋转和AVL树中旋转的方式如出一辙，可以拿过来直接复用。
• 同样的道理，如果是右边高了，我们就可以进行左单旋，旋转的方法也和AVL树中的如出一辙，也可拿过来直接复用。（这里我们就不像AVL树那样详细解释了，实现方法是一样的，如果读者不太了解可以看上一篇文章）

 具体情况 2

当叔叔存在且为黑时：

按照上文说明，这种情况必定是由情况一变化而来的。

此时也是旋转+变色

这样子才能保护好红黑树的结构。

---

 情况三：叔叔不存在or叔叔存在且为黑——双旋+变色（区别于情况二）

同样是 叔叔不存在 or 叔叔存在且为黑，为啥分为情况二和情况三呢？

上述旋转的情况都是单边的情况，也就是说，cur、p、g在一条线上的情况，若是出现了这三者不在一条直线的时候，单旋就解决不了问题了。

区别:

• p是g的左，cur是p的左，那么是情况二 —— 单旋
• p是g的左，cur是p的右，那么是情况三 —— 双旋

此时我们就引入了双旋

（这里我们可以结合上一篇AVL树来区别单旋和双旋）

• 先以p为旋转点再以g为旋转点
• 先变到情况二的样子
• 再根据情况二来继续变

其实看完情况二和三有些人就会有疑问了，看上去每条路径上黑色结点树不一样啊，为什么要这样旋转变色？

再此之前我们推测过当叔叔存在且为黑时，一定是由情况一变来的，所以cur一开始是黑的，这个树并不违反性质，子树由情况一变化之后的子树结点的颜色也相应变化了，只是没有显示出来而已。

4、具体代码（Find+Insert）

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;}bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}Node* cur = _root;Node* parent = nullptr;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);if (parent->_kv.first>kv.first){parent->_left = cur;}else if (parent->_kv.first < kv.first){parent->_right = cur;}cur->_parent = parent;//调整颜色while (parent && parent->_col == RED){Node* grandfather = parent->_parent;if (grandfather->_left == parent)//u存在且为红{Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else//u不存在或者为黑,旋转加变色{if (cur == parent->_left){//    g//  p   u//cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//     g//   p   u//     cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else//grandfather->_right == parent{Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){//     g//  u    p//          cuncle->_col = BLACK;parent->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else// ：u不存在/u存在且为黑，旋转+变色{if (cur == parent->_right){//     g//  u    p//          cRotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//      g//   u     p//      cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}

（三）验证红黑树

老样子，我们在上一章模拟实现AVL树后用了几个函数来验证我们构建的树是否是AVL树，这里我们也要验证一下我们构建的这棵树是否是红黑树。

几个验证要点：

• 这棵树是否是二叉搜索树
• 根结点是否是黑色结点
• 红色结点的子结点是否是黑色结点
• 每条路径黑色结点树是否一样

满足这几个要点，也就是红黑树的特性，那么这棵树1就是红黑树了。

1、中序遍历

一棵树是红黑树的前提就是他必须是二叉搜索树，二叉搜索树的特点就是中序遍历是有序的。

void InOrder(){return _InOrder(_root);}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << " ";_InOrder(root->_right);}

ps：为了符合用户的使用习惯，我们还是采取嵌套的方式，大家不明白的可以看一下上一篇文章验证处有说明哦！

2、验证红黑树几大特性

相对AVL树，验证红黑树是更加麻烦的，几个要点：

• 首先判断根结点是否是黑色
• 判断每条路径黑色结点数我们思路是先取一条路径黑色结点数量为基准值，然后递归统计其他路径的数目，遇到空结点再比较
• 遇到红色结点我们如果判断他的孩子结点是否是黑色，如果是要跳过（代码不好写），不如换个思路，遇到一个红色结点就判断双亲是否是红色，如果是（存在连续红色结点）返回false。

bool IsBalance(){if (_root->_col == RED){cout << "根节点颜色是红色" << endl;return false;}int benchmark = 0;Node* cur = _root;while (cur){if(cur->_col==BLACK)benchmark++;cur = cur->_left;}return _Check(_root, 0, benchmark);}private:bool _Check(Node* root, int blackNum, int benchmark){if (root == nullptr){if (benchmark != blackNum){cout << "某条路径黑色节点的数量不相等" << endl;return false;}return true;}if (root->_col == BLACK){++blackNum;}if (root->_col == RED&& root->_parent&& root->_parent->_col == RED){cout << "存在连续的红色节点" << endl;return false;}return _Check(root->_left, blackNum, benchmark)&& _Check(root->_right, blackNum, benchmark);}

通过递归的方式将每条支路都走了一遍和基准值比较，并且将红黑树的性质全都验证了。

3、测试用例

void Test_RBTree1()
{//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14, 16, 3, 7, 11, 9, 26, 18, 14, 15 };RBTree<int, int> t1;for (auto e : a){/*	if (e == 14){int x = 0;}*/t1.Insert(make_pair(e, e));//cout << e << "插入：" << t1.IsBalance() << endl;}t1.InOrder();cout << endl;cout << t1.IsBalance() << endl;
}void Test_RBTree2()
{srand(time(0));const size_t N = 5000000;RBTree<int, int> t;for (size_t i = 0; i < N; ++i){size_t x = rand() + i;t.Insert(make_pair(x, x));//cout << t.IsBalance() << endl;}//t.Inorder();cout << t.IsBalance() << endl;cout << t.Height() << endl;
}

精检验，没有问题：

（四）项目完整代码

#pragma once
#include<iostream>
#include<assert.h>using namespace std;enum Colour
{RED,BLACK,
};template<class K,class V>
struct RBTreeNode
{RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;pair<K, V> _kv;Colour _col;RBTreeNode(const pair<K,V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED){}
};template<class K,class V>
struct RBTree
{typedef RBTreeNode<K, V> Node;void Destroy(Node* root){_Destroy(root);root = nullptr;}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;}bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}Node* cur = _root;Node* parent = nullptr;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);if (parent->_kv.first>kv.first){parent->_left = cur;}else if (parent->_kv.first < kv.first){parent->_right = cur;}cur->_parent = parent;//调整颜色while (parent && parent->_col == RED){Node* grandfather = parent->_parent;if (grandfather->_left == parent)//u存在且为红{Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else//u不存在或者为黑,旋转加变色{if (cur == parent->_left){//    g//  p   u//cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//     g//   p   u//     cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else//grandfather->_right == parent{Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){//     g//  u    p//          cuncle->_col = BLACK;parent->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else// ：u不存在/u存在且为黑，旋转+变色{if (cur == parent->_right){//     g//  u    p//          cRotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//      g//   u     p//      cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}void InOrder(){return _InOrder(_root);}int Height(){return _Height(_root);}bool IsBalance(){if (_root->_col == RED){cout << "根节点颜色是红色" << endl;return false;}int benchmark = 0;Node* cur = _root;while (cur){if(cur->_col==BLACK)benchmark++;cur = cur->_left;}return _Check(_root, 0, benchmark);}private:bool _Check(Node* root, int blackNum, int benchmark){if (root == nullptr){if (benchmark != blackNum){cout << "某条路径黑色节点的数量不相等" << endl;return false;}return true;}if (root->_col == BLACK){++blackNum;}if (root->_col == RED&& root->_parent&& root->_parent->_col == RED){cout << "存在连续的红色节点" << endl;return false;}return _Check(root->_left, blackNum, benchmark)&& _Check(root->_right, blackNum, benchmark);}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << " ";_InOrder(root->_right);}int _Height(Node* root){if(root==nullptr){return 0;}int leftH = _Height(root->_left);int rightH = _Height(root->_right);return leftH > rightH ? leftH + 1 : rightH + 1;}void _Destroy(Node* root){if (root == nullptr)return;_Destroy(root->_left);_Destroy(root->_right);delete root;}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 (ppnode == nullptr){_root = subR;_root->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subR;}else{ppnode->_right = subR;}subR->_parent = ppnode;}}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;_root->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subL;}else{ppnode->_right = subL;}subL->_parent = ppnode;}}
private:Node* _root=nullptr;
};void Test_RBTree1()
{//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14, 16, 3, 7, 11, 9, 26, 18, 14, 15 };RBTree<int, int> t1;for (auto e : a){/*	if (e == 14){int x = 0;}*/t1.Insert(make_pair(e, e));//cout << e << "插入：" << t1.IsBalance() << endl;}t1.InOrder();cout << endl;cout << t1.IsBalance() << endl;
}void Test_RBTree2()
{srand(time(0));const size_t N = 5000000;RBTree<int, int> t;for (size_t i = 0; i < N; ++i){size_t x = rand() + i;t.Insert(make_pair(x, x));//cout << t.IsBalance() << endl;}//t.Inorder();cout << t.IsBalance() << endl;cout << t.Height() << endl;
}

祝您学业有成！