C++红黑树实现
文章目录
- （一）红黑树的介绍
- （二）红黑树的实现
- 1.红黑树的结构
- 2.插入函数的实现
- 3.检测一棵树是否是红黑树
- 4.查找函数的实现
（一）红黑树的介绍
红黑树的概念：红黑树是一棵二叉搜索树，他的每个结点增加一个存储位来表示结点的颜色，但颜色只能是红色或者黑色。它是通过约束任何一条从根到叶子结点上的颜色来控制平衡的，这样就会确保没有一条路径会比其他路径长出两倍，因而红黑树接近平衡
红黑树实现的规则：
- 结点颜色只能是红色或者黑色
- 根结点必须是黑色
- 若一个结点是红色，那么它左右孩子的结点只能是黑色，换句话说就是，不能有连续的红色结点（注：若红色结点的孩子结点为空，那么该“空叶子结点”也是黑色的）
- 对于任意一个结点，从该结点到其他所有空结点的简单路径上，均包含相同数量的黑色结点
以下是经典的红黑树举例：
从图中可以看到，根结点均为黑色，且红色结点的左右孩子均为黑色结点，且不存在连续的红色结点。对于规则4的理解，我们可以看到图中的第一棵红黑树，看根结点，它到所有空结点的简单路径都只有两个黑色的结点，例如：从根结点到结点10的左孩子的路径上只有两个黑色结点；从根结点到结点35的左孩子的路径上也只有两个黑色结点；从根结点到结点35的右孩子的路径上也只有两个黑色结点。
红黑树的时间复杂度：
可以通过极端场景来进行红黑树的效率分析，假设每条路径有h个黑色结点，那么最长路径就是一黑一红的情况，就有2*h个结点，最短路径就是全黑的情况，就有h个结点，那么就可以推出，红黑树的最长路径 <= 2x最短路径，也就确保没有一条路径会比其他路径长出两倍。
一棵红黑树，我们将最短路径的横截部分截取下来，可看作一个满二叉树，假设N是红黑树的结点个数，h又是最短路径的高度，推出N >= 2^h -1，又从上面得知2*h是最长路径的高度，将其看作个满二叉树，推出N <= 2^2h - 1，由此推出2^h -1 <= N <= 2^2h -1，也就说明了，h可约等于logN，也就意味着红黑树增删查改最坏的情况下也就是最长路径为2xlogN，那么其时间复杂度就为O(logN)
（二）红黑树的实现
1.红黑树的结构
由于红黑树的底层是二叉搜索树，所以，它的结构与二叉搜索树类似，区别就是需要多一个变量来存储结点的颜色，结构代码如下：
#pragma once
#include <iostream>
using namespace std;
//用一个枚举的结构来记录颜色
enum Colour
{
RED,
BLACK
};
template<class k,class v>
struct RBTNode
{
pair<k, v> _kv;
RBTNode<k, v>* _left;
RBTNode<k, v>* _right;
RBTNode<k, v>* _parent; //记录父结点便于控制树的平衡
Colour _col;
RBTNode(const pair<k,v>& kv)
:_kv(kv)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
{ }
};
template<class k,class v>
class RBTree
{
typedef RBTNode<k, v> Node;
public:
private:
Node* _root = nullptr;
};
2.插入函数的实现
步骤如下：
- 底层是二叉搜索树，所以数据插入需要先按照二叉搜索树的规则，找到要插入的位置，找到后观察是否符合红黑树的规则
- 如果是空树，那么新增结点就是根结点，该结点必须是黑色。若是非空树插入，新增结点必须是红色，虽然说可能会破坏不能有连续红结点的规则，但是如果插入的结点是黑色，就很难维持每条路径上的黑色结点的数量相同的规则，连续红结点的规则相对于保持黑色结点数量相同的规则来说，比较好维护
- 非空树插入后，新增结点必须是红色，若父结点是黑色，则符合红黑树规则，插入结束
- 非空树插入后，由于新增结点是红色，若父结点也是红色，存在连续的红结点，不符合红黑树的规则，则需要进一步的分析，进行处理，让其符合要求
1到3步骤的代码实现如下：
bool insert(const pair<k, v>& kv)
{
if (_root == nullptr)
{
//为空树，新增结点为根结点，结点需为黑色
_root = new Node(kv);
_root->_col = BLACK;
return true;
}
else
{
Node* cur = _root;
Node* parent = nullptr;
//根据二叉搜索树的插入规则，找到空位置进行插入
while (cur)
{
if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else
{
return false;
}
}
cur = new Node(kv);
//新增结点不是根结点，需为红色
cur->_col = RED;
if (parent->_kv.first > cur->_kv.first)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent;
//判断父结点是否为红结点，若为红则进行处理，若不为红则插入结束
//......
return true;
}
}
若父结点为红，则分以下三种情况进行处理：
- 情况1，如下图：
如图，新增结点2之后，导致连续的红结点，我们可以通过==变色==，对该种现象进行处理，变色操作：cur为红，parent为红，grandfather为黑，uncle存在且为黑，那么就可以将parent和uncle的结点变成黑色，再把grandfather的结点变成红色，变色操作结束，继续往上更新，向上更新就是把cur位置变到grandfather的位置，父结点的位置变到grandfather的父结点的位置，因为将grandfather变成红结点，有可能grandfather的父结点也为红
情况1只进行变色的操作，所以无论新增结点在父结点的左边还是右边，父节点在grandfather的左边还是右边，都是用变色的操作进行处理，变色处理的前提条件就是uncle结点存在且为红
- 情况2，如下图：
（1）uncle不存在时，新增结点一定是在cur结点，因为要满足每条路径上的黑色结点的数量相同，所以结点2一定是新增的
（2）uncle存在且为黑时，结点2一定不是新增结点，为满足路径上黑色结点的数量相同它原本的结点颜色肯定为黑色，但由于它的左右子树出现了连续的红色结点，在变色的过程中，导致它变成了红色，所以出现了这种连续红结点的现象
上述的uncle存在与否的情况，其实可以视为同一种情况，因为文章上面有说到，若结点为空结点，该空的“叶子结点”是黑色，所以uncle位置，可以视为有一个空的黑色的叶子结点
那么对上述连续的红色结点的处理操作就是，单旋+变色，若grandfather与parent、cur都在“一条直线上”也就是说它们连起来的路径是直的，且parent和cur都在grandfather的左边，就进行右单旋+变色；若grandfather与parent、cur都在“一条直线上”且parent和cur都在grandfather的右边，就进行左单旋+变色。单旋完之后，parent变黑色，grandfather变红色，插入结束，不需要再继续向上更新
左单旋的操作与右单旋完全类似，这里就不举例了，若对旋转不理解的友友，可以看我的上一篇博客AVL树的实现，那里有详细的介绍
- 情况3，如下图：
（1）与情况2相同，当uncle不存在时，新增结点必然是结点7
（2）当uncle存在且为黑时，结点7变成了红结点，必然是由情况1变色所导致
同样地，上图中的两棵红黑树的现象可看作同一种问题。对上图连续红结点的处理操作就是，双旋+变色，图中我们可看到连续红结点的位置，与grandfather的结点连起来的路径不是一条直线，那么就可以通过双旋的操作进行处理。若parent结点在grandfather的左边，cur结点在parent的右边，就进行左右双旋+变色的操作；若parent结点在grandfather的右边，cur结点在parent的左边，就进行右左双旋+变色的操作。旋转完之后cur结点就被旋转到了grandfather的位置，那么就将cur结点变成黑色，grandfather的结点变成红色，操作结束，不需要继续向上更新。
上图中的，parent结点位于grandfather的左边，cur结点位于parent结点的右边，所以进左右双旋+变色的操作，操作结果如下图：
右左双旋的例子这里就不举例了，也是类似的做法。上面的插入过程都是在插入之前这棵树是符合红黑树规则的树的情况下进行插入的
完整插入代码如下：
bool insert(const pair<k, v>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLACK;
return true;
}
else
{
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else
{
return false;
}
}
cur = new Node(kv);
cur->_col = RED;
if (parent->_kv.first > cur->_kv.first)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent;
//判断是否有连续的红结点
while (parent && parent->_col == RED)//父结点存在且为红，就说明有连续的红结点
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)
{
//说明uncle结点在grandfather的右边
Node* uncle = grandfather->_right;
//情况1,uncle存在且为红色，直接进行变色处理
if (uncle && uncle->_col == RED)
{
grandfather->_col = RED;
parent->_col = uncle->_col = BLACK;
//继续向上更新
cur = grandfather;
parent = cur->_parent;
}
else
{
//说明uncle不存在或者uncle存在且为黑
//情况2，右单旋+变色
if (parent->_left == cur)
{
//说明父结点、cur结点、grandfather结点的路径在一条直线上，且位于左边
//那么对grandfather结点进行右单旋+变色
RotateR(grandfather);
//变色
grandfather->_col = RED;
parent->_col = BLACK;
break;
}
else
{
//情况3，双旋+变色
//说明父结点、cur结点、grandfather结点的路径不在一条直线上，父结点位于祖先结点的左
// cur结点位于父结点的右
//那么对grandfather结点进行左右双旋+变色
RotateL(parent);
RotateR(grandfather);
grandfather->_col = RED;
cur->_col = BLACK;
break;
}
}
}
else
{
//parent位于grandfather的右边
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED)
{
//情况1，无论在哪边都是直接变色
grandfather->_col = RED;
parent->_col = uncle->_col = BLACK;
cur = grandfather;
parent = cur->_parent;
}
else
{
//uncle不存在或者uncle存在且为黑
//情况2，左单旋+变色
if (cur == parent->_right)
{
//说明父结点、cur结点、grandfather结点的路径在一条直线上，且位于右边
//那么对grandfather结点进行左单旋+变色
RotateL(grandfather);
grandfather->_col = RED;
parent->_col = BLACK;
break;
}
else
{
//情况3，双旋+变色
//说明父结点、cur结点、grandfather结点的路径不在一条直线上，父结点位于祖先结点的右
// cur结点位于父结点的左
//那么对grandfather结点进行右左双旋+变色
RotateR(parent);
RotateL(grandfather);
grandfather->_col = RED;
cur->_col = BLACK;
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* pparent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (pparent == nullptr)
{
_root = subL;
subL->_parent = pparent;
}
else
{
if (pparent->_left == parent)
{
pparent->_left = subL;
}
else
{
pparent->_right = subL;
}
subL->_parent = pparent;
}
}
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
Node* pparent = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (pparent == nullptr)
{
_root = subR;
subR->_parent = pparent;
}
else
{
if (pparent->_left == parent)
{
pparent->_left = subR;
}
else
{
pparent->_right = subR;
}
subR->_parent = pparent;
}
}
3.检测一棵树是否是红黑树
只要根据红黑树的4条规则检测，就可判断是否是红黑树了。规则1和规则2都很好检测，规则3我们可通过用孩子结点来判断父结点是否为红色，因为每一个孩子结点都有唯一的父亲结点，从下往上判断，是否存在连续结点即可。规则4，可通过找一条路径作为参照路径，计算该路径的黑色结点个数，再通过递归来遍历每条路径，与参照路径的黑色结点个数进行对比，即可。
实现代码如下：
bool _Isbalance(Node* root)
{
if (_root == nullptr)
{
return true;//空树也是红黑树
}
if (_root->_col == RED)
{
return false;//根结点不能为红色
}
int blackcount = 0;
Node* cur = _root;
//我选择用最左路径作为参照路径
while (cur)
{
if (cur->_col == BLACK)
{
blackcount++;
}
cur = cur->_left;
}
return check(root, 0, blackcount);
}
//用递归来遍历每条路径
bool check(Node* root, int blacknum,const int blackcount)//balcknum用来记录每条路径的黑色结点数
{
if (root == nullptr)
{
if (blacknum == blackcount)
{
return true;
}
cout << "黑色结点数不相同" << endl;
return false;
}
if (root->_col == RED && root->_parent->_col == RED)
{
cout << "存在连续的红色结点" << endl;
return false;
}
if (root->_col == BLACK)
{
blacknum++;
}
return check(root->_left, blacknum, blackcount)
&& check(root->_right, blacknum, blackcount);
}
4.查找函数的实现
根据二叉搜索树的规则来进行查找，比当前的值大就往右边查找，比当前值小就往左边查找即可。
代码如下：
Node* find(const pair<k, v>& kv)
{
Node* cur = _root;
while (cur)
{
if (cur->_kv.first > kv.first)
{
cur = cur->_left;
}
else if (cur->_kv.first < kv.first)
{
cur = cur->_right;
}
else
{
return cur;
}
}
return nullptr;
}