C++《红黑树》

在之前的篇章当中我们已经了解了基于二叉搜索树的AVL树，那么接下来在本篇当中将继续来学习另一种基于二叉搜索树的树状结构——红黑树，在此和之前学习AVL树类似还是通过先了解红黑树是什么以及红黑树的结构特点，接下来在试着实现红黑树的结构以及实现红黑树插入新节点、进行节点查询的功能，相信通过本篇的学习能让你了解红黑树，一起加油把！！！

1. 红黑树的概念

在此红黑树是基于二叉搜索树进行改进的，因此红黑树的中序遍历也是有序的。

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

1.1 红黑树的规则

只有同时满足以下的几点要求时才是在红黑树：
1. 每个结点不是红色就是黑色
2. 根结点是黑色的
3. 如果⼀个结点是红色的，则它的两个孩⼦结点必须是黑色的，也就是说任意⼀条路径不会有连续的红色结点。
4. 对于任意⼀个结点，从该结点到其所有NULL结点的简单路径上，均包含相同数量的黑色结点

以上的要求看起来是规律的，但是其实这几点规则之间是相互协调的，接下来我们就通过几个示例来看看这些规则是怎么使得红黑树当中的最长路径的长度不大于其他路径的两倍的。 

来看以下的示例：

以上图示的二叉树当中，根节点为黑，并且不存在连续的红节点，那么接下来就是要知道二叉树当中每个路径上黑节点的个数；在此之前需要我们先找出以上的二叉树有几条路径，可能你会简单的认为以上不就是有4条路径吗？如下所示

但是其实以上求路径个数的方式是错误的，在此要一条路径的需要到空节点为止，因此以上的正确的路径应如下所示：


 

此时就可以看出以上的二叉树有9条路径，并且每条的路径上黑色节点的个数都是2两个，这也是满足红黑树的要求的。

以上的二叉树当中满足了以上所示的红黑树的1、2、4点规则，但是对应规则3以上的所示的二叉树的叶子节点为红时不就不满足规则了吗？

这其实在在此通常情况下我们会忽略这种情况，在《算法导论》等书籍上补充了⼀条每个叶⼦结点(NIL)都是黑色的规则。他这⾥所指的叶子结点不是传统的意义上的叶子结点，而是我们说的空结点，有些书籍上也把NIL叫做外部结点。NIL是为了方便准确的标识出所有路径，《算法导论》在后续讲解实现的细节中也忽略了NIL结点，所以我们知道⼀下这个概念即可。

那么在满足红黑树的规则下，就可以使得没有⼀条路径会比其他路径长出2倍，因而是接近平衡的。

以上所示的红黑树当中最长路径为3，最短的为2，这时二叉搜索树就是接近平衡的

以下的二叉搜索树也是满足以上的红黑树规则，也是红黑树

 这是就可以看出红黑树当中其实是完全没有红色节点的，这是也是满足红黑树的规则的

1.2 红黑树如何保持接近平衡 

在此我们就要思考在红黑树是如何确保基本平衡的，也就是在红黑树当中是如何确保最长的路径不超过最短路径的两倍的？

• 由规则4可知，从根到NULL结点的每条路径都有相同数量的黑色结点，所以极端场景下，最短路径就就是全是⿊⾊结点的路径，假设最短路径长度为bh(black height)。
• 由规则2和规则3可知，任意⼀条路径不会有连续的红色结点，所以极端场景下，最长的路径就是一黑一红间隔组成，那么最长路径的长度为2*bh。
• 综合红黑树的4点规则而言，理论上的全⿊最短路径和一黑一红的最长路径并不是在每棵红⿊树都存在的。假设任意⼀条从根到NULL结点路径的⻓度为x，那么bh <= h <= 2*bh。

1.3 红黑树的效率 

以上我们了解了红黑树的概率，以及要使得二叉搜索树为红黑树要满足什么样的要求，那么接下来就来分析在红黑树当中进行查找的效率。

假设N是红⿊树树中结点数量，h最短路径的长度，那么 2^{h}-1<=N<2^{2h}-1, 由此推出
h ≈ logN ，也就是意味着红⿊树增删查改最坏也就是走最长路径为 2*logN，那么时间复杂度就为O(\log N)

 

在此红黑树其实相比之前学习的AVL树控制平衡的方式不用，AVL树是通过子树的控制高度差进行整体的平衡控制，而红黑树是通过4条规则的颜色约束间接的实现近似平衡，他们效率都是同⼀档次，但是相对而言，插⼊相同数量的结点，红黑树的旋转次数是更少的，因为他对平衡的控制没那么严格。在大量节点时AVL树的高度相比红黑树会低一些。

2. 红黑树实现

以上我们了解了红黑树的结构特点之后接下来就来实现红黑树的代码

在此创建两个文件BRTRee.h和test.cpp，在BRTRee.h内实现红黑树的结构以及各种的功能，在test.cpp内对实现的红黑树进行测试，看是否满足我们的要求

2.1 红黑树节点实现

在实现红黑树的结构之前我们先要实现红黑树节点的结构体，在此创建一个名为colour的枚举来表示节点的颜色，创建一个名为RBTree的struct结构体来表示红黑树的节点，实现代码如下所示：

enum colour
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{pair<K, V> _val;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;colour _col;RBTreeNode(const pair<K, V>& val):_val(val), _left(nullptr), _right(nullptr), _parent(nullptr){}};

2.2 红黑树结构实现 

在实现了红黑树节点的结构之后，接下来我们抽奖一个名为RBTree的类，在该类内实现红黑树的结构以及各种功能，接下来就先实现结构，实现的代码如下所示：

template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;public://各种功能……private:Node* root = nullptr;};

以上我们时使用类模板的方式来创建对应的二叉树，这样就可以使得创建的二叉树内节点的数据的类型是任意的，不过要存储在红黑树内的数据类型是需要能进行大小的比较，如果默认不支持也是需要我们自己实现的。

2.3 红黑树插入实现

以上实现了红黑树的大体结构之后接下来就来实现红黑树当中的插入功能，接下来在实现插入的代码之前先来分析在红黑树当中插入新的节点会有几种情况。

在插入新的节点之后，新形成的也是要满足红黑树的4条规则的。

1.在空树当中插入节点，那么新增的节点需要是黑色节点。

在非空的树当中插入新的节点，此时我们就要思考应将新的节点的颜色置为黑的还是红色？

如果我们插入的节点是红色的那么就只需要在其父节点为红色是进行调整，但是如果插入的节点为黑色的，这就会使得新产生的路径内的黑色节点数比其他的路径要多一个，这时要进行调整是很困难的，因此插入的节点应该初始化为红节点

2.在非空树当中插入新的节点，将该节点初始化为红

在非空树内插入新节点之后接下来就要看其父节点是否为红，是的话此时的树就违背了红黑树的规则3，就需要进行调整。调整直到没有应该红色节点的父节点为红为止。如果一开始插入的节点的发节点就为黑；那么插入完就可以停止操作

以下就是实现的不包含调整调整代码的插入代码：

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->_val.first < kv.first){Parent = cur;cur = cur->_right;}else if (cur->_val.first > kv.first){Parent = cur;cur = cur->_left;}else{return false;}}//创建新节点cur = new Node(kv);if (Parent->_val.first < kv.first){Parent->_right = cur;}else{Parent->_left = cur;}cur->_parent = Parent;cur->_col = RED;//进行调整使得树满足红黑树的规则……//无论以上是否进行调整都将根结点的颜色置为黑root->_col = BLACK;return true;}


 

接下来就来讲解插入的节点的父节点为红时进行调整的3种情况

注：接下来的讲解当中假设我们把新增结点标识为c (cur)，c的父亲标识为p(parent)，p的父亲标识为g(grandfather)，p的兄弟标识为u（uncle）。

1.情况1：只需变色

当插入的节点的为父亲节点为红时，而且父亲的父亲的另一个节点也是红的，也就是c节点的叔叔节点u也为红时。因为在插入新的节点c之前当前的树一定是满足红黑树的规则的，那么此时p节点的父亲节点f一定是为黑，也就是c节点的祖父节点一定为黑。

 

例如以下示例：


新插入的节点为x，此时c、p、u的节点颜色情况就满足以上描述的形式。那么要让该节点变回满足红黑树的规则，就只需要将p、u变黑；g变红即可。这时调整完之后就可以使得树当中每条路径内的黑色节点的个数都相同。

以下是只进行变色情况的抽象表达，d/e/f代表每条路径拥有hb个黑色结点的子树，a/b代表每条路径拥有hb-1个黑色结点的根为红的子树，hb>=0。和之前学习AVL树一样接下来来通过看看几种只进行变色的情况。

那么接下来就开看看 hb==0 、hb==1、hb==2的情况 ，其中当hb等于2时，这⾥组合情况上百亿种，这些样例是帮助我们理解，不论情况多少种，多么复杂，处理方式⼀样的，变⾊再继续往上处理即可，所以我们只需要看抽象图即可。

通过以上的示例就可以看出在处理只需要变色的情况时，新出现的红色节点可能是新插入的也可能是下部分的节点调整上来的，此时只需要一直进行调整直到对应的p为黑时就停止 

实现的代码如下所示：

以下以p节点分别为g节点的左节点和右节点的两种情况分别进行分析
 

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->_val.first < kv.first){Parent = cur;cur = cur->_right;}else if (cur->_val.first > kv.first){Parent = cur;cur = cur->_left;}else{return false;}}//创建新节点cur = new Node(kv);if (Parent->_val.first < kv.first){Parent->_right = cur;}else{Parent->_left = cur;}cur->_parent = Parent;cur->_col = RED;while (Parent && Parent->_col == RED){Node* grandfather = Parent->_parent;//父节点为祖父节点的左节点时//    g//  p  u//cif (grandfather->_left == Parent){Node* uncle = grandfather->_right;//叔叔存在且为红if (uncle && uncle->_col == RED){Parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;Parent = cur->_parent;}//其他情况……}//父节点为祖父节点的右节点时//    g//  u   p//       celse{Node* uncle = grandfather->_left;//叔叔存在且为红if (uncle && uncle->_col == RED){Parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;Parent = cur->_parent;}//其他情况……}}//无论以上是否进行调整都将根结点的颜色置为黑root->_col = BLACK;return true;}

2.情况2：单旋+变色

以上情况1当中是叔叔存在且为红的情况，那么如果叔叔不存在或者是不为红又要怎么进行调整呢？

首先是c为红，p为红，g为⿊，u不存在或者u存在且为⿊，u不存在，则c⼀定是新增结点，u存在且为⿊，则c⼀定不是新增，c之前是⿊⾊的，是在c的⼦树中插⼊，符合情况1，变⾊将c从⿊⾊变成红⾊，更新上来的。
 

在此p是必须变为黑的，但是由于u为黑或者不存在，那么这就使得将p变为黑时p节点所在的路径的黑色节点的个数就与其他的路径不相同，那么这时就需要进行旋转来解决问题。

在此也是以p节点分别为g节点的左节点和右节点的两种情况分别进行分析

     gp    u
c

如果p是g的左，c是p的左，那么以g为旋转点进行右单旋，再把p变⿊，g变红即可。p变成课这颗树新的根，这样⼦树⿊⾊结点的数量不变，没有连续的红⾊结点了，且不需要往上更新，因为p的⽗亲是黑色还是红色或者空都不违反规则。

     gu    pc

如果p是g的右，c是p的右，那么以g为旋转点进行左单旋，再把p变⿊，g变红即可。p变成课这颗树新的根，这样⼦树⿊⾊结点的数量不变，没有连续的红⾊结点了，且不需要往上更新，因为p的⽗亲是⿊⾊还是红⾊或者空都不违反规则。

3.情况3：双旋+变色
 

以上我们分析了单旋的情，那么接下来就来分析双旋的情况，当插入c之后红黑树的子树结构如下所示时只使用单旋是无法实现调整之后的树满足红黑树的规则的，在此接下来要使用到双旋才能调整至满足要求。

c为红，p为红，g为黑，u不存在或者u存在且为黑，u不存在，则c⼀定是新增结点，u存在且为黑，则c⼀定不是新增，c之前是黑色的，是在c的子树中插入，符合情况1，变⾊将c从黑色变成红⾊，更新上来的。


在此p必须变黑，才能解决，连续红色结点的问题，u不存在或者是⿊⾊的，但是这⾥单纯的变色⽆法解决问题，需要旋转+变色。

     gp    uc

如果p是g的左，c是p的右，那么先以p为旋转点进行左单旋，再以g为旋转点进行右单旋，再把c变
黑，g变红即可。c变成课这颗树新的根，这样子树黑⾊结点的数量不变，没有连续的红色结点了，且不需要往上更新，因为c的⽗亲是⿊⾊还是红⾊或者空都不违反规则。

 

     gu    pc

如果p是g的右，c是p的左，那么先以p为旋转点进行右单旋，再以g为旋转点进行左单旋，再把c变
⿊，g变红即可。c变成课这颗树新的根，这样⼦树黑色结点的数量不变，没有连续的红色结点了，且不需要往上更新，因为c的⽗亲是黑色还是红色或者空都不违反规则。

2.4 插入完整代码

以上我们就进行插入节点的三种情况的分析，那么接下来就将以上的插入代码补充完整

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->_val.first < kv.first){Parent = cur;cur = cur->_right;}else if (cur->_val.first > kv.first){Parent = cur;cur = cur->_left;}else{return false;}}//创建新节点cur = new Node(kv);if (Parent->_val.first < kv.first){Parent->_right = cur;}else{Parent->_left = cur;}cur->_parent = Parent;cur->_col = RED;while (Parent && Parent->_col == RED){Node* grandfather = Parent->_parent;//父节点为祖父节点的左节点时//    g//  p  u//cif (grandfather->_left == Parent){Node* uncle = grandfather->_right;//叔叔存在且为红if (uncle && uncle->_col == RED){Parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;Parent = cur->_parent;}//叔叔不存在或者为黑else{//当c为p的左节点时//    g//  p  u//cif (Parent->_left == cur){RotateR(grandfather);grandfather->_col = RED;Parent->_col = BLACK;}//当c为p的右节点时//     g//   p   u//    celse{RotateL(Parent);RotateR(grandfather);grandfather->_col = RED;cur->_col = BLACK;}break;}}//父节点为祖父节点的右节点时//    g//  u   p//       celse{Node* uncle = grandfather->_left;//叔叔存在且为红if (uncle && uncle->_col == RED){Parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;Parent = cur->_parent;}//叔叔不存在或者为黑else{//当c为p的右节点时//    g//  u   p//       cif (Parent->_right == cur){RotateL(grandfather);grandfather->_col = RED;Parent->_col = BLACK;}//当c为p的左节点时//    g//  u   p//     celse{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;if (subLR != nullptr){subLR->_parent = Parent;}Node* tmpNode = Parent->_parent;Parent->_left = subLR;Parent->_parent = subL;subL->_right = Parent;if (tmpNode != nullptr){if (tmpNode->_left == Parent){tmpNode->_left = subL;}else{tmpNode->_right = subL;}subL->_parent = tmpNode;}else{root = subL;subL->_parent = nullptr;}}void RotateL(Node* Parent)
{Node* subR = Parent->_right;Node* subRL = subR->_left;if (subRL != nullptr){subRL->_parent = Parent;}Node* tmpNode = Parent->_parent;Parent->_right = subRL;Parent->_parent = subR;subR->_left = Parent;if (tmpNode != nullptr){if (tmpNode->_left == Parent){tmpNode->_left = subR;}else{tmpNode->_right = subR;}subR->_parent = tmpNode;}else{root = subR;subR->_parent = nullptr;}}

2.4 红黑树查找

在此红黑树的查找实现和之前实现的二叉搜索树和AVL树类似，对你来说实现查找的代码肯定是 so easy 的，在此就不再进行讲解，直接奉上代码：

Node* Find(const K& val)
{if (root == nullptr){return nullptr;}Node* cur = root;while (cur){if (cur->_val.first < val){cur = cur->_left;}else if (cur->_val.first > val){cur = cur->_right;}else{return cur;}}return nullptr;
}

2.5 红黑树删除

在此红黑树的删除较为复杂且不是很重要，在此就不进行讲解。

 

2.6 红黑树验证

以上我们实现了红黑树的插入以及查找，那么接下来就来实现验证的代码

首先来分析验证的代码该如何实现：
这力获取最长路径和最短路径，检查最长路径不超过最短路径的2倍是不可行的，因为就算满足这个条件，红黑树也可能颜色不满足规则，当前暂时没出问题，后续继续插入还是会出问题的。所以我们还是去检查4点规则，满足这4点规则，⼀定能保证最长路径不超过最短路径的2倍。

1. 规则1枚举颜⾊类型，天然实现保证了颜色不是黑色就是红色。
2. 规则2直接检查根即可
3. 规则3前序遍历检查，遇到红色结点查孩子不太方便，因为孩⼦有两个，且不⼀定存在，反过来检查父亲的颜色就方便多了。
4. 规则4前序遍历，遍历过程中用形参记录跟到当前结点的blackNum(黑色结点数量)，前序遍历遇到黑色结点就++blackNum，走到空就计算出了⼀条路径的⿊⾊结点数量。再任意⼀条路径黑色结点数量作为参考值，依次比较即可。

实现代码如下所示：

bool Check(Node* root, int blackNum, const int refNum)
{if (root == nullptr){// 前序遍历⾛到空时，意味着⼀条路径⾛完了//cout << blackNum << endl;if (refNum != blackNum){cout << "存在⿊⾊结点的数量不相等的路径" << endl;return false;}return true;}// 检查孩⼦不太⽅便，因为孩⼦有两个，且不⼀定存在，反过来检查⽗亲就⽅便多了if (root->_col == RED && root->_parent->_col == RED){cout << root->_val.first << "存在连续的红⾊结点" << endl;return false;}if (root->_col == BLACK){blackNum++;}return Check(root->_left, blackNum, refNum)&& Check(root->_right, blackNum, refNum);
}bool IsBalance()
{if (root == nullptr)return true;if (root->_col == RED)return false;// 参考值int refNum = 0;Node* cur = root;while (cur){if (cur->_col == BLACK){++refNum;}cur = cur->_left;}return Check(root, 0, refNum);
}

测试用例：

void TestAVLTree1()
{RBTree<int, int> t;// 常规的测试⽤例int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };// 特殊的带有双旋场景的测试⽤例//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto e : a){t.Insert({ e, e });}t.InOrder();//cout << t.IsBalanceTree() << endl;cout<<t.IsBalance();
}

运行以上代码输出如下所示：
 

这时只能是说明对以上示例的测试用例进行插入是没问题的，要更严谨的验证就需要有更多的测试用例，这时使用以上的代码进行验证 ，并且测试进行插入的效率以及查找效率

void TestAVLTree2()
{const int N = 1000000;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 << t.IsBalance() << endl;cout << "Insert:" << end2 - begin2 << 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;
}

将vs的调整为release模式之后，通过输出的结果就可以看出我们实现的红黑树的插入代码是没问题的，并且实现的红黑树的插入效率以及查找效率都是很高的，效率基本和AVL树不差上下。 

2.7 完整代码

RBTree.c

#pragma once
#include<iostream>using namespace std;enum colour
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{pair<K, V> _val;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;colour _col;RBTreeNode(const pair<K, V>& val):_val(val), _left(nullptr), _right(nullptr), _parent(nullptr){}};template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;public: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->_val.first < kv.first){Parent = cur;cur = cur->_right;}else if (cur->_val.first > kv.first){Parent = cur;cur = cur->_left;}else{return false;}}//创建新节点cur = new Node(kv);if (Parent->_val.first < kv.first){Parent->_right = cur;}else{Parent->_left = cur;}cur->_parent = Parent;cur->_col = RED;while (Parent && Parent->_col == RED){Node* grandfather = Parent->_parent;//父节点为祖父节点的左节点时//    g//  p  u//cif (grandfather->_left == Parent){Node* uncle = grandfather->_right;//叔叔存在且为红if (uncle && uncle->_col == RED){Parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;Parent = cur->_parent;}//叔叔不存在或者为黑else{//当c为p的左节点时//    g//  p  u//cif (Parent->_left == cur){RotateR(grandfather);grandfather->_col = RED;Parent->_col = BLACK;}//当c为p的右节点时//     g//   p   u//    celse{RotateL(Parent);RotateR(grandfather);grandfather->_col = RED;cur->_col = BLACK;}break;}}//父节点为祖父节点的右节点时//    g//  u   p//       celse{Node* uncle = grandfather->_left;//叔叔存在且为红if (uncle && uncle->_col == RED){Parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;Parent = cur->_parent;}//叔叔不存在或者为黑else{//当c为p的右节点时//    g//  u   p//       cif (Parent->_right == cur){RotateL(grandfather);grandfather->_col = RED;Parent->_col = BLACK;}//当c为p的左节点时//    g//  u   p//     celse{RotateR(Parent);RotateL(grandfather);grandfather->_col = RED;cur->_col = BLACK;}break;}}}//无论以上是否进行调整都将根结点的颜色置为黑root->_col = BLACK;return true;}Node* Find(const K& val){if (root == nullptr){return nullptr;}Node* cur = root;while (cur){if (cur->_val.first < val){cur = cur->_left;}else if (cur->_val.first > val){cur = cur->_right;}else{return cur;}}return nullptr;}void InOrder(){_InOrder(root);cout << endl;}int  Height(){return _Height(root);}int Size(){return _Size(root);}bool Check(Node* root, int blackNum, const int refNum){if (root == nullptr){// 前序遍历⾛到空时，意味着⼀条路径⾛完了//cout << blackNum << endl;if (refNum != blackNum){cout << "存在⿊⾊结点的数量不相等的路径" << endl;return false;}return true;}// 检查孩⼦不太⽅便，因为孩⼦有两个，且不⼀定存在，反过来检查⽗亲就⽅便多了if (root->_col == RED && root->_parent->_col == RED){cout << root->_val.first << "存在连续的红⾊结点" << endl;return false;}if (root->_col == BLACK){blackNum++;}return Check(root->_left, blackNum, refNum)&& Check(root->_right, blackNum, refNum);}bool IsBalance(){if (root == nullptr)return true;if (root->_col == RED)return false;// 参考值int refNum = 0;Node* cur = root;while (cur){if (cur->_col == BLACK){++refNum;}cur = cur->_left;}return Check(root, 0, refNum);}private:Node* root = nullptr;void RotateR(Node* Parent){Node* subL = Parent->_left;Node* subLR = subL->_right;if (subLR != nullptr){subLR->_parent = Parent;}Node* tmpNode = Parent->_parent;Parent->_left = subLR;Parent->_parent = subL;subL->_right = Parent;if (tmpNode != nullptr){if (tmpNode->_left == Parent){tmpNode->_left = subL;}else{tmpNode->_right = subL;}subL->_parent = tmpNode;}else{root = subL;subL->_parent = nullptr;}}void RotateL(Node* Parent){Node* subR = Parent->_right;Node* subRL = subR->_left;if (subRL != nullptr){subRL->_parent = Parent;}Node* tmpNode = Parent->_parent;Parent->_right = subRL;Parent->_parent = subR;subR->_left = Parent;if (tmpNode != nullptr){if (tmpNode->_left == Parent){tmpNode->_left = subR;}else{tmpNode->_right = subR;}subR->_parent = tmpNode;}else{root = subR;subR->_parent = nullptr;}}void _InOrder(Node* cur){if (cur == nullptr){return;}_InOrder(cur->_left);cout << cur->_val.first << ":"<<cur->_val.second<<endl;_InOrder(cur->_right);}int _Height(Node* cur){if (cur == nullptr){return 0;}int Left = _Height(cur->_left);int Right = _Height(cur->_right);return Left > Right ? Left + 1 : Right + 1;}int _Size(Node* cur){if (cur == nullptr){return 0;}return 1 + _Size(cur->_left) + _Size(cur->_right);}};

test.cpp

#include<iostream>
#include<vector>
#include"BRTree.h"using namespace std;void TestAVLTree1()
{RBTree<int, int> t;// 常规的测试⽤例int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };// 特殊的带有双旋场景的测试⽤例//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto e : a){t.Insert({ e, e });}t.InOrder();//cout << t.IsBalanceTree() << endl;cout<<t.IsBalance();
}void TestAVLTree2()
{const int N = 1000000;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 << t.IsBalance() << endl;cout << "Insert:" << end2 - begin2 << 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()
{//TestAVLTree1();TestAVLTree2();return 0;
}

以上就是本篇的全部内容了，在实现了红黑树之后接下来我们就可以基于红黑树来自己实现封装set和map，未完待续……

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/39425.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

java实现coze平台鉴权+工作流调用（踩坑记录）

java实现coze平台鉴权+工作流调用（踩坑记录）

问题偏多建议大家看完文章后再开始实现 OAuth鉴权 https://www.coze.cn/open/docs/developer_guides/preparation https://www.coze.cn/open/docs/developer_guides/oauth_apps OAuth 授权码鉴权 https://www.coze.cn/open/docs/developer_guides/oauth_code 创建OAuth应…
阅读更多...
2025年优化算法：龙卷风优化算法（Tornado optimizer with Coriolis force，TOC）

2025年优化算法：龙卷风优化算法（Tornado optimizer with Coriolis force，TOC）

龙卷风优化算法&#xff08;Tornado optimizer with Coriolis force&#xff09;是发表在中科院二区期刊“ARTIFICIAL INTELLIGENCE REVIEW”&#xff08;IF&#xff1a;11.7&#xff09;的2025年智能优化算法 01.引言 当自然界的狂暴之力&#xff0c;化身数字世界的智慧引擎&…
阅读更多...
面试题分享-多线程顺序打印奇偶数

面试题分享-多线程顺序打印奇偶数

目录 1.题目详情 2.解题思路 2.1.分析题目 2.2.解析思路 3.代码实现 4.运行结果 1.题目详情 昨天刷抖音&#xff0c;遇到一个面试题&#xff0c;描述如下&#xff1a; 请使用两个线程&#xff0c;分别顺序交替打印奇数和偶数&#xff0c;直到10为止。例如有两个线程&#…
阅读更多...
QuecPython 网络协议之TCP/UDP协议最祥解析

QuecPython 网络协议之TCP/UDP协议最祥解析

概述 IP 地址与域名 IP 地址是网络中的主机地址&#xff0c;用于两台网络主机能够互相找到彼此&#xff0c;这也是网络通信能够成功进行的基础。IP 地址一般以点分十进制的字符串来表示&#xff0c;如192.168.1.1。 ​ 我们日常访问的网站&#xff0c;其所在的服务器主机都有…
阅读更多...
React - LineChart组件编写（用于查看每日流水图表）

React - LineChart组件编写（用于查看每日流水图表）

一、简单版本 LineChart.tsx // src/component/LineChart/LineChart.tsx import React, {useEffect,useRef,useImperativeHandle,forwardRef,useMemo,useCallback, } from react; import * as echarts from echarts/core; import type { ComposeOption } from echarts/core; …
阅读更多...
医学图像分割数据集肺分割数据labelme格式6299张2类别

医学图像分割数据集肺分割数据labelme格式6299张2类别

数据集格式&#xff1a;labelme格式(不包含mask文件&#xff0c;仅仅包含jpg图片和对应的json文件) 图像分辨率&#xff1a;1024x1024 图片数量(jpg文件个数)&#xff1a;6299 标注数量(json文件个数)&#xff1a;6299 标注类别数&#xff1a;2 标注类别名称:["leftl…
阅读更多...
帕金森病致生活艰难，如何缓解心理负担？

帕金森病致生活艰难，如何缓解心理负担？

你是否留意到身边有人手部不由自主地颤抖&#xff0c;且肢体变得僵硬&#xff0c;行动也愈发迟缓&#xff1f;这很可能是帕金森病的症状。帕金森病是一种常见的神经系统退行性疾病&#xff0c;多发生于中老年人。​ 静止性震颤往往是帕金森病的首发症状&#xff0c;患者在安静状…
阅读更多...
从零构建大语言模型全栈开发指南：第二部分：模型架构设计与实现-2.1.1自注意力机制（Scaled Dot-Product Attention）的逐行代码实现

从零构建大语言模型全栈开发指南：第二部分：模型架构设计与实现-2.1.1自注意力机制（Scaled Dot-Product Attention）的逐行代码实现

👉 点击关注不迷路 👉 点击关注不迷路 👉 点击关注不迷路 文章大纲 2.1.1 自注意力机制（Scaled Dot-Product Attention）的逐行代码实现1. 自注意力机制的核心原理与数学表达1.1 注意力计算的三元组：`Q, K, V`2. 逐行代码实现与解析2.1 输入嵌入与权重矩阵初始化2.2 完…
阅读更多...
机械臂【逆运动学】

机械臂【逆运动学】

回顾正运动学fk&#xff1a; IK&#xff1a; 几何法 代数法 六轴 456轴交再同一点 有解析解 下列公式为正运动学部分结论 a和d是长度 &#xff0c;theta和alfa是角度 **疑问&#xff1a;alfa00&#xff1f; Z轴互相平行 ** 已知末端要在空间XYZ处如下 绿色项&#x…
阅读更多...
IDEA批量替换项目下所有文件中的特定内容

IDEA批量替换项目下所有文件中的特定内容

文章目录 1. 问题引入2. 批量替换项目下所有文件中的特定内容2.1 右键项目的根目录&#xff0c;点击在文件中替换2.2 输入要替换的内容 3. 解决替换一整行文本后出现空行的问题4. 增加筛选条件提高匹配的精确度 更多 IDEA 的使用技巧可以查看 IDEA 专栏&#xff1a; IDEA 1. 问…
阅读更多...
Ubuntu22.04美化MacOS主题

Ubuntu22.04美化MacOS主题

安装Tweaks 参考Ubuntu 22.04 桌面美化成Mac风格这篇更好点 sudo apt install gnome-tweaks gnome-shell-extensions -y安装macos主题 git clone https://github.com/vinceliuice/WhiteSur-gtk-theme.git # 进到文件目录 ./install.sh -t all -N glassy sudo ./tweaks.sh -g…
阅读更多...
基于Python的机器学习入门指南

基于Python的机器学习入门指南

在当今数字化时代&#xff0c;机器学习&#xff08;Machine Learning&#xff09;已经成为科技领域中最热门的话题之一。它不仅改变了我们对数据的理解和处理方式&#xff0c;还在许多行业中得到了广泛应用&#xff0c;如金融、医疗、交通等。Python作为一门强大的编程语言&…
阅读更多...
Python前缀和(例题：异或和，求和)

Python前缀和(例题：异或和，求和)

前缀和 前缀和&#xff1a;对于一个长度为n的列表a&#xff0c;前缀和为&#xff1a; sum[i]a[0]a[1]...a[i] 前缀和的性质&#xff1a; 第一条性质用于处理出前缀和&#xff1a; Sum[i]Sum[i-1]a[i] 第二条性质可以在O(l)的时间内求出区间和&#xff1a; a[l]....a[r] S…
阅读更多...
统计矩的高阶推广：经验还是理论推导？

统计矩的高阶推广：经验还是理论推导？

矩的发展既是经验总结的结果&#xff0c;也是数学理论推导的产物。研究者们在分析数据、描述物理现象的过程中&#xff0c;发现了低阶矩与日常物理概念&#xff08;如质心、惯性&#xff09;之间的紧密联系&#xff0c;而高阶矩的应用往往出现在更复杂的数学体系中&#xff0c;…
阅读更多...
安宝特分享｜AR智能装备赋能企业效率跃升

安宝特分享｜AR智能装备赋能企业效率跃升

AR装备开启智能培训新时代 在智能制造与数字化转型浪潮下&#xff0c;传统培训体系正面临深度重构。安宝特基于工业级AR智能终端打造的培训系统&#xff0c;可助力企业构建智慧培训新生态。 AR技术在不同领域的助力 01远程指导方面 相较于传统视频教学的单向输出模式&#x…
阅读更多...
《软件安装与使用教程》— NVIDIA CUDA在Windows的安装教程

《软件安装与使用教程》— NVIDIA CUDA在Windows的安装教程

《软件安装与使用教程》— NVIDIA CUDA在Windows的安装教程 Installed: - Nsight Monitor Not Installed: - Nsight for Visual Studio 2019 Reason: VS2019 was not found - Nsight for Visual Studio 2017 Reason: VS2017 was not found - Integrated Graphics Frame Debugge…
阅读更多...
领域驱动设计（DDD）实践入门

领域驱动设计（DDD）实践入门

文章目录 1.认识领域驱动设计1.1 简介1.2 发展历史1.3 DDD 的兴起 2.从一个简单案例2.1 转账需求2.2 设计的问题2.3 违反的设计原则 3.使用 DDD 进行重构抽象数据存储层抽象第三方服务抽象中间件封装业务逻辑重构后的架构 4.小结参考文献 1.认识领域驱动设计 1.1 简介 领域驱…
阅读更多...
OrangePi 5B 内核开启 CONFIG_CIFS 通过 Samba 挂载 NAS 路径

OrangePi 5B 内核开启 CONFIG_CIFS 通过 Samba 挂载 NAS 路径

文章目录 OrangePi 5B 内核开启 CONFIG_CIFS 通过 Samba 挂载 NAS 路径获取 Linux SDK 的源码从 github 下载 orangepi-build编译 linux 内核更新开发板内核上传编译好的 deb 包到开发板登录开发板&#xff0c;卸载旧内核安装新内核重启开发板 Ubuntu & Debian 系统下挂载 …
阅读更多...
8662 234的和

8662 234的和

8662 234的和 ⭐️难度&#xff1a;中等 &#x1f31f;考点&#xff1a;模拟、二维前缀和 &#x1f4d6; &#x1f4da; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner;public class Main {static int[] a ne…
阅读更多...
softmax回归的实现

softmax回归的实现

softmax回归是logistic回归在多分类问题上的推广 原理 网络架构&#xff1a; 常用的方式是独热编码&#xff1a; 如果下面这样&#xff0c;会使得分类器更倾向于把奶牛和耗牛预测到一起&#xff0c;因为预测为海公牛惩罚更大&#xff0c;这样是不合理的。 损失函数&…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023