详解c++---红黑二叉树的原理和实现_设计一个c++类redblacktree,他派生于抽象类bstree,函数find,insert,d

什么是红黑二叉树树

avl树是通过控制平衡因子来控制二叉搜索树的平衡，当某个节点的平衡因子等于2或者-2的话我们就根据他所在的位置来进行旋转，如果这个节点位于右右的话就对其进行向左旋转，如果这个节点位于左左的话就对其进行向右旋转，如果这个节点位于右左的话就对其进行右左旋转，如果这个节点位于左右的话就对其进行左右旋转，平衡因子是通过控制节点的平衡因子的方式来控制搜索二叉树的平衡，那么红黑二叉树就是通过控制每个节点的颜色来控制二叉树的平衡，在每个节点上面增加一个存储位置用来表示节点的颜色，可以是red和black，通过对任何一条从根到叶子的路径上各个节点着色的限制来确保红黑树总没有一条路劲会比其他路劲长出两倍，因而最接近平衡。也就是说avl树是一种控制搜索二叉树平衡的方法，红黑树又是另外一种控制搜索二叉树平衡的方法。

红黑树的性质

我们首先来看看红黑二叉树有哪些特点：

1.每个节点不是红色就是黑色。
2. 根节点是黑色的。
3. 如果一个节点是红色的，则它的两个孩子节点是黑色。
4. 对于每个节点，从该节点到其所有后代的简单路径上均包含相同数目的黑色结点。这里的路径得算到空节点为止。
5. 每个叶子节点都是黑色的(此时的叶子节点指的是空结点)。

第一点特征就是限制每个节点的颜色只能是红色或者黑色，如果没有这个性质作为限制的话我们这就不能叫红黑二叉树了而是叫多色二叉树，第二个节点就是规定不管红黑二叉树长什么样长度为多少他的根节点永远都是黑色，第三点表示的意思就是当一个节点为红色时那么他的子节点必须得是黑色，这样做的目的就是为了防止出现连续的红色节点，比如说下面的图片：

这种树就是错误的，因为出现了连续的红色节点，但是这里反则来是可以的黑色节点的下面既可以是红色节点也可以是黑色节点这里是没有要求的。第四点时红黑二叉树最关键的一点，这里的每条路径指的时根节点到空节点的路径，比如说下面的图片

这里有多少个空节点就说明当前有多少条不同的路径，这里存在六个空节点所以就存在6条不同的路径，所以上面的第四点就是得保证6条路径上的黑色节点的数目是一样的，比如说下面的图片：

上面的二叉树就不符合我们的要求因为3号路径上的黑色节点的数目于其他路径的黑色节点的数目不一样，所以他不是红黑二叉树，第五点就是给第四点进行辅助没啥用，那么看到这里想必大家应该知道了红黑二叉树的规则，那这些性质又是如何保证二叉树的平衡的呢？首先红黑二叉树所能达到的平衡是最长路径的长度要小于等于最短路径的两倍，上面的性质规定每个红色节点的孩子节点肯定得是黑色的，而黑色节点的孩子不一定是红色的，所以最短路径为一条路径上全是黑色的节点，最长的路径则是一条路径中红色和黑色节点交替形成的支路，比如说下面的图片这里为了方便我们就不考虑空节点所带来的影响：

因为每条路径的黑色节点数目是相同的，所以上述图片中1号路径就是最短的情况，3号路径就是路径最长的情况，通过上述的四个性质就可以保证我们的树是相对平衡的。

红黑树的效率分析

红黑树的最好情况就是所有的支路都是一黑一红，这种情况就是满二叉树。最差情况就是：左右最不平衡
左子树全部都是黑色的节点，右子树都是一黑一红，假设全黑路径的长度是h，只有一两条路径是最坏的情况的话所有节点的个数为：2^h-1+红色节点的个数=所有节点的个数。因为红色节点的个数可以忽略不计，所以h=logN，所以红色节点的支路长度就为2*logN，虽然这里没有那么平衡但是这里的搜索次数对于cpu计算的次数来说的话依然很少，一个要搜索30次一个要搜索60次这个差距可以忽略不计，虽然没有avl树好，但是差别也不大，而且avl树之所以非常的平衡，但是这个平衡是通过频繁的旋转不停的更新节点的平衡因子所得到的，这个带来的效率损失不一定比红黑树要少，红黑树通过减少旋转的次数通过减少平衡因子的更新换来一个不是那么平衡的红黑树，那么这就是红黑二叉树的效率，两者既有优点又有缺点。

红黑树的准备工作

在AVL树里面通过每个节点添加平衡因子的方式来实现平衡，那么在红黑树里面就是每个节点添加整型变量记录节点的颜色即可，那么这里的颜色存在两种情况，我们直接使用枚举将这两个情况列举出来，比如说下面的代码：

enum colour
{
	RED ,
	BLACK ,
};
1
2
3
4
5

然后我们就用struct创建一个描述节点的类，这个类里面有三个指针，一个指向左子树一个指向右子树一个指向父节点，然后还有一个pair类型的对象来存储数据，并且还有一个整型变量来记录当前节点的颜色，因为节点里面会存储各种各样的数据，所以我们还得给节点添加一个模板上去，那么这里的结构体的数据就如下：

template<class K,class V>
struct RBTreeNode
{
	RBTreeNode<K, V>* parent;
	RBTreeNode<K, V>* right;
	RBTreeNode<K, V>* left;
	pair<K, V> kv;
	colour _col;
};
1
2
3
4
5
6
7
8
9

那么接下来我们就要实现这个结构体的构造函数，首先这个构造函数需要一个pair类型的参数用来初始化内部的pair数据，然后在构造函数里面就可以将三个指针初始化为nullptr，那么这里就存在一个问题colour变量的内容初始化为什么？这里有两个选择一个初始化为红色一个初始化吧为黑色，那我们默认初始化为什么颜色呢？是初始化为黑色吗？好像不对吧我们说红黑树有个特性就是二叉树的每条路径上的黑色节点数目都得是相等，如果这里默认初始化为黑色的话我们不管插入这个节点之前是数量是相等的还是插入这个节点之后是相等的，这里都必定会出现问题，比如说下面的图片

插入之前这个树是不正常的，插入之后这个树就变成正常的了，比如说下面的图片：

那这里不就出现问题了嘛，我之前树的结构就出错了那为什么还能插入节点呢？对吧按之前的逻辑来看的话应该是逻辑没出错再插入节点对吧，所以这种情况是错的，第二种情况就是插入之前树的结构是对的那插入一个黑色的节点之后呢？我们来看看下面这张图片，这个是插入之前树的结构：

插入之后树的结构变成这个样子：

对吧依然不符合规定，所以对于黑色来说的话不管是那种情况插入节点都会导致树的结构不符合规定，那我们这里就来看看红色，我们说红黑二叉树中不能出现连续的红色节点比如说插入之前树的结构是这样的

这时再插入一个节点如果是红色的话是不是就出问题了啊对吧，比如说下面的图片：

是不是就报错了啊对吧，但是将颜色设置为红色有一个好处就是他有时候会出错但是有时候又不会出错，比如说下面的图片，这种情况插入一个红色的节点就不会报错：

这里有4个位置可以供我们插入，但是不管插在哪里都不会影响树的结构也不会报错，所以这里选择颜色的时候红色会比黑色好一些，虽然两个都会出错但是红色会更少所以选择红色，那么这里完整的代码就如下：

template<class K,class V>
struct RBTreeNode
{
	RBTreeNode(const pair<K, V>& _kv)
		:parent(nullptr)
		,right(nullptr)
		,left(nullptr)
		,kv(_kv)
		,_col(RED)
	{}
	RBTreeNode<K, V>* parent;
	RBTreeNode<K, V>* right;
	RBTreeNode<K, V>* left;
	pair<K, V> kv;
	colour _col;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

然后就是完成红黑树这个类的准备工作，那么这个类中就有一个成员变量root用来记录根节点的root，然后钩爪函数我们将其初始化为空即可，那么这里的代码就如下：

template<class K,class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
	RBTree()
		:root(nullptr)
	{}
private:
	Node* root;
};
1
2
3
4
5
6
7
8
9
10
11

准备工作完成

红黑树的insert函数

这里的insert函数跟之前的实现逻辑是差不多，首先得判断一下当前插入的位置是不是根节点，如果是根节点的话根据红黑树的性质我们得将该节点的颜色修改成为黑色，然后再修改类中root指针的指向，那么这里的代码如下：

bool insert(const pair<K, V>& _kv)
{
	if (root == nullptr)
	{
		root = new Node(_kv);
		root->_col = BLACK;
		return true;
	}
}
1
2
3
4
5
6
7
8
9

当插入节点的地方不为空的话，这里就得先根据搜索二叉树的性质找到要插入节点的位置，那么这里还是原来的思想先创建两个指针一个指向父节点一个指向子节点，通过while循环不停的将子节点的值和要插入的值进行比较，如果相等的话就就返回false，如果要插入的值较大的话就往右边移动，如果插入的值较小的话就往左边移动，直到指向子节点的指针为空就停止循环，那么这里的代码就如下：

Node* _cur = root;
Node* _parent = nullptr;
while (_cur != nullptr)
{
	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;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

当程序走到这里说明我们当前已经找到了节点应该插入的位置，那么这里我们就用new创建一个节点，用cur指向这个新创建出来的节点，然后判断一下要插入的节点位于parent的左边还是右边，然后再将其链接起来，那么这的代码就如下：

_cur = new Node(_kv);
if (_kv.first > _parent->kv.first)
//如果插入的数据比parent的数据大
{
	_parent->right = _cur;
	_cur->parent = _parent;
}
else
//如果插入的数据比parent的数据笑
{
	_parent->left = _cur;
	_cur->parent = _parent;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

那么代码走到这里insert函数的第一步就算完成了，那么接下来我们就要对插入的节点进行调整。

节点的调整

这里的调整跟AVL树的调整差不多，也是可以将数不清的各种情况具体归结于以下几种情况，在总结规律之前我们首先来介绍几个节点，比如说下面的图片：

我们把刚插入的节点称为cur，那么他的父节点我们就称为parent，父节点的父节点我们就称为grandparent简称grand，我们把grand的另外一个子节点称为uncle，那么知道这些之后我们就能对所有出现的情况来进行总结。

情况一

情况一：cur为红，parent也为红，g为黑，uncle存在并且颜色也为红色。 比如说下面的图片：

这种情况他就违反了不能出现连续的红色节点的性质，所以我们这里的调整方法就是将节点p和节点u的颜色修改成为黑色，但是这样修改之后不同路径的节点数目就又变的不一样了，所以我们还得修改g的颜色将其修改为红色，那么图片就变成了下面这样：

这样树中既没有了连续的红色节点，并且每个路径的黑色节点的数目也是一样的。那么这里大家要注意的一点就是如果节点g是根节点的话，那这里调整成为红色是会出现错误的，所以我们得判断一下如果当前g为根节点的话我们就不调整它的颜色，如果g不为根节点我们就将其调整为红色，比如说下面的图片

情况一是不分方向的，只要p节点为红且u节点也为红的话就可以采用这样的方法来进行调整。

情况二

情况二：cur的颜色为红，p也为红，g为黑，u不存在或者存在且节点的颜色为黑。那么这里的情况对应的有两种图形一种事u存在且为红，第二种就是u压根不存在比如说下面的图片：

这个就是u存在且u的颜色为黑

这种就是u压根就不存在，那么接下来我们就来看看第一个图片叔叔存在且为黑

对于这种情况cur根本就不可能是新增的节点，因为我们把cur节点去掉再看这颗树的时候就会发现u所在的路线的黑色节点数量比其他节点的要多，所以在插入cur节点之前这个树就已经有问题了，所以出现这种情况的唯一可能就是由第一种情况转换而来，比如说下面的图片

cur为红p和u也为红，所以当前插入的节点就属于第一种情况我们将p和u改成黑色将g改成红色，那么这里的图片就变成这样：

因为g的改变可能会影响上面节点的稳定性所以将情况一解决完之后我们又得吧g当成新添加的节点，所以cur就指向了当前的g，其他关系就依次往上推，那么图片就变成了下面这样：

那么这就变成了第二种情况，cur和p为红，u存在且和g的颜色一样为黑，如果出现了这样的情况那么就说明当前的树违背了最长路径是最短路径两倍的规则，所以对于这种情况我们得降低左树的高度，那么这里我们就可以采用之前AVL树的思路，在之前的学习中我们说如果左边的树较高但是插入的节点依然在左边的话我们就采用向右旋转，让子树整体往右边旋转，使得左边的高度降低，右边的高度升高，那么这里也是同样的道理，当前最短路径是最右边的u，最长的路径为左边的cur，所以我们这里可以采用对根节点向右旋转来改变当前树的两边的高度，那这里就是将p的右子树放到g的左边，然后将g放到p的右边比如说下面的图片：

链接起来就变成这样：

旋转之后可以看到这里的高度问题确实解决了，但是这里还有个问题没有解决就是每条路径上黑色节点的数量，这里很明显是不相等的，所以我们这里还得做一个处理就是将g节点的颜色变成红色，将p的颜色变成黑色，那么这里的图片就变成了这样：

变成这样这个树就符合了所有规则，那么这种情况我们就可以简单的称为cur节点位于左子树的左边，那么与之相反的就有插入的节点位于树的右边，这样就会导致树的右边变高那么对于相反的情况我们就得使用向左旋转来进行解决，比如说下面的图片：

通过第一种情况的调整树就会变成下面这个样子：

再调整以下cur和g ，p，u指针的指向就可以得到下面的图片：

再对其进行左旋转就可以得到下面的图片：

最后再修改一下p和g的颜色就可以得到下面的图片：

看到这里大家应该能够理解上面解决问题的过程，可是这时有小伙伴就要抬杠了说你上面的都是指定情况p，u，g节点的左右子树都被你画好了你这样变可以，那我要是换个情况你还能这么变动吗？答案是依然可以的，我们把cur节点位于左子树的左边的情况简化成为下面这张图片：

对吧！这时有些小伙伴就敏捷的发现这里出现了我呢提，好家伙两边黑色节点的数量不一样，u这边的明显比p这边的看上去要多一个节点，可是真的是这样的吗？我们说第二种情况一定是由第一种情况转换而来的，而第一种情况的转换方法是（这里不考虑g为根节点的情况）：将g由原来的黑色变为红色，将u和p由原来的红色变为黑色，比如说下面的图片：

那么这里我就要问大家一个问题，出现情况一的原因是什么？是不是因为有两个连续的红色节点，而不是黑色节点的数目不一样对吧，那我们解决情况一的过程有没有修改每条路径上的黑色节点数量呢？好像没有吧，虽然颜色的位置发生了改变，但是黑色节点的数目都是一样的对吧，好！我们说情况2是由情况1转换而来的，也就是说插入一个节点之后先经历了情况一的问题再出现了当前情况二的问题，但是我们不插入这个节点的话是不是什么问题都没有情况一不会出现情况二也不会出现，那是不是就说明之前的树是正常的，正常的话每条路径上的黑色节点数量是不是就是一样的，插入节点出现了情况1我们对其进行了修改，但是修改的过程我们没有改变每条路径上的黑色节点的数目，那是不是就能够证明经过情况一之后当前的情况二的每条路径上的黑色节点数目依然是相等的，也就是说我们假设d和e子树上存在n-1个黑色节点，那么a b c中就一定存在n个黑色节点，因为这里是插入的cur而引发了一系列的问题，所以没插入之前这个树是没有问题的，所以c d e子树也是没有问题的，插入cur之后我们要对其进行调整，调整之后的结果可能会g节点出现问题，但是它却能够保证p u cur节点没有问题，所以a，b子树也是没有任何问题的，情况二的问题就只会出现在g和g的parent的之间，也就是调整节点指向的p和cur之间，其他子树都是没有问题的，那情况二调整之后的结果就变成了这样：

我们说a b c d e的结构上是没有任何问题的，并且a b c子树都有n个黑色节点，d e子树都有n-1个节点，所以经过情况二调整之后不管a b c d e子树长什么样这种调整都是对的，并且这个调整完成之后这个树的根节点为黑色，并不会引起像情况一一样的连续红色节点的情况，而且调整完之后该子树的每条黑色节点数目也没有发生变化，所以这个树往上的其他节点就不需要继续调整了。这个就是cur位于右边的右，采用向右旋转并修改g节点的方法来进行调整

这种就是插入的节点位于右子树的右边采用的调整方法为向左旋转并修改g节点的颜色。那么上述的都是u节点存在的情况，如果说u不存在的话这里的修改方法会有变动吗？如果u不存在的话那么他的两个子树e和d肯定也是不存在的，所以上图g含有u的那边黑色节点的数目就为1，p和cur的颜色都为红色，所以他们子树c d a要么不存在要么就子树的根节点为黑色，但是如果为黑色的话就不符合每条路径黑色节点数目相同的情况，所以这里的a b c也得为空，所以当u不存在时我们的树就变成了这个样子：

那么这种形式所采用的调整方法也是向左旋转，旋转完之后修改p和g的颜色

同样的道理这里也存在一个相反的情况：

那么这种情况就是采用向右旋转并修改p和g的情况，那这里的图片就变成下面这个样子：

那么这就是u为空的两种情况，所以大家通过上面的例子可以看到这里不管是u为空还是不为空处理的方法都是一样的，如果cur在右边并且还是p的右的话就采用左旋转并修改p和g节点的颜色，如果cur在左并且是parent的左的话就向右旋转并修改p和g的颜色，那么这就是第二种情况。

情况三

情况三：cur为红，p为红，g为黑，u不存在/u存在且为黑
虽然情况三看上去和情况二是一样的，但是情况三和情况二节点的位置是不一样的，情况二是p是g的左孩纸，cur是p的左孩子，或者p是g的右孩子，cur的是p的右孩子，而这里的情况三就是p是g的左孩子，cur是p的右孩子或者p是g的右孩子，cur是p的左孩子，比如说下面的图片：

当然情况三也不可能是一步就能得到的，它也是通过情况一转换过来的，原因跟前面的情况二是一的，如果cur是插入的节点那么这个树之前就是错的，所以它只能是由情况一转换过来的，比如说下面的图片：

这个就是情况一，将p和u修改成为黑色将g修改成为红色就变成下面这个样子：

更新一下节点的指向就变成了下面这个样子：

那么这就是情况三出现的过程，p是g的左节点，cur是p的右节点，我们就把这种现象成为左右，对于这种情况我们调整的方法就是对p节点实行左单选，旋转之后的图形就变成了下面这样：

那变成这样之后是不是就非常的眼熟啊对吧，情况三经过旋转就变成了上面的情况二，那么我们再对这个执行情况二的处理是不是就可以了啊对吧。但是这里大家要注意的一点就是这里修改节点的颜色和情况是不同的，情况3得将cur节点修改成为黑色将g节点修改成为红色这里大家得注意一下，好！与之对应的还有这种情况p是g的右孩子，cur是p的左孩子，这种情况的图片就如下：

经过情况一的调整之后图片就变成下面这个样子：

调整节点的指向就变成下面这样：

这个时我们就对节点p实行右旋转就变成下面这个样子：

是不是又变成情况二了对吧，所以对其进行情况二的处理即可但是颜色的修改得改一下。那么这里我们就可以把上面的图片进行简化，变成下面这个样子：

因为情况三是由情况一转换过来的，所以子树a b c d e就不会存在黑色节点不相同的问题，并且a b c子树中黑色节点的数目是相同，子树d和e的黑色节点的数目也是相同的但是比a b c子树的数目少1，经过旋转之后子树d会来到p的下面，p会来到cur的下面，但是这并不会影响每个支路的黑色节点的数量，所以将情况三变成情况二的过程是没有问题的，并且变换之后的树也符合情况二的条件，那么这就是情况三u存在的变化过程，接下来我们来看看u不存在的情况，如果u为空的话子树d和e也一定是为空的，因为不能存在连续的红色节点所以这里的a b c节点也一定为空，那么这里的图片就变成下面这个样子：
那么这里处理方式也是对p节点实行左旋转就变成下面这个样：

那么这是不是就变成情况二了对吧，相反的也是同样的道理这里就不多说了我们待会直接来看代码的实现。

转换的实现

这里我们就紧接着前面的insert函数来写，之前的insert代码如下：

	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 != nullptr)
		{
			if (_kv.first > _parent->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);
		if (_kv.first > _parent->first)
		//如果插入的数据比parent的数据大
		{
			_parent->right = _cur;
			_cur->parent = _parent;
		}
		else
		//如果插入的数据比parent的数据笑
		{
			_parent->left = _cur;
			_cur->parent = _parent;
		}

	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

走到了这里我们的节点就插入到了树里面，那么下面我们就要判断一下节点的颜色是否正确，首先根据前面的讲解我们知道这里的调整大致分为三种，并且第一种的调整会往上影响其他结构，所以这里的修改我们得创建一个循环，如果调整的是情况一的话我们还得循环继续往上调整，如果调整的是情况二或者情况三的话我们调整完就可以直接使用break来结束循环，那么这里的循环条件是什么呢?首先根节点是不用调整的因为它压根就没有啥p节点g节点对吧，所以我们就可以拿p节点来作为判断如果p节点为空的话我们就结束循环那还有吗？答案是肯定还有的，情况一每次调整节点的颜色之后都会修改cur指针的指向并且会让它指向g节点，而g除了根节点都会被调整成为红色，所以cur大概率也会是红色，所以当p节点的颜色也为红色的话这里是不是也得调整啊，所以这里继续调整的情况就是如果父节点为红色并且父节点不为空的话就继续调整，那么这里的代码就如下：

while (_parent != nullptr && _parent->_col == RED)
{

}
1
2
3
4

这里我们就先创建一个grandparent节点，因为这里的调整大体上可以分为对g节点的左边或者右边的节点进行调整，那么这里我们就可以添加一个if语句来创建一个分支那这里的代码就如下：

while (_parent != nullptr && _parent->_col == RED)
{
	Node* _grandparent = _parent->parent;
	if (_grandparent->left == _parent)
		//祖先节点的左边要调整
	{
	}
	else
		//祖先节点的右边要调整
	{
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

祖先节点的左边或者右边进行调整都会分为3种情况，首先来实现情况一，如果u节点存在且为红的话我们就对其进行情况一的调整，那么这里我们就可以创建一个名为uncle的节点然后用if语句判断一下它是否存在即颜色是否为红，那么这里的代码就如下：

while (_parent != nullptr && _parent->_col == RED)
{
	Node* _grandparent = _parent->parent;
	if (_grandparent->left == _parent)
		//祖先节点的左边要调整
	{
		Node* uncle = _grandparent->right;//parent在左边所以uncle在右边
		if (uncle != nullptr && uncle->_col == RED)
		{

		}
	}
	else
		//祖先节点的右边要调整
	{
		Node* uncle = _grandparent->left;//parent在右边所以uncle在左边
		if (uncle != nullptr && uncle->_col == RED)
		{
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

然后调整的方法就是先将p和u节点的颜色改为黑色，然后判断一下g节点是否为根节点，如果不为根节点的话就将其调整为红色，如果为根节点的话就什么不调整它的颜色，最后改变一下cur和p节点的指向，让cur指向g节点让p指向g节点的父亲，那么这里的代码就如下：

while (_parent != nullptr && _parent->_col == RED)
{
	Node* _grandparent = _parent->parent;
	if (_grandparent->left == _parent)
	//祖先节点的左边要调整
	{
		Node* uncle = _grandparent->right;//parent在左边所以uncle在右边
		if (uncle != nullptr && uncle->_col == RED)
		{
			uncle->_col = _parent->_col = BLACK;
			if (_grandparent->parent != nullptr)
			{
				_grandparent->_col = RED;
			}
			_cur = _grandparent;
			_parent = _grandparent->parent;
		}
	}
	else
		//祖先节点的右边要调整
	{
		Node* uncle = _grandparent->left;//parent在右边所以uncle在左边
		if (uncle != nullptr && uncle->_col == RED)
		{
			uncle->_col = _parent->_col = BLACK;
			if (_grandparent->parent != nullptr)
			{
				_grandparent->_col = RED;
			}
			_cur = _grandparent;
			_parent = _grandparent->parent;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

然后我们就要实现情况二的调整办法，实现情况二之前我们首先得左旋转和右旋转这两个函数，那这两个函数我们之前实现过，这里就不多说了，我直接把代码稍微做一些改动放到下面：

//左旋转
void RototalL(Node* _parent)
{
	Node* subR = _parent->right;//右孩子的节点
	Node* subRL = subR->left;//右孩子的左节点
	Node* ppNode = _parent->parent;//祖父节点
	//把subRL放到_parent的右
	_parent->right = subRL;
	if (subRL)
	{
		//如果subRL不为空则修改父节点的指向
		subRL->parent = _parent;
	}
		//把_parent放到subR的左
	subR->left = _parent;
		//修改_parent的parent的指向
	_parent->parent = subR;
	if (ppNode)//如果祖父不为空，则要改变祖父的指向
	{
		if (ppNode->right == _parent)
		{
			ppNode->right = subR;
			subR->parent = ppNode;
		}
		else//如果_parent是祖父的左
		{
			ppNode->left = subR;
			subR->parent = ppNode;
		}
	}
	else//祖父为空节点说明当前调整的是根节点
	{
		root = subR;
		subR->parent = nullptr;
	}
}
//右旋转
void RototalR(Node* _parent)
{
	Node* subL = _parent->left;
	Node* subLR = subL->right;
	Node* ppNode = _parent->parent;
	_parent->left = subLR;
	if (subLR)
	{
		subLR->parent = _parent;
	}
	subL->right = _parent;
	_parent->parent = subL;
	if (ppNode != nullptr)
	{
		if (ppNode->right == _parent)
		{
			ppNode->right = subL;
			subL->parent = ppNode;
		}
		else
		{
			ppNode->left = subL;
			subL->parent = ppNode;
		}
	}
	else
	{
		root = subL;
		subL->parent = nullptr;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

那么情况二可以简略的说成是左左和右右，所以如果cur节点是p节点的左边那么它就在上面的if语句里面，如果cur在p节点的右边那么它就在上面的else语句里面，因为uncle节点的存在与否不会影响我们的调整逻辑，所以这里只需要判断cur和parent的关系即可，那这里的代码就如下;

while (_parent != nullptr && _parent->_col == RED)
{
	Node* _grandparent = _parent->parent;
	if (_grandparent->left == _parent)//祖先节点的左边要调整
	{
		Node* uncle = _grandparent->right;//parent在左边所以uncle在右边
		//情况一
		if (uncle != nullptr && uncle->_col == RED)
		{//...}
		else
		{
			if (_cur == _parent->left)//情况二
			{
			}
		}
	}
	else//祖先节点的右边要调整
	{
		Node* uncle = _grandparent->left;//parent在右边所以uncle在左边
		//情况一
		if (uncle != nullptr && uncle->_col == RED)
		{//....}
		else
		{
			if (_cur == _parent->right)//情况二
			{
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

如果是左左的话我们就对g节点实行右旋转然后修改一下p和g的颜色即可，这里就是将p变为黑色将g改为红色，如果是右右的话我们就对g节点实行左旋转然后修改一下p和g的颜色即可，这里大家别忘了情况那么这里的代码如下：

while (_parent != nullptr && _parent->_col == RED)
{
	Node* _grandparent = _parent->parent;
	if (_grandparent->left == _parent)//祖先节点的左边要调整
	{
		Node* uncle = _grandparent->right;//parent在左边所以uncle在右边
		//情况一
		if (uncle != nullptr && uncle->_col == RED)
		{//...}
		else
		{
			if (_cur == _parent->left)//情况二
			{
				RototalR(_grandparent);
				_parent->_col = BLACK;
				_grandparent->_col = RED;
			}
		}
	}
	else//祖先节点的右边要调整
	{
		Node* uncle = _grandparent->left;//parent在右边所以uncle在左边
		//情况一
		if (uncle != nullptr && uncle->_col == RED)
		{//....}
		else
		{
			if (_cur == _parent->right)//情况二
			{
				RototalL(_grandparent);
				_parent->_col = BLACK;
				_grandparent->_col = RED;
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

如果情情况二不成立的话就只能来到了情况三所以这里直接用else语句即可，那么对于左右的情况我们直接先对p节点使用向左旋转然后再对g节点向右旋转，最后修改cur和g的颜色即可，将cur修改成为黑色将g修改成为红色，那么与之相反的就是右左情况这里就是先对p节点实行向右旋转，然后再对g节点实行向左旋转，最后修改一下颜色即可，这里大家别忘了当情况二和三执行结束之后得用break来结束循环，那么这里的代码就如下：

if (_grandparent->left == _parent)//祖先节点的左边要调整
{
	Node* uncle = _grandparent->right;//parent在左边所以uncle在右边
	//情况一
	if (uncle != nullptr && uncle->_col == RED)
	{//....}
	else
	{
		if (_cur == _parent->left)//情况二
		{//....}
		else//情况三
		{
			RototalL(_parent);
			RototalR(_grandparent);
			_cur->_col = BLACK;
			_grandparent->_col = RED;
		}
		break;
	}
}
else//祖先节点的右边要调整		
{
	Node* uncle = _grandparent->left;//parent在右边所以uncle在左边
	if (uncle != nullptr && uncle->_col == RED)//情况一
	{//...}
	else
	{
		if (_cur == _parent->right)//情况二
		{//...}
		else//情况三
		{
			RototalR(_parent);
			RototalL(_grandparent);
			_cur->_col = BLACK;
			_grandparent->_col = RED;
		}
		break;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

那么insert函数的完整代码就如下：

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 != nullptr)
	{	
		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);
	if (_kv.first > _parent->kv.first)
	//如果插入的数据比parent的数据大
	{
		_parent->right = _cur;
		_cur->parent = _parent;
	}
	else
	//如果插入的数据比parent的数据笑
	{
		_parent->left = _cur;
		_cur->parent = _parent;
	}
	while (_parent != nullptr && _parent->_col == RED)
	{
		Node* _grandparent = _parent->parent;
		if (_grandparent->left == _parent)
			//祖先节点的左边要调整
		{
			Node* uncle = _grandparent->right;//parent在左边所以uncle在右边
			//情况一
			if (uncle != nullptr && uncle->_col == RED)
			{
				uncle->_col = _parent->_col = BLACK;
				if (_grandparent->parent != nullptr)
				{
					_grandparent->_col = RED;
				}
				_cur = _grandparent;
				_parent = _grandparent->parent;
			}
			else
			{
				//情况二
				if (_cur == _parent->left)
				{
					RototalR(_grandparent);
					_parent->_col = BLACK;
					_grandparent->_col = RED;
				}
				else//情况三
				{
					RototalL(_parent);
					RototalR(_grandparent);
					cur->_col = BLACK;
					_grandparent->_col = RED;
				}
				break;
			}
	}
	else
	//祖先节点的右边要调整
	{
		Node* uncle = _grandparent->left;//parent在右边所以uncle在左边
		//情况一
		if (uncle != nullptr && uncle->_col == RED)
		{
			uncle->_col = _parent->_col = BLACK;
			if (_grandparent->parent != nullptr)
			{
				_grandparent->_col = RED;
			}
			_cur = _grandparent;
			_parent = _grandparent->parent;
		}
		else
		{
			//情况二
			if (_cur == _parent->right)
			{
				RototalL(_grandparent);
				_parent->_col = BLACK;
				_grandparent->_col = RED;
			}
			else//情况三
			{
				RototalR(_parent);
				RototalL(_grandparent);
				cur->_col = BLACK;	
				_grandparent->_col = RED;
			}
			break;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

打印函数

我们知道搜索二叉树中序遍历的结果是有序的，所以我们这里就可以写一个中序遍历的函数来打印二叉树的内容，首先这个函数是没有返回值的，我们在函数运行的过程中就将函数的内容打印完成了，其次这个函数需要一个参数，因为递归需要知道节点，所以这个函数的参数就是一个Node的指针，二叉树的前中后序遍历想必大家都已经非常的熟悉了，那这里我们就直接上代码：

	void _inorder(const Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_inorder(root->left);
		cout << root->kv.first << " "<< root->kv.second<<endl;
		_inorder(root->right);
	}
1
2
3
4
5
6
7
8
9
10

但是这里存在一个问题，这个类的使用能够传递参数root吗？好像不能吧root的属性是private，所以如果这个函数有参数的话使用者是无法进行传参的，那这里就存在两个常见的解决方法一个是再创建一个函数，这个函数的功能就是放回root的值，另外一个就是直接将root的属性变成public，由于这两个方法的风险比较大，开放了root就意味着使用者可以直接根据root的值修改树的内容 ，所以我们采用另外一种方法，在类外无法使用root的值，但是在类里面我们是可以使用root的值的，所以我们可以创建一个函数这个函数对于使用者来说是可以执行一些功能的，但是对于我们来说这个函数就是一个空壳子，我们把需要传参的函数放到private里面然后通过这个空壳函数进行调用不就可以了吗，这样使用者即无法通过root来修改里面的内容，也不用担心传参的问题，那这里的代码就如下：

public：
	void inorder()
	{
		_inorder(root);
	}
private:
	void _inorder(const Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_inorder(root->left);
		cout << root->key <<" ";
		_inorder(root->right);
	}
	Node* root;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

find函数

有了上面的insert函数那么要想实现查找函数就十分的简单，首先find函数的返回类型是bool类型，如果要查找的元素存在的话就返回true，如果要查找的元素不存在的话就返回false，然后find函数的参数也是K类型的参数，那这里的代码就如下：

	bool find(const K& val)
	{

	}
1
2
3
4

这里实现的思路差不多，首先创建一个Node类型的指针cur将其值初始化为root，因为这里要进行多次查找所以我们创建一个while循环，在循环体里面我们就用cur里面的key和val进行比较，如果key的值大于val的话就让cur往左边跑，如果key的值小于val的话就让cur往右边跑，key和val的值相等的话就返回true，如果cur的值为空的话我们就结束循环然后返回false来结束这里的函数，那么这里的代码就如下：

	bool find(const K& val)
	{
		Node* cur = root;
		while (cur)
		{
			if (cur->kv.first == val)
			{
				return true;
			}
			else if (cur->kv.first > val)
			{
				cur = cur->left;
			}
			else
			{
				cur=cur->right;
			}
		}
		return false;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

检查函数

红黑树的is_balance和avl的is_balance的原理是不一样的。首先根节点不等于黑就自己返回错误，然后检查是否有连续的红节点，那么这里检查的方法就是如果当前的节点为红就检查他的父节点是否也为红，之所以不检查子节点是因为子节点可能会不存在。首先在递归额度外层创建一个变量ref和循环用于记录一条支路的黑色节点的数目，然后再递归的时候我们就把这个ref传递过去，然后函数的参数里面再添加一个sum，每次递归的时候如果当前节点为黑色的话就对这个sum变量加一，如果遇到空节点的话就进行一下比较如果ref和sum不想等额度话就说明当前的支路出现了问题。通过上面的三个判断条件就可以确定我们当前实现的红黑树是否是正确的，这里也可以通过在结构体里面添加一个变量来记录当前路劲的黑色节点数量，但是这种方法实现的效率太差了，因为这个变量就用于判断红黑树实现的对不对，在其他的方法上用不上，而且每个节点上都会存在这么个变量就会导致效率下降，那么这里的检查函数就如下：

bool check(Node* root, int BlackNums, int ref)
{
	if (root == nullptr)
	{
		if (ref != BlackNums)
		{
			cout << "违反规则" << endl;
			return false;
		}
		return true;
	}
	if (root->_col == RED && root->parent->_col == RED)
	{
		cout << "出现了连续红色节点" << endl;
	}
	if (root->_col == BLACK)
	{
		BlackNums++;
	}
	return check(root->left, BlackNums, ref) && check(root->right, BlackNums, ref);
}
bool IsBalance()
{
	if (root == nullptr)
	{
		return true;
	}
	if (root->_col != BLACK)
	{
		return false;
	}
	int ref = 0;
	Node* _left = root;
	while (_left)
	{
		if (_left->_col == BLACK)
		{
			ref++;
		}
		_left = _left->left;
	}
	return check(root, 0, ref);

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

那么有了这个函数之后我们就可以用下面代码来测试一下我们写的代码是否正确：

int main()
{
	srand(time(0));
	const size_t N = 100000;
	RBTree<int, int> t;
	for (size_t i = 0; i < N; ++i)
	{
		size_t x = rand();
		t.insert(make_pair(x, x));
	}
	cout << t.IsBalance() << endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

这段代码的运行结果如下：

那么这就说明我们的代码实现的是正确的，没有什么太大的问题，那么这就是本篇文章的全部内容希望大家能够理解，对于删除函数这里就不做讲解。