c++进阶——红黑树的实现

红黑树的实现

继承上文，我们实现了AVL树。AVL树是通过严格的控制每一个子树的左右高度差来保证树的平衡，但是STL库中的容器map系列和set系列其实底层并不是AVL树，而是红黑树。既然这样为什么要先讲AVL树呢？是因为AVL树可以认为是实现红黑树的前提(针对于里面的旋转操作)。

在AVL树中我们重点讲解了旋转的方式，所以这篇文章对于旋转的具体细节就不会再过多赘述，点到即可。如果直接上来就讲红黑树，里面涉及的旋转操作时非常抽象晦涩的。学习最讲究的就是循序渐进，所以先学会AVL树再来学习红黑树时百利而无一害的。

现在进入本文正文部分——红黑树的实现。红黑树的规则是非常抽象的，需要我们好好理解。

红黑树的概念

红黑树是一棵二叉搜索树，他的每个结点增加一个存储位来表示结点的颜色，可以是红色或者黑色。通过对任何⼀条从根到叶子的路径上各个结点的颜色进行约束，红黑树确保没有⼀条路径会比其他路径长出2倍，因而是接近平衡的。

在这里我们需要说明一下路径这个概念，举个例子来说：

就比如这个红黑树，当然规则我们先不管。

很多人会不假思索的说，路径有5条。这是不对的。
树的路径的规定是：从整个树的根节点走到一个空节点的唯一路径。
也就是计算路径条数的时候，我们需要看看有几个空节点。在这个树中，应该是有9条路径：

按照这个图来就很好理解了。当然有些书籍或者教材上可能在图中写null的位置放上一个叫NIL的叶子节点。注意，这里的叶子节点并非我们常说的叶子节点，而是特指红黑树中的叶子节点。但是本篇文章中不使用这个说法。

红黑树的规则

了解完红黑树是什么后，就得了解一下红黑树的规则。

红黑树的规则有如下四条：

1. 每个结点不是红色就是黑色
2. 根结点是黑色的
3. 如果一个结点是红色的，则它的两个孩子结点必须是黑色的，也就是说任意一条路径不会有连续的红色结点。
4. 对于任意一个结点，从该结点开始，在以这个节点为根节点的子树走到所有NULL结点的简单路径上，均包含相同数量的黑色结点。

我们来稍微解释一下：
第一条是必然的，注意不能出现第三种颜色即可。第二条意思是说，整个树的根节点必须是黑色的。而不是保证每个子树的根节点是黑色的。如果是保证每个子树的根节点为黑色，那整棵树都是红色的树了，何来红黑树一说呢？

第三点意思就是，对于某个节点和其父亲节点的关系(如果有)，除了不能是二者都为红色，其他都可以。所以这也就是为什么一条路径上不能出现连续的两个红色节点。

第四点是非常重要的，可以说加上第四点后，这四条规则直接奠定了红黑树这个数据结构为什么能够有比较高的效率。这个点的意思是说，对于每个子树(包括整个树)，从根节点走到这个子树的空节点对应的全部路径来说，每一条路径的黑色节点数量是一样的。
最后得出的结论就是，每个子树的路径黑色节点个数相同。

我们来看看几个比较标准的红黑树：

在这里就不逐个对照红黑树规则了。感兴趣的读者可以自己验证一下。这些都是标准的红黑树，都是严格满足红黑树的要求的。

红黑树性能分析

我们现在来一起分析一下红黑树的性能。

控制最值路径长度之差

这几点规则是如此抽象，我们肯定是搞不明白为什么天才们能创造出这些东西的。但是我们只需要学会使用和分析就可以了。

我们现在会很自然而然的思考，为什么根据这四点规则就能控制前面说到的，最大路径不会超过最小路径的2倍数呢？
我们还是要从红黑树的四点规则进行分析，只不过说前两点是不需要关注的。

首先得知道怎么样找到最小路径和最大路径。我们来想一下最小路径是什么？结合规则来看，说一条路径上不能出现连续的两个红色节点，但是一旦有一个树在又是路径必然有黑色节点的(根节点)。每条路径上黑色节点个数又相同。所以我们就推测出一个极端场景：即一个树的最短路径是全为黑色节点的路径，这条路径长度假设为bh(black height)。

那最长的路径呢？我们肯定知道这条最长路径的黑色节点个数为bh了(规则四)，那如果多些红色节点不就变长了嘛?但是不是可以无限增加红色节点的。要满足规则三——不能出现连续红色节点，根节点又是黑的。那怎么样加入能添加最大数量的红色节点呢？那就只能一黑一红的串着，这样又会有bh个红色节点。那最长路径上就是2bh个节点(一半黑，一半红)。然后发现无论如何也是不能再添加红色节点和黑色节点了。再添加就需要对这个红黑树进行调整了。

所以经过上面的一通分析发现，最长路径也就最多是最短的2倍。但是这个极端场景是很难出现的。也可以说几乎出现不了。所以整个红黑树的高度差并不会有那么离谱的差异。这里只是观测一下极端情况下的红黑树。

效率问题

相比于AVL树这种严控左右子树高度的树来说，红黑树自然是没有AVL树那般平衡的。但是其实二者在性能上差异并不是太大，同属一个量级。且红黑树在实际应用中使用的更为广泛。

我们就以极端情况来举例，假设某个红黑树节点数为N，h为最短路径长度。
我们之前算过，一个满二叉树前h层的个数必然是（2^{h + 1} - 1）个。

那N的个数必然是（2^h - 1 ~ 2^2h - 1）之间。这里稍微解释一下，即大于h - 1层满二叉树节点的个数，小于2h - 1层的满二叉树节点个数。

大致推算一下h与N的关系仍是h = log₂N，还是对数级别。实际上在数据量特别大的时候，红黑树和AVL的数高度之差可能也就是几十层的差距。在这种对数级别的效率下其实影响并不是太大。所以红黑树的搜索效率就是O(LogN)级别的。所以效率也很高。

红黑树与AVL树的区别

红黑树的表达相对AVL树要抽象一些，AVL树通过高度差直观的控制了平衡。红黑树通过4条规则的颜色约束，间接的实现了近似平衡，他们效率都是同一档次，但是相对而言，插入相同数量的结点，红黑树的旋转次数是更少的，因为他对平衡的控制没那么严格。

红黑树的代码实现

这个部分我们来重点讲解一下红黑树。注：删除操作由于面试等环节考的较少。并不是重点。在这里就先和AVL树一样先不实现删除操作了。重点将放在插入流程的讲解上。待以后有空可能会把删除操作一并补上。

红黑树代码框架

根据规则，我们先搭好一个框架，实现一些基础的功能方便我们测试使用：

enum color
{BLACK,RED
};template<class K, class V>
struct RBTreeNode {pair<K, V> _kv;color _col;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;RBTreeNode(const pair<K, V>& kv) :_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED) {} 
};template<class K, class V>
class RBTree {
public:using Node = RBTreeNode<K, V>;  Node* Find(const K& k) {  Node* cur = _root; while (cur) {if (k > cur->_kv.first) cur = cur->_right; else if (k < cur->_kv.second)cur = cur->_right;  else return cur;}return nullptr; }void InOrder() { _InOrder(_root);cout << endl;}int Height() {return _Height(_root);}int Size() {return _Size(_root);}private: //中序遍历void _InOrder(Node* root) {if (root == nullptr) return;_InOrder(root->_left); cout << root->_kv.first << " : " << root->_kv.second << endl;_InOrder(root->_right); }int _Height(Node* root) {if (!root) return 0;size_t LHeigth = _Height(root->_left);size_t RHeigth = _Height(root->_right);return (LHeigth > RHeigth) ? LHeigth + 1 : RHeigth + 1;}//旋转代码 有用void RotateR(Node* parent) {//右单旋其实就是把cur的右孩子给parent作为左孩子//再让cur作为根节点 parent作为cur的右孩子//还得修改一下被改动节点的_parent指针指向//然后需要将新的子树根节点与原来指向此子树的根节点的节点进行链接Node* Parent = parent;Node* subL = parent->_left;Node* subLR = subL->_right;Node* P_Parent = Parent->_parent;Parent->_left = subLR;//subLR可能为空 所以需要判断if (subLR != nullptr) subLR->_parent = Parent;subL->_right = Parent;Parent->_parent = subL;//链接原来的AVLTree//但是这时候有一个问题 即原来的子树根节点的父亲P_Parent可能是空//(对应此时Parent是整个树的根节点)if (Parent == _root) {_root = subL;subL->_parent = nullptr;}else {//此时的新根节点subL不知道是应该插入在P_Parent的左边还是右边 需要判断一下if (P_Parent->_left == Parent) P_Parent->_left = subL;else P_Parent->_right = subL;subL->_parent = P_Parent;}}void RotateL(Node* parent) {Node* Parent = parent;Node* subR = Parent->_right;Node* subRL = subR->_left;Node* P_Parent = Parent->_parent;Parent->_right = subRL;if (subRL != nullptr) subRL->_parent = Parent;subR->_left = Parent;Parent->_parent = subR;if (Parent == _root) {_root = subR;subR->_parent = nullptr;}else {if (P_Parent->_left == Parent) P_Parent->_left = subR;else P_Parent->_right = subR;subR->_parent = P_Parent;}}int _Size(Node* root) {if (!root) return 0;return _Size(root->_left) + _Size(root->_right) + 1;}Node* _root = nullptr;   
};

这个部分实现的是key_value版本。当然STL库中不是这么干的。但是这是下个部分的内容。当前的重点是如何把一个红黑树的插入操作手撕出来。

在这里有一些细节我们来讲一下。红黑树的颜色我们可以使用自定义的枚举类型。当然也可以使用bool值来控制。都可以。但是为了更加生动形象一些我选择了自定义枚举。

这里也出现了一些旋转代码，这是有用的。我们先保留在这。只不过要去掉最后的更新平衡因子部分。双旋的代码就不拷贝过来了，因为双旋的本质是两次单旋。

现在还面临着一个问题就是，新插入的节点给黑色还是给红色好呢？这里一定要默认为红色。
如果默认插入黑色就麻烦了。本来一颗好好的红黑树，每条路径上的黑色节点个数就是一样的。如果默认插入的是一个黑色的节点，那无论插在哪条路径上，都会导致那条路径相比于其他路径多出了一个黑色节点。这时候就需要根据红黑树规则去调整这个树。但是这样子调是很复杂的，很难控制的住。代价特别大。

但插入红色节点就不一样了，如果父亲为黑色节点，那直接插入是一点毛病没有。不会破坏原有性质。如果父亲是红色，只需要进行一些适当的操作就好了。本质上对于每条路径上的黑色节点个数还是一样的。这些具体的操作就是我们后面要讲的插入流程。所以在这里得出结论：
红黑树新插入的节点必须是红色的！

红黑树的插入流程

先来看主要的流程：
插入一个值按二叉搜索树规则进行插⼊，插入后我们只需要观察是否符合红黑树的4条规则。本质上遵循的逻辑就是和AVL树一样的，先插入，后调整。

1. 如果是空树插入，新增结点是黑色结点。如果是非空树插入，新增结点必须红色结点，因为非空树插入，新增黑色结点就破坏了规则4，规则4是很难维护的。
2. 非空树插入后，新增结点必须红色结点，如果父亲结点是黑色的，则没有违反任何规则，插入结束
3. 非空树插入后，新增结点必须红色结点，如果父亲结点是红色的，则违反规则3。进⼀步分析，c是红色，p为红，g必为黑，这三个颜色都固定了，关键的变化看u的情况，需要根据u分为以下几种情况分别处理。

说明：下图中假设我们把新增结点标识为c (cur)，c的父亲标识为p(parent)，p的父亲标识为
g(grandfather)，p的兄弟标识为u（uncle）

调整操作

现在我们来正式分析一下如何进行调整：

这里相比于AVL树会更加抽象一点。但是具体的插入情况其实已经被整理成三种情况了。我们来一起看一下。

我们要知道何时才需要调整，即父亲节点和新插入节点都是红色时候就需要进行调整了。所以我们这里下面对应的所有的调整情况都是父亲§为红色的时候。在这里为了能更简便的说明，将对涉及到的节点进行标识替代。

所以插入节点后进入调整状态下，c一定指向的是红色节点，p也是红色。插入前又是一个平衡的红黑树，所以g(p的父亲节点)一定是黑色。否则就违反了规则三。那这个时候u节点是不知道是什么个情况的。有可能是红，有可能是黑，甚至可能不存在。所以在这里我们初步得出一个结论就是，红黑树的调整方式取决于叔叔节点(u)。

1.u存在且为红色节点，单纯变色操作
还是给几个图来看看：

比如这个情况，新插入一个红色节点x在6的左边。那应该怎么调整呢？很简单，把p和u节点都变成黑色的，再把g节点变成红色的就可以了。

这个情况也是如出一辙。但是这里出现了一个问题，如果变色的过程中根节点被调为红色怎么办呢？这个十分好办，代码的最后部分你强制把根节点变成黑色不就好了。就算被调整为红色，整个树被调整后是平衡的。把根节点位置变为黑不就是在每条路径上都加入一个黑色节点吗？这并不违反规则。所以可行。

但是我们举例的这些图还是太简单了，有没有可能需要调整多次呢？
我们先来看抽象图：
此时c如果不是插入的节点，那必然是黑色的，否则c此时就是红色的。那就直接在这里调整了。但是现在abcde这五个子树到底是个什么状况我们也是不清楚，我们举几个例子看看：

第一种情况就是abcde一开始均为空，然后插入一个新的cur。这个时候执行变色操作。

第二种情况：

此时def中各有一个黑色节点，也就是子树中每条路径黑色节点个数hb == 1，这个时候c必然不是新的插入节点。因为新插入节点的话c为红色，且没有子树。这样子每条路径下的黑色节点数量不一样了。所以在插入新节点前，cur必然是黑色。如果要出现在cur处就有红色父亲和红色叔叔的情况，那必然是需要从下面调整上来。

图中也分析过了，这种状况对应的种类有256种。

我们再来看看cde三个子树种有两个黑色节点的情况：

如果子树中有两个黑色节点，那情况可就多了去了。图中蚊子解析已经解释了为何有如此多的种类。我们发现，对应cur这个位置，还是一样的执行变色操作。只不过区别就在于cur到底是新加入的节点还是调整上来的节点。

h == 2的情况下都这么多情况了，那其它的情况其实是很难再来详细的举例分析了。但是我们不太需要关注这些这么细节的东西。我们只需要关注局部就好了。所以在这个部分来讲，只要叔叔节点u存在，那就将u和p节点均变为黑色，g变成红色，不断向上调整到根就可以了。

2.u不存在或者存在且为黑色节点，变色 + 旋转
我们已经分析完了叔叔节点存在且为红色了，但是其他情况呢？
在这里我们均以p为g的左孩子，u为g的右孩子来举例。反方向其实类似，就不进行举例了。

//    g
//  p   u
//c在p的左边或者右边

假设p在c的左边：

1. u不存在
   如果u不存在，也就是g不存在右子树。那么对于g子树来讲，只有g这么一个黑色节点。p一定是红的，c也是红的。故得知c是新插入的节点：
   
   如这个图所示，很明显，直接对g节点进行右旋操作后，再把p变为黑，g变为红就可以了。旋转操作的代码早在AVL树实现部分就已经有了，所以可以直接复用。

2. u存在且为黑色
   这种情况c必然不是新插入节点。原因是一样的，就是u为黑色，那么如果c为新插入节点又不满足规则四了。所以c必然是通过调整上来变成红色的，这个时候怎么办呢？
   
   我们直接以抽象图来看了，因为具体展开的时候情况很多种，但其实都满足这个道理。

此时经过多次调整后，c变为红色，p为红色，需要进行调整，但是u为黑色。其实操作还是一样，继续对g进行单旋操作即可，还是让g变为红色，p变为黑色。

也就是说，对于u不存在或者存在为黑的情况其实是一样的。

假设p在c的右边：
我们现在看到了，这种是单旋的操作。有没有可能进行双旋呢？当然有：

如果此时c在p的右边呢，经过画图分析，经过单旋操作时不会成功，仅仅是把连续的红色节点从左边换到了右边去。在这里我并没有进行展示。稍微分析一下就可知道。

这个时候就应该启用双旋操作。先对p节点进行左单旋，再对g进行右旋操作。也可以直接从双旋的本质来看。在这个图中，双旋的本质就是c的左边给p的右边，c的右边给g的左边，p和g分别充当c的左边和右边。

那这个时候，c就充当了根节点了，就不能再让p变成黑色了，而是应该让c变成黑色。然后因为双旋后，g这个原本黑色的根节点被旋转到右边去，会导致右边的子树多出一个黑色节点，所以还是需要将g节点变成红色的。

如果实在搞不明白就看这个最简单的情况进行推广就可以了。还是一样的，u无论是黑色节点还是不存在，都是一样的操作。因为旋转的操作会把u的高度往下降一层，不会涉及到它的操作。所以这点需要我们注意一下。

当然我们上面讲的全是叔叔节点在右边的。实际上还有在左边的。但是原理都是一样的，只不过说针对于某些部分需要取反一下逻辑而已。就不赘述了。

调整操作的总结

经过一通分析，最后发现其实调整的关键就是叔叔节点u。我们的所有调整逻辑都是基于它来干的。

叔叔节点为红色，那就需要不断地向上调。但是每一次调整的逻辑可能会各不相同。因为不确定叔叔节点到底是什么情况。所以需要判断。

当u为红色，就执行单纯的变色操作。但是变色操作没办法保证变色完后，新的c节点和p节点不是连续的红色。所以还需要继续判断。

但是对于u为黑色或者不存在的情况，我们需要进行旋转操作(单旋或者双旋)，一旦经过旋转了，那么会让旋转后放在根部的节点变成黑色。那不管这个新的根节点的父亲节点是什么颜色，都是满足红黑树的规则的。因为没有出现两个连续的红色节点。并且还成功的把高度降了下来。而且被旋转的那部分子树也没有额外增加黑色节点的个数，子树中每条路径的黑色节点数也通过变色操作给控制想同了。所以碰到需要旋转的时候，直接就旋转一次就可以保证这个红黑树的平衡了。

这些是我们需要注意的东西。

代码展示

现在来直接看代码：

bool Insert(const pair<K, V>& kv) {if (_root == nullptr) {_root = new Node(kv);//根节点需要为黑色 但是默认插入的节点是红色_root->_col = BLACK;return true;}//先按照二叉树的逻辑插入Node* parent = _root, * cur = _root; while (cur) { if (kv.first > cur->_kv.first)   cur = cur->_right; else if (kv.first < cur->_kv.first)  cur = cur->_left; else return false;if (cur) parent = cur; }//此时cur指向被插入的位置 parent指向被插入位置的父亲节点cur = new Node(kv); if (kv.first > parent->_kv.first) parent->_right = cur; else parent->_left = cur;  cur->_parent = parent; //根据红黑树的规则来调整这个树//此时cur指向被插入节点 parent指向其父亲节点while (parent && parent->_col == RED) {Node* grandfather = parent->_parent; //  g// p u// c在p的左边或者右边 if (parent == grandfather->_left) {Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED) {//这种情况只需要变色 不断向上调整就可以了(uncle存在且为红)parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续向上调整cur = grandfather; parent = cur->_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;}}// g//u  p//c在p的左边或者右边else {Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED) { //这种情况只需要变色 不断向上调整就可以了(uncle存在且为红)parent->_col = uncle->_col = BLACK; grandfather->_col = RED; //继续向上调整cur = grandfather;  parent = cur->_parent;  }else {//此时叔叔不存在或者存在且为黑色if (cur == parent->_right) {// g//u  p//     c//此时需要进行单旋 + 变色 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->_col = BLACK; return true;}

这里的代码有对刚刚的情况的注释，只需要对照前面讲的调整逻辑进行操作就可以了。

红黑树的平衡测试

当然写完之后最好是进行一下测试。主要就是测试一下这个树中序遍历是否正确，是否平衡，搜索效率等，节点数量是否计算正确等。

框架中基本上覆盖了这些代码，在这里我只介绍一下如何进行平衡测试。

AVL树的平衡测试思路比较简单，就是测算一下某个子树的左右子树高度之差是否小于等于1。只不过根据效率选择来看从上往下算还是从上往下算而已。但是红黑树的检测是不太一样的。红黑树是根据那四条规则来进行判断的：

1. 每个结点不是红色就是黑色
2. 根结点是黑色的
3. 如果一个结点是红色的，则它的两个孩子结点必须是黑色的，也就是说任意一条路径不会有连续的红色结点。
4. 对于任意一个结点，从该结点开始，在以这个节点为根节点的子树走到所有NULL结点的简单路径上，均包含相同数量的黑色结点。

其中第一第二条判断其实很简单。第一条其实都可以不用管。现在问题就是，第三第四点这两个应该怎么来判断？

第三条正常来说就是，遍历到一个节点，就判断一下这个节点是否为红色。如果为红色的情况下判断一下左右节点是否有红色。如果是黑色或者不存在可以不管。但是这样写十分麻烦。因为树从上往下走是一对多的关系。我们能不能网上查找呢？网上查找不就简单多了，只需要看下父亲节点是否为红即可。当然是可以的。因为我们实现的二叉树其实更详细来说是三叉链。有一个指向父亲节点的指针。

所以只需要判断一下自己为红色时候父亲是否为红色就可以了。可能会有疑问说，如果父亲为空怎么办？这点也是不用怕。因为没有父亲节点的节点就是树根，树根一定是黑色的。如果是非黑的提前判断一下就可以了。

第三点就被解决了，最难的就是第四点，怎么样判断每条路径的黑色节点数是否相同呢？特别是我们使用递归写法的情况下其实是很难控制的。

这个时候就得使用传入一个基准值。我们就假设当前这个红黑树每条路径的黑色节点相同。那就随便找一条路径上的黑色节点数作为基准值就好了。这个基准值不能被修改，作为一个const常量传入函数中。然后我们可以通过递归的前序遍历，碰到黑色节点就记录一次。那就得再传入一个变量记录当前算到的黑色节点数。

然后走到空的时候，比较一下记录的黑色节点数和基准值是相同。如果不相同就说明一定有=不平衡。如果能够每一次比较都相同，那就是平衡的：

public:
bool IsBalance() {//处理空树if (_root == nullptr)return true;//根为红色也不行if (_root->_col == RED)return false;//计算基准值Node* pcur = _root;int standard = 0;while (pcur) {if (pcur->_col == BLACK)++standard;pcur = pcur->_left;} return _IsBalance(_root, 0, standard);       
}private:
bool _IsBalance(Node* root, int BlackNum, const int BlackNumStandard){ if (root == nullptr) {if (BlackNum != BlackNumStandard) {cout << "每条路径上的黑色节点个数不相同" << endl;return false;}else return true;}if (root->_col == RED && root->_parent->_col == RED) {cout << "出现连续的两个红色节点" << endl;return false;}if (root->_col == BLACK)++BlackNum;return _IsBalance(root->_left, BlackNum, BlackNumStandard) && _IsBalance(root->_right, BlackNum, BlackNumStandard);}

这个时候就有人会问了，既然BlackNum记录的是当前计算到的黑色节点数。那一直传进去不是被改动了嘛？退回来的时候还能是原来的值嘛？

答案是当然的。这里的BlackNum是函数的形参，每个函数调用都要开辟函数栈帧。每个栈帧中都有独立的BlackNum，记录的是不同状态下记录的黑色节点个数。退回去后，就是找回原来那个栈帧，那不还是那个变量吗，没有改动。

很多人觉得被改变是因为见过一种用法，确实能将这个改变。就是传地址。我们这里的BlackNum是通过外界main函数传的0来衍生出来的。但是如果外面是这样做的：

int x = 0;
return _IsBalance(_root, &x, standard);

如果第二个参数修改为int*类型，外界传地址，那就会被改变了。因为此时这个地址指向的变量是开辟在main函数栈帧的，而不是这里的_IsBalance函数的栈帧。每一次修改都是通过传入的这个地址进行修改，那自然而然会影响到外界的变量。但是我们这里的第二个参数是int类型。这就是本质的区别。所以退回去原来那个栈帧后，BlackNum的状态其实没有被改变。

//插⼊⼀堆随机值，测试平衡，顺便测试⼀下⾼度和性能等
#include<vector>
void TestAVLTree2()
{const int N = 100000;vector<int> v;v.reserve(N);srand(time(0));for (size_t i = 0; i < N; i++){v.push_back(rand() + i);}size_t begin2 = clock();RBTree<int, int> t;for (auto e : v){t.Insert(make_pair(e, e));}size_t end2 = clock();cout << "Insert:" << end2 - begin2 << endl;cout << t.IsBalance() << endl;cout << "Height:" << t.Height() << endl;cout << "Size:" << t.Size() << endl;size_t begin1 = clock();// 确定在的值/*for (auto e : v){t.Find(e);}*///随机值for (size_t i = 0; i < N; i++){t.Find((rand() + i));}size_t end1 = clock();cout << "Find:" << end1 - begin1 << endl;
}int main() {TestAVLTree2();return 0;
}

还是拿这个随机测试的代码进行测试一下就可以了：

效率还是非常高的，而且也是平衡的。