数据结构——红黑树的实现

1>.每个节点不是红色就是黑色。

2>.根节点是黑色的。

3>.如果一个节点是红色的，则它的两个孩子节点必须是黑色的，也就是说任意一条路径不会由连续的红色节点。

4>.对于任意一个节点，从该节点到其所有的空节点的节点路径上，均包含相同数量的黑色节点。（注：红黑树的路径数目是指从根节点到空节点的路径数目）

说明：《算法导论》等书籍上补充了一条每个叶子节点（NIL）都是黑色的规则。他这里是所指的叶子节点不是传统意义上的叶子节点，而是我们所说的空节点，有的书籍上也把NIL叫做外部节点。NIL是为了能够方便且准确地标识出所有的路径，《算法导论》在后续讲解实现地细节中也忽略了NIL节点，所以我们这里知道一个这个概念即可。

1.2 红黑树是如何确保最长路径不超过最短路径的2倍的？

1>.由规则4可知，从根到NULL节点的每条路径都有相同数量的黑色节点，所以在极端场景下，最短路径就是全是黑色节点的路径，假设最短路径长度为bh(black height)。

2>.有规则2和规则3可知，任意一条路径不会有连续的红色节点，所以极端场景下，最长的路径就是一黑一红间隔组成，那么这样的话最长路径的长度为2*bh。

3>.综合红黑树的4点规则而言，理论上全黑路径和一黑一红的最长路径并不是在每棵红黑树中都是存在的。假设任意一条从根到NULL节点路径的长度为x，那么bh=<x=<bh。

1.3 红黑树的效率

假设N是红黑树中节点的数量，h是最短路径的长度，那么2^n-1=<N=<2^2n-1，由此便可推断出h=logN，既然这样也就意味着红黑树的增删查改（改指的是修改value，并非是关键字key）最坏的也就是走2*logN，那么这样的话时间复杂度就还是O(logN)。

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

2 红黑树的实现

2.1 红黑树的结构

enum colour//红黑树中的每个节点它不是黑色的就是红色的，这里我们为了表示节点的颜色显得方便，再结合枚举的特点刚好满足我们在这里的这个需求，由此我们在这里使用枚举来定义颜色变量。
{RED,//1BLACK//2
};
//我们这里默认按照key/value的发生来实现。
template<class K,class V>
struct RBTreeNode//通过我们前面对二叉搜索树结构的了解我们可以得知，一棵二叉树是由许许多多的节点构成的，而这些节点是由各个指针连接起来的，由此我们这里要提前先写一个节点的结构，我们实际上后面在实现红黑树里面的各种操作时，要访问节点里面的各个元素变量，由此建议用struct。
{pair<K, V> _kv;//节点里面存放到元素。这里我们先来假设节点里存放的是pair类类型的变量(实际上存放的不一定是这个，具体是什么，下一章会讲到)。RBTreeNode<K, V>* _left;//指向左子树的指针。RBTreeNode<K, V>* _right;//指向右子树的指针。//红黑树这里也要更新平衡也需要加入parent指针(后面讲插入时会用到)RBTreeNode<K, V>* _parent;//指向这个节点的父亲节点。colour _col;//表示当前这个节点的颜色，这个变量只能被赋予RED或BLACK。(这里补充一个知识:枚举在定义类型时可以不加enum这个关键字)RBTreeNode(const pair<K,V>& kv):_kv(kv),_left(nullptr),_right(nullptr)_parent(nullptr){ }//这里我们不给_col变量赋初始值，是因为不知道插入到这个节点为何颜色，若插入的节点为根节点，则此节点的颜色为黑色，反之，为红色，至于为什么插入的节点若不是根节点的话，那它的颜色就一定是红色，后面会对这个问题进行讲解。
};

template<class K,class V>
class RBTree
{typedef RBTreeNode<K, V> node;//为了后续方便书写。
public://...
private:node* _root = nullptr;//定义一个指针指向根节点。
};

2.2 红黑树的插入

2.2.1 红黑树插入节点的大概过程

1>.插入一个值按二叉搜索树的规则进行插入操作，插入之后我们只需观察是否符合红黑树的4条规则。

2>.如果被插入的树是一棵空树的话，那么插入的这个节点就是根节点，由规则2我们可知，这个新增节点的颜色是黑色的。但如果被插入的树是一棵非空树的话，那么这个新增节点就只能且必须是红色节点，因为通过规则4可知，红黑树的所有路径中黑色节点的数量是相同的，这里其实间接地隐藏了一个条件，就是这里插入节点，既然可以插入，就说明在插入之前，这棵树就已经是红黑树了，其中的每条路径上地黑色节点地个数均是相同的，如果我们此时新插入一个黑色节点的话，那么便会破坏规则4。

3>.非空树插入后，新增节点必须是红色节点，如果新增节点的父亲节点是黑色节点的话，那么就没有违反任何的规则，则插入结束。

4>.非空树插入后，新增节点必须是红色节点，如果新增节点的父亲节点是红色的，就违反了规则3。进一步分析的话，c（插入的新节点）是黑色节点，p（插入的新节点的父亲节点）是红色节点，g（插入的新节点的爷爷节点）就必定是黑色节点，在p为红色节点的情况下，g就只能是黑色节点，否则，被插入的这棵树就根本不是一棵红黑树，就玩不了。由此观之，在4>这种情况下，关键的变化就要看u（插入的新节点的亲叔叔）的情况，由此还需要根据u而分为以下几种情况分别进行处理。（说明：下图中假设我们把新增节点标识为c（cur），c的父亲标识为p（parent），p的父亲标识为g（grandfather），p的兄弟则标识为u（uncle））。

2.2.2 情况1：只变色，不旋转

c为红色，p为红色，g为黑色（这3个节点的颜色是固定的），若u存在且为红色，则将p和u变成黑色，将g变成红色。再把g当成新的c，然后就继续向上更新。

分析：由于c和p以及u这3个节点是相互挨着的，又由于它们3个均为红色，从而违反了规则3，由于我们插入的那个节点只能是红色，由此这里只能选择将p节点的颜色换成黑色，因此导致以g节点为根节点的红黑树的左子树中的每一条路径就都会多了一个黑色节点，为了保持所有路径中黑色节点的数目相同，因此这里我们选择将u节点也变成黑色节点，这样的话，就会让以g节点为根的树的所有路径上的黑色节点的数目就会保持一致，进而就会使得以g节点为根的树的所有路径上的黑色节点的数目比这棵红黑树其余的所有路径上的黑色节点的数目都要多一个，但是，通过4>中的分析我们可以得知g是黑色节点，因此，我们将g变为红色节点，那么，这样的话，以g为根的那棵树的所有路径中的黑色节点的数目就都与这棵红黑树其余的所有路径上的黑色节点的数目都相同了，注，到这还没完，进行完上面的步骤之后，g就变成了红色节点，那么g这个节点是不是这整棵树的根节点，如果是的话，那么我们到这里就可以结束了，如果不是的话，就还要看它的父亲节点是否是红色的，若是的话，则g就成为了新的c，继续往上不断重复上述的操作，直至结束，若不是，则也可以结束了。

1>.跟AVL树类似，上图我们展示了一种具体的情况，但是实际中需要这样处理的其实由很多种情况。

2>.下面的几幅图我们将以上类似的处理进行了抽象的表达，d/e/f代表的是每条路径上拥有bh个黑色节点的子树，而a/b则代表的是每条路径拥有bh-1个黑色节点的且根为红色节点的子树，bh>=0。

3>.下面的几幅图分别展示了bh==0/bh==1/bh==2的具体情况组合分析，当bh==2时，这里组合情况就已经高达上亿种了，这些样例是可以帮助我们去理解，不论情况有多少种，多么复杂，它们的处理方式都是一样的，变完色之后，再继续往上处理即可。

场景1：bh==0（a/b/c/d/e均为nullptr）

场景2：d/e/f为bh==1的红黑树（每条路径中都只有1个黑色节点）

现在我们先来看一下当bh==1时，都有哪些红黑树符合这个要求：

（这里我们需要注意一下，就是a/b/d/e/f这5棵子树具体是什么，它必须要满足变色到5这个节点时，让5这个节点变为红色才可以，无论bh为多少）通过我们上述的讲解可知，我们得知了要想执行我们这个场景1，p/g/u这3个节点是要存在的，并且p和u必须为红色节点，而g为黑色节点，只有当以上条件满足且c为红色节点时，才会执行只变色的这个操作，OK，好，我们回到这里，bh==1，就说明，d/e/f三棵子树均多了一个黑色节点（我们的a/b子树的目的是为了让5这个节点变成红色节点），但又因只变色的这种场景条件限制，就使得5这个节点原先是黑色节点，那这样的话，这整棵树的每条路径上的黑色节点的个数就均等了，接下来，就是要探讨一下该如何让5这个节点从黑色变成红色了，如果a/b子树为空的话，那么显然无法让5这个节点变成红色节点，我们来看一下bh==0这个情况，既然5刚开始是黑色节点，要经过变色让其成为红色节点，我们从bh==0这种情况种可以得到灵感，就是让5这个节点成为g，把bh==0这种情况中的10看作5，6看作a子树，15看作b子树，最后g变成新的c，这样的话，5节点不就变成红色节点了吗，并且还成为了新的c，完美地达到了我们想要地结果，综上所述，在d/e/f均为bh==1的红黑树的条件下，a/b均为红色节点。（假设下图中的d/e/f均为m子树）

场景3：d/e/f为bh==2的红黑树（每条路径中只有2个黑色节点）

首先我们这里先来看一下，当bh==2时，都有哪些红黑树符合bh==2这个条件要求：

这里我们先来说一下就是为什么a/b只能为bh==1且根要是红色节点的一棵红黑树（这里我们依旧是以bh==0这个场景中的第二幅图为例来展开分析的），就如图中所示的那样，要想触发变色的条件的话，就必须要想办法让5这个节点变成红色节点，由于在情况1中，p节点被确定为红色节点，而g节点被确定为黑色节点，u节点存在且为红色，而且还要保证插入元素之前这棵树为红黑树，为此刚开始的时候5这个节点不能是红色节点，只能是黑色节点，既然是黑色节点，要想让它在进行2轮变色操作后变成红色，就必须让它的儿子节点为红色节点，只有儿子为红色节点，最后才有可能经过变色让5节点变红，又由于d/e/f均为bh==2的红黑树，因此以5为根的这棵子树中的所有路径都少一个黑色节点，为了保持黑色节点的平衡，就让5节点的孙子节点均变为黑色节点，由此可知，a/b只能为bh==1且根为红色节点的一棵红黑树。

这里我们还需要注意一个知识，就是如果是插入在a子树上的话，a子树的种类没有16种，而b子树可以是这16种的任意一种，如果是插入在b子树上的话，b子树的种类也没有16种，而a子树可以是这16种中的任意一种。

这里我们再说一个知识，就是我们这里写的这个情况1它的条件是p为红色，g为黑色，并且同时我们还要保证u节点存在且u节点为红色，也就是说，只要满足我们这里所说的这个条件的话，就走情况1的方法，一旦有一个条件不符合，就不可以走情况1的这个方法，但是由于插入节点时不一定只是在a子树中插入，还有可能插在b子树中，如果我们仔细观察的话，我们会发现不管是在a/b哪个子树中，当更新到5节点时，之后相应的操作都是一样的，是因为不管是在a子树中插入还是在b子树中插入，当更新到5这个节点时，它们的叔叔都是同一个，都是15，但如果换作是在e子树或f子树中插入的话，此时若更新到相应的节点的话，那么它们的叔叔就会变成6这个节点了，因此，在情况1中好需要分成两种情况考虑。我们这里以bh==0的情况试着在6为根的子树上插入和15为根的子树上插入这两种情况看一下。

2.2.3 情况2：单旋+变色

c为红，p为红，g为黑，u不存在或u存在且为黑，若u不存在的话，则c一定时新增节点，若u存在且为黑色的话，则c一定不是新增节点，并且c之前的颜色一定是黑色，是在c子树中插入，并且情况刚好符合情况1中的一种，变色将c从黑色节点变成了红色节点，是像这样更新上来的。

分析：由于c和p以及g这个3个节点的颜色我们时可以确定知晓的，在情况1中，我们是因为有 " u存在且u为红色节点 " 这个条件，因此我们只需变色，说白了，情况1的逻辑实际上就相当于是 " 将黑色节点往下挪了一层 " ，" 往下挪了一层 "之后，仍然会保持整棵红黑树中每条路径的黑色节点的个数是相同的，OK，现在回到我们的这个情况中来，我们现在已知c和p节点均为红色节点，是不可以的，也就是说，p节点它必须要变色变成黑色节点，才能解决红色连续的问题，在我们的情况2中，u不存在或者是黑色节点，既然如此的话，那么这里单纯的变色就无法解决问题了，需要旋转+变色才可以。

这里我们在正式开始画图之前，我们来讲解一下为什么要外加一个旋转操作。大家首先要知道一点就是我们这里进行的操作是插入操作（往红黑树中），也就是说，我们这里在插入节点之前，它就已经是一棵红黑树了，我们插入了一个红色节点，且这个节点的父亲，爷爷，叔叔均与情况2的条件相吻合，如果我们继续延用情况1中的那种变色方法的话，将爷爷变红，将父亲和叔叔（如果叔叔步存在的话就不说了）变黑，就会导致这棵树将不再是一棵红黑树了，因为规则4被违反了（我们情况2分为u节点存在和不存在两种情况，这里以u节点不存在展开讲解），接下来我们来细细地分析一下，结合下图来看并做讲解：

我们通过上图可以得知在插入节点c之前，以g为根节点地红黑树地每条路径上所拥有地黑色节点地个数均是相同的，如果只进行变色的话，就会造成以p为根节点的红黑树左右子树中的各个路径的长度是不相同的，通过上图可分析出变色之后以p节点为根的红黑树的右子树中所有的路径上黑色节点个数均比左子树中所有路径上的黑色节点的个数少一个，进而违反了规则4，由此可知，对于情况2这种情况，只进行变色操作不可以的，因此要再加上一个旋转的操作，让p节点成为新的根节点，这样就使得整棵树中所有路径上的黑色节点的个数都是相同的。（这里不管u是存在的还是不存在的，都可以用上述的方法去做，因此这里是不用分析u是否存在，不存在......，存在且为黑......）

bh==0（a/b/d/e/f均为nullptr）

当bh==0时，也就间接地说明了u节点不存在，且c一定为插入节点

bh!=0（a/b/d/e/f均为bh-1的子树，d为bh的节点，不同的是e/f的根是黑色或红色的，而a/b的根只能是红色的，d的根只能是黑色的，因为只有当a/d/b/e/f分别满足上述的条件时，才可以让更新到3这个节点时，让3这个节点由黑色变成红色）

当bh!=0时，也就间接地说明了u节点一定存在且为黑，而c一定不是新增节点

当我们说到这里时，很多同学认为情况2中的这种情况在这里已经是结束了，但实际上还有一个注意事项，就是这里要分情况考虑，因为不止可以在a或b中插入，还可以在f中插入，在a或b中插入是进行右单旋操作，但如果是插入在f中，则进行的是左单旋操作。我们通过下图来看一下（以bh==0为例）：

2.2.4 情况3：双旋+变色

c为红色，p为红色，g为黑色，u不存在或者是u存在且为黑色，若u节点不存在的话，则c一定是新增节点，若u节点存在且为黑色的话，则c节点一定不是新增节点，c之前的颜色是黑色的，是在c的子树中插入，符合情况1中的某一种，变色将c的颜色从黑色变成了红色。

分析：p必须要变成黑色节点，才能解决连续红色节点的问题，u不存在或是黑色的，这里单纯的只使用变色是无法解决问题的，需要旋转+变色。

这里我们提前把这个分情况考虑的事项简单说明一下，也是因为插入位置的不同进而导致我们这里需要分情况讨论：

（不管是先旋转还是先变色其实没有先后顺序，先弄哪个其实都可以），接下来，我们通过画图来更加具体形象地看一下情况3的变化过程：

bh==0时（a/b/d/e/f均为nullptr）

当bh==0时，也就间接地说明了u节点不存在，且c节点一定为插入节点

bh!=0（e和f是根为红色或黑色，且黑色节点数量为bh-1的子树，a和b是根为红色，黑色节点的数量为bh-1的子树，d是根为黑色的，且黑色节点的数量为bh的子树，只有当a/b/d/e/f这5棵子树满足上述条件后，才可以让更新到8这个节点时让节点颜色由黑色变成红色）

当bh!=0时，也就间接地说明了u节点存在且为黑色，c节点一定不是新增节点

2.2.5 红黑树插入的代码实现

我们接下来的代码会用到左单旋和右单旋，这两种旋转的方式我们在前一篇博客讲过，大家如有不会的可以去看我前一篇博客，链接在下面，方便大家观看：

数据结构——AVL树的实现-CSDN博客文章浏览阅读474次，点赞14次，收藏19次。Hello，大家好，这一篇博客我们来讲解一下数据结构中的AVL树这一部分的内容，AVL树属于是数据结构的一部分，顾名思义，AVL树是一棵特殊的搜索二叉树，我们接下来要讲的这篇博客是建立在了解搜索二叉树这个知识点的基础之上的，因此，我在这里建议大家可以先去看看我之前写过的那片有关搜索二叉树内容的博客，为了方便大家寻找，链接就放到下面了：搜索二叉树，效率的进一步upgrate！-CSDN博客Hello，大家好，我们关于C++的大部分语法知识就可以宣告结束了，不知道聪明的你有没有掌握扎实呢？https://blog.csdn.net/2301_81390458/article/details/143649479?spm=1001.2014.3001.5502https://blog.csdn.net/2301_81390458/article/details/143649479?spm=1001.2014.3001.5502https://blog.csdn.net/2301_81390458/article/details/143649479?spm=1001.2014.3001.5502https://blog.csdn.net/2301_81390458/article/details/143649479?spm=1001.2014.3001.5502https://blog.csdn.net/2301_81390458/article/details/143649479?spm=1001.2014.3001.5502https://blog.csdn.net/2301_81390458/article/details/143649479?spm=1001.2014.3001.5502https://blog.csdn.net/2301_81390458/article/details/143649479?spm=1001.2014.3001.5502https://blog.csdn.net/2301_81390458/article/details/143649479?spm=1001.2014.3001.5502https://blog.csdn.net/2301_81390458/article/details/143649479?spm=1001.2014.3001.5502https://blog.csdn.net/2301_81390458/article/details/143649479?spm=1001.2014.3001.5502

bool Insert(const pair<K, V>& kv)
{//我们这里要实现的是插入操作，既然要插入节点，那么就要找到相应的且最为合适的位置，红黑树从本质上来说其实就是二叉搜索树，因此我们这里用二叉搜索树找位置的方式去到这里找相应的位置。if (_root == nullptr){_root = new node(kv);_root->_col = BLACK;//根据规则2可知，根节点是黑色节点。return true;}node* parent = nullptr;//指向插入节点的父亲节点，通过我们前面所讲的红黑树中的节点的结构我们可知，每个节点中都有一个指向父亲节点的指针，因此，我们就需要定义一个指针去指向插入节点的父亲。node* cur = _root;//通过cur指针去遍历红黑树。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//cur->_kv.first == kv.first;说明要插入的节点已存在，重复了，就不插入了。{return false;}}cur = new node(kv);//新建一个红色节点。cur->_col = RED;//接下来要将新建节点给连到原红黑树中去，那么就要判断一下新建的这个节点要插入到父亲的左子树还是右子树上。if (parent->_kv.first < cur->_kv.first)//在右子树上。{parent->_right = cur;}else//在左子树上。{parent->_left = cur;}cur->_parent = parent;//连接cur节点中的_parent指针。while (parent && parent->_col == RED)//上述的代码我们是将节点插入好了，接下来，我们就要开始更新颜色了，以确保在插入节点之后这棵树任可以是一棵红黑树。而更新的条件就是要保证父亲节点存在，且父亲节点为红色，这里要卡一下父亲节点存在这个条件是为了防止更新到根节点的这个情况，而parent->_col为RED是因为通过我们前面的解析可以得知只有当c的父亲为红色时，才会进行向上更新颜色的操作。{node* grandparent = parent->_parent;//指向cur的爷爷节点。if (parent == grandparent->_left)//通过我们前面的分析讲解可知，在3种情况中，还要对每一种情况进行细分，是因为插入节点位置不同进而使得我们还要进行细分，通过我们前面的分析可知，无论c插入到哪个位置上，它的爷爷都是同一个，而不同位置上的p是不同的，因此，我们这里则是选择通过parent节点和grandparent节点的相对位置来判断的，这里之所以选择判断parent和grandparent的相对位置而不选择parent和cur的相对位置，是因为我们要想完成更新节点颜色的操作，还要找到叔叔，而只有得知了parent相对于grandparent的相对位置之后，我们才能找到叔叔，其余均不行。{//通过我们前面的分析可知，之所以会有3种情况，全部都是由于叔叔节点造成的，因此我们接下来就需要围绕叔叔节点展开了，首先我们要得到叔叔节点。node* uncle = grandparent->_right;//父亲在左子树中，那么相对的叔叔就在右子树中。if (uncle && uncle->_col == RED)//如果叔叔存在且为红色的话，那么对应的是情况1，只需要变色就可以了。{parent->_col = uncle->_col = BLACK;grandparent->_col = RED;cur = grandparent;//让grandparent成为新的cur节点。parent = cur->_parent;//parent指向新的cur的父亲节点，准备新一轮的更新颜色。}else//叔叔不存在或者叔叔存在且为黑色。{if (cur == parent->_left)//对应的是情况2，单旋+变色中的右单旋。{//如果插入的节点在以grandparent为根的树的左子树上，且同时在以parent为根的树的左子树上，则进行右单旋+变色操作。RotateR(grandparent);//右单旋操作和AVL树中所讲的右单旋操作相同，以grandparent旋转点进行右单旋操作。parent->_col = BLACK;grandparent->_col = RED;}//这里之所以不让grandparent变成新的cur节点，是因为通过我们前面的解析可以得知，当旋转+变色过后，子树的根就是黑色的，那么如此的话，无论子树的根是什么颜色，都不会违反规则。else//cur==parent->_right;对应的是情况3中的左右双旋{//如果插入的节点在以grandparent为根的树的左子树上，且同时在以parent为根的树的右子树上，则解析左右双旋+变色。RotateL(parent);RotateR(grandparent);cur->_col = BLACK;grandparent->_col = RED;}break;//旋转过后，就不再往上更新颜色了，直接结束更新。}}else//parent == grandparent->_right;{node*uncle= grandparent->_left;//父亲在右子树中，那么相对应的叔叔就在左子树中。if (uncle && uncle->_col == RED)//如果叔叔存在且为红色的话，那么对应的是情况1，只需要变色就可以了。{parent->_col = uncle->_col = BLACK;grandparent->_col = RED;cur = grandparent;//让grandparent成为新的cur节点。parent = cur->_parent;//parent指向新的cur的父亲节点，准备新一轮的更新颜色。}else//叔叔不存在或者叔叔存在且为黑色。{if (cur == parent->_right)//对应的是情况2，单旋+变色中的左单旋。{RotateL(grandparent);//左单旋操作和AVL树中所讲的左单旋操作相同，以grandparent旋转点进行左单旋操作。parent->_col = BLACK;grandparent->_col = RED;}//这里之所以不让grandparent变成新的cur节点，是因为通过我们前面的解析可以得知，当旋转+变色过后，子树的根就是黑色的，那么如此的话，无论子树的根是什么颜色，都不会违反规则。else//cur==parent->_left;对应的是情况3中的右左双旋{//如果插入的节点在以grandparent为根的树的右子树上，且同时在以parent为根的树的右子树上，则解析右左双旋+变色。RotateR(parent);RotateL(grandparent);cur->_col = BLACK;grandparent->_col = RED;}break;//旋转过后，就不再往上更新颜色了，直接结束更新。}}}//当走到这里时，就说明更新颜色结束了，但是，逻辑在这里还没有结束，根节点(_root)是什么颜色不确定，因此在最后我们将_root的颜色变成黑色。_root->_col = BLACK;//这句代码放在最后的好处是不管哪种情况下，都能保证_root是黑色的。return true;
}

2.3 红黑树的查找

按照二叉搜索树的逻辑实现即可，搜索效率为O(logN)。

node* Find(const K& key)
{node* cur = _root;//用cur指针去遍历红黑树。while (cur)//如果cur为空，则说明没找到。{if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else//cur->_kv.first==key;找到了。{return cur;}}return nullptr;
}

2.4 红黑树的验证

验证一棵树是否是红黑树的方法其实有很多种，许多的同学在看到这个问题时，第一时间想到的是获取最长路径和最短路径的长度，检查最长路径不超过最短路径的2倍，但是这样的方法时行不通的，因为就算满足这个条件，红黑树也可能颜色不满足规则，当前暂时没出问题，后续若继续插入的话迟早是会出问题的，所以我们还是要去检查4点规则，满足这4点规则的话就一定能保证最长路径不超过最短路径的2倍。

1>.规则1枚举颜色类型，天然实现保证了颜色不是黑就是红。

2>.规则2直接检查根节点就可以了。

3>.规则3前序遍历检查，遇到红色节点查孩子不太方便，因为孩子有两个，且还不一定存在，反过来检查父亲节点就方便多了。

4>.规则4前序遍历，遍历过程中用形参记录根到当前节点的blackNum（红色节点数目），前序遍历遇到黑色节点就++blackNum，走到空的话就计算出了一条路径的黑色节点的数目。再任意一条路径的黑色节点数量作为参考值，依次比较就可以了。

bool IsBalance()
{if (_root == nullptr)//说明这棵树是一棵空树，空树也属于红黑树。{return true;}if (_root->_col == RED)//若根节点为红色，违反了规则2，则不是红黑树。{return false;}//通过4>.我们可知，我们要想判断规则4，还需要任意一条路径上的黑色节点的数量作为参考值。int refNum = 0;node* cur = _root;//去遍历红黑树的任意一条路径。while (cur){if (cur->_col == BLACK){++refNum;}cur = cur->_left;}return Check(_root, 0, refNum);//Check是检查是否符合规则3和规则4，0是当前这条路径上黑色节点的个数，refNum为参考值。
}
bool Check(node* root, int blackNum, const int refNum)
{//我们这里走的是一个前序遍历的一个过程。if (root == nullptr)//说明红黑树的一条路径走完了，判断黑色节点的个数。{if (blackNum != refNum){cout << "存在黑色节点数量不相同的路径" << endl;return false;}return true;//这条路径满足要求。}//接下来检查规则3。if (root->_col == RED && root->_parent->_col == RED)//满足条件的话就说明此条路径上有2个连续的红色节点。这里我还想说一个注意事项，就是这里难道不用判断根节点吗？因为根节点的父亲是nullptr，其实是不用的，因为我们这个条件是当遇到的那个节点为红色节点时，才会去看它的父亲节点，而根节点永远时黑色的，因此不用考虑。{cout << root->_kv.first << "存在连续的红色节点" << endl;return false;}if (root->_col == BLACK)//当前节点为黑色节点。{++blackNum;}return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum);//用前序遍历去继续检查。
}