当前位置： 首页 > news >正文

【STL】红黑树的全面探索与红黑树的实现

news 来源：原创 2024/9/19 2:14:04

ps：文章最后有完整的代码

1.红黑树的概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的

2.红黑树的性质

1. 根节点⼀定是⿊⾊

2. ⼀条简单路径下不会出现连续的红⾊节点，如果⽗亲节点为红⾊，则其孩⼦节点⼀定为⿊⾊，如果⽗亲节点为⿊⾊，则没有限制

3. 对于每个节点来说，从该节点开始到其后代所有节点的简单路径上均包含相同数量的⿊⾊节点

4. （了解）每个空叶⼦结点都是⿊⾊的

在上图中，NIL 表示空叶⼦节点，以NIL 作为结束条件，⼀共有11 条路径，需要注意不是以叶⼦节点为结束条件（即不是7 条路径

满⾜上⾯的四个性质，红⿊树就可以保证其相对平衡的条件：红黑树可以保证最长路径会比最短路径的长度长出两倍。

最短路径：节点颜⾊为全⿊的路径，此时⿊⾊节点的个数即为路径的⻓度 最⻓路径：节点颜⾊为红⾊和⿊⾊交替出现的路径

3.红黑树的节点结构及定义

红黑树节点的定义通常包含以下几个关键部分：

3.1 基本元素

  • _left：指向节点的左子节点的指针
  • _right：指向节点的右子节点的指针
  • _parent：指向节点的父节点的指针
  • _kv：一个结构体或配对（pair），包含节点的键值（key）和值（value）。这取决于红黑的具体用途，可能只包含键或包含键值对。
  • _col：表示当前节点的颜色。

3.2 节点颜色（_col）

  • 在上面的定义中，_col 成员变量用于表示节点的颜色，通过 Color 枚举类型来定义，可以是 RED 或 BLACK。

3.3 构造函数

  • 初始化一个新节点时，通常需要一个构造函数，它接受一个键值对（或仅键），并设置节点的左子节点、右子节点、父节点和颜色（初始化为红色）

3.4BR节点定义：

template<class K, class V>
struct BSTreeNode
{BSTreeNode<K, V>* _left;    //左子树BSTreeNode<K, V>* _right;   //右子树BSTreeNode<K, V>* _parent;  //父亲pair<K, V> _kv;       //存放节点值的string _col;    //颜色（通过这个可以直到左右子树存在情况）//构造函数BSTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col("RED")     //默认颜色为红色{}
};

红黑树的节点结构与二叉搜索树和AVL树差别不大，最大的差别就是加入了一个新的存储点——颜色

4.红⿊树的性质与平衡控制关系

因为⿊⾊节点的个数可以决定⼀条路径的⻓度，假设⿊⾊节点的个数为 h ，则最短路径的⻓度也为 h ，满⾜第⼆条规则时，红⾊节点的 个数不会超过⿊⾊节点（ 1 个或者 h 个），从⽽最⻓路径的最⼤⻓度为 2h ，因为红⾊节点是在⿊⾊节点出现后才会出现。

如果按照下图的插⼊⽅式导致红⾊节点连续出现

违反了规则⼆，此时最短路径的⻓度的两倍会⼩于最⻓路径的⻓度，从⽽打破了红⿊树的平衡。

如果插⼊的 27 为⿊⾊节点，则最⻓路径的⻓度增加，并且⿊⾊节点的个数也增加，违反了规则三，此时对于其他路径来说也需要增加 ⼀个⿊⾊节点。

所以为了维持平衡，不可以插⼊⿊⾊节点，此时最⻓路径的⻓度刚好为 2h ，如下图所示：

综上所述，在满⾜第⼆条规则和第三条规则下可以保证红⿊树的最⻓路径始终不会超过最短路径的 2 倍

5.红黑树的插入

根据红⿊树的性质可以看出红⿊树如何控制⾼度近似平衡，但是如果插⼊了节点，可能会破坏原有的平衡，此时需要通过重新填⾊或 者旋转调整使红⿊树重新达到平衡

在前⾯的分析中可以得知，如果插⼊的节点是⿊⾊节点，可能会导致每⼀条路径都需要多⼀个⿊⾊节点，为了更加⽅便处理，规定插 入的节点是红色节点

情况1 ：不需要调整

如果插⼊的节点是红色节点，并且其⽗亲节点是黑色节点，此时不需要进⾏任何处理，当⽗亲节点是⿊⾊节点时，保证了规则三没有 违背，因为⿊⾊节点的个数决定了⾼度，插⼊前如果保证原树是红⿊树，那么⾼度⼀定满⾜红⿊树的近似平衡，并且此时插⼊红⾊节 点也不会违背规则⼆，如下图的⼀种情况所示：

情况2 ： uncle 节点为红⾊

如果 cur 的节点是红⾊，并且其⽗亲节点（假设为 parent ）是红⾊节点，此时说明⽗亲的兄弟节点（假设为 uncle ）也⼀定为红⾊， 因为插⼊前⼀定是红⿊树（插⼊前不是红⿊树那么插⼊前就已经出现了不平衡，需要进⾏调整），当⽗亲节点时红⾊，说明⽗亲节点 所在的路径缺少⿊⾊节点，违反了规则三。⽗亲节点的⽗亲节点（假设为 grandfather ）也⼀定为⿊⾊，如果为红⾊则违反了第⼆条 规则所以插⼊前的状态应该为：

cur 节点可能为新增的红⾊节点，也可能为上⼀次调整变为的红⾊节点

1. 假设 a 、 b 、 c 、 d 和 e 为⿊⾊节点个数为 0 的红⿊树，此时 cur 为新插⼊节点如下图所示：

因为出现了连续的红⾊节点，为了恢复红⿊树的平衡，此时需要进⾏调整，因为 uncle 节点为红⾊，为了保证每条路径上都有⼀ 个⿊⾊节点并且保证没有连续的红⾊节点出现，将 parent 节点的颜⾊改为⿊⾊，将 uncle 节点的颜⾊改为⿊⾊，将 节点改为红⾊（如果 grandfather 节点为根节点则再处理为⿊⾊），处理完后， cur = grandfather 继续向上调整直到遇到根节 点：

2、假设 a 、 b 、 c 、 d 和 e 为⿊⾊节点个数⼤于 0 ，此时 cur 为上⼀次调整变成的红⾊节点，如下图所示：

对于当前情况来说，只有 cur 位置的节点是红⾊，其余⼏棵⼦树已经通过调整变成了符合规则的红⿊树，所以也可以归类为上⾯ 的情形，处理⽅式与上⾯相同

情况3 ： uncle 节点为⿊⾊

uncle 节点为⿊⾊时⼀共有两种情况：

1. uncle 节点不存在

2. uncle 节点存在且为⿊

因为红⿊树规定下空节点是⿊⾊的，所以 析，对于 uncle 节点不存在与存在且为⿊可以视为⼀种情况，下⾯主要以 uncle 节点不存在进⾏分 uncle 节点存在且为⿊的情况给出⼀种分析，剩下与 uncle 节点不存在的情况类似

当 cur 节点在 parent 的左⼦树并且 parent 在 grandfather 的左⼦树时，此时需要进⾏右单旋，将 parent 的颜⾊更新为⿊⾊，grandfather 的颜⾊更新为红⾊，原因类⽐左单旋，过程如下图所示：

当 cur 节点在 parent 的右⼦树并且 parent 在grandfather 的左⼦树时，此时需要进⾏左右双旋，将 cur 的颜⾊更新为⿊⾊，将grandfather 的颜⾊更新为红⾊，过程如下：

当 cur 节点在 parent 的左⼦树并且 parent 在grandfather 的右⼦树时，此时需要进⾏右左双旋，将 cur 的颜⾊更新为⿊⾊，将grandfather 的颜⾊更新为红⾊，过程如下：

如果 un cle 节点本身存在，那么经过 uncle 节点的路径下⽅的两个⼦树为红⾊，而parent 插⼊节点前⾄少会有⼀个⿊⾊节点，如下图：

此时在 parent 的右侧插⼊⼀个 cur 节点（本身就是红⾊节点 cur 节点也是如此）如下：

此时如果只是对 parent 节点的颜⾊进⾏改变，则会出现 parent 所在路径⽐uncle 所在路径多⼀个⿊⾊节点，所以为了解决这个问题，单单改变颜⾊⽆法解决，当 cur在parent 的右边时，只需要⼀次左单旋即可，⽽ cur 在 parent 的左边时，需要先进⾏右旋再进⾏左旋，以右左双旋为例，如下图所示：

6、检测红黑树是否造到破坏代码演示(C++)：

while (parent && parent->_col == RED) //当父亲节点为红色，则出现了连续的红色，不符合条件{Node* grandfather = parent->_parent;//    g//  p   uif (parent == grandfather->_left) {	Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED) //叔叔存在并且为红{parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent; //往上面走}else{//u存在且为黑或不存在 ->变色再继续往上处理 + 变色if (cur == parent->_left) { //cur存在那么cur一定为红色 //    g//  p   u//c//单旋，把p旋转上去，p作为子树根节点，g作为p的右RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//    g//  p   u//    c//双旋，将cur旋转上去，p作为cur的左，然后再旋转把cur旋转上去，g作为cur右边RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{//    g//  u   pNode* uncle = grandfather->_left;// 叔叔存在且为红，-》变色即可if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent;}else // 叔叔不存在，或者存在且为黑{// 情况二：叔叔不存在或者存在且为黑// 旋转+变色//      g//   u     p//            cif (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//		g//   u     p//      cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}

7.红黑树的验证

  • 检测其是否满足二叉搜索树(中序遍历是否为有序序列)
  • 检测其是否满足红黑树的性质
  • 中序遍历的代码演示
void InOrder()
{_InOrder(_root);cout << endl;
}
void _InOrder(Node* root)
{if (root == nullptr) return;_InOrder(root->_left);_cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);
}

检测其是否满足红黑树的性质(C++)

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);
}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->_kv.first << "存在连续的红色节点" << endl;return false;}if (root->_col == BLACK){blackNum++;}return Check(root->_left, blackNum, refNum)&& Check(root->_right, blackNum, refNum);
}

8.完整代码

#include<iostream>
#include<vector>
#include<assert.h>
using namespace std;enum Colour
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{pair<K, V> _kv;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Colour _col;RBTreeNode(const pair<K, V>& kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr){}
};template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:RBTree() = default;RBTree(const RBTree<K, V>& t){_root = Copy(t._root);}RBTree<K, V>& operator=(RBTree<K, V> t){swap(_root, t._root);return *this;}~RBTree(){Destroy(_root);_root = nullptr;}bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK; //根节点默认为黑色return true;}Node* parent = nullptr;Node* cur = _root;while (cur){parent = cur;if (cur->_kv.first < kv.first) cur = cur->_right;else if (cur->_kv.first > kv.first) cur = cur->_left;else return false;}cur = new Node(kv);// 新增节点。颜色红色给红色cur->_col = RED;if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;while (parent && parent->_col == RED) //当父亲节点为红色，则出现了连续的红色，不符合条件{Node* grandfather = parent->_parent;//    g//  p   uif (parent == grandfather->_left) {Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED) //叔叔存在并且为红{parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent; //往上面走}else{//u存在且为黑或不存在 ->变色再继续往上处理 + 变色if (cur == parent->_left) { //cur存在那么cur一定为红色 //    g//  p   u//c//单旋，把p旋转上去，p作为子树根节点，g作为p的右RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//    g//  p   u//    c//双旋，将cur旋转上去，p作为cur的左，然后再旋转把cur旋转上去，g作为cur右边RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{//    g//  u   pNode* uncle = grandfather->_left;// 叔叔存在且为红，-》变色即可if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent;}else // 叔叔不存在，或者存在且为黑{// 情况二：叔叔不存在或者存在且为黑// 旋转+变色//      g//   u     p//            cif (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//		g//   u     p//      cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK; //无论什么情况根节点都为黑return true;}void InOrder(){_InOrder(_root);cout << endl;}int Height(){return _Height(_root);}int Size(){return _Size(_root);}Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return nullptr;}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: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->_kv.first << "存在连续的红色节点" << endl;return false;}if (root->_col == BLACK){blackNum++;}return Check(root->_left, blackNum, refNum)&& Check(root->_right, blackNum, refNum);}int _Size(Node* root){return root == nullptr ? 0 : _Size(root->_left) + _Size(root->_right) + 1;}int _Height(Node* root){if (root == nullptr)return 0;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}void RotateL(Node* parent){_rotateNum++;Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* parentParent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (parentParent == nullptr){_root = subR;subR->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}}void  RotateR(Node* parent){_rotateNum++;Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* parentParent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (parentParent == nullptr){_root = subL;subL->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}}void Destroy(Node* root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;}Node* Copy(Node* root){if (root == nullptr) return nullptr;Node* newRoot = new Node(root->_kv);newRoot->_left = Copy(root->_left);newRoot->_right = Copy(root->_right);return newRoot;}private:Node* _root = nullptr;public:int _rotateNum = 0;
};void TestRBTree1()
{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.IsBalance() << endl;
}

9.添加完整注释的代码

#pragma once
#include<iostream>
#include<vector>
#include<assert.h>
using namespace std;enum Colour
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{pair<K, V> _kv;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Colour _col;RBTreeNode(const pair<K, V>& kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr){}
};template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node; // 节点类型的别名。public:// 默认构造函数，初始化一个空的红黑树。RBTree() = default;// 拷贝构造函数，创建源树的深拷贝。RBTree(const RBTree<K, V>& t){_root = Copy(t._root); // 从源树复制根节点。}// 赋值运算符重载，交换当前树和另一个树的内容。RBTree<K, V>& operator=(RBTree<K, V> t){swap(_root, t._root); // 交换当前树和输入树的根节点指针。return *this; // 返回当前实例。}// 析构函数，清理树中的所有节点以避免内存泄漏。~RBTree(){Destroy(_root); // 从根节点开始销毁所有节点。_root = nullptr; // 确保销毁后根节点指针为 null。}bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv); // 树为空时，创建根节点。_root->_col = BLACK; // 根节点颜色设置为黑色。return true;}Node* parent = nullptr;Node* cur = _root;while (cur){parent = cur; // 记录当前节点的父节点。if (cur->_kv.first < kv.first) cur = cur->_right; // 按键值比较，移动到右子树。else if (cur->_kv.first > kv.first) cur = cur->_left; // 移动到左子树。else return false; // 键值已存在，插入失败。}cur = new Node(kv); // 创建新节点。cur->_col = RED; // 新节点颜色设置为红色。if (parent->_kv.first < kv.first){parent->_right = cur; // 将新节点作为父节点的右子节点。}else{parent->_left = cur; // 将新节点作为父节点的左子节点。}cur->_parent = parent; // 设置新节点的父节点。// 修正红黑树的性质：如果父节点为红色，则可能需要调整。while (parent && parent->_col == RED){Node* grandfather = parent->_parent; // 获取祖父节点。if (parent == grandfather->_left){Node* uncle = grandfather->_right; // 获取叔叔节点。if (uncle && uncle->_col == RED) // 叔叔节点存在且为红色。{// 变色处理。parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather; // 继续向上调整。parent = cur->_parent;}else{// 叔叔节点不存在或为黑色。if (cur == parent->_left){// 单旋转：父节点成为新的根节点。RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{// 双旋转：先对父节点进行左旋，再对祖父节点进行右旋。RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break; // 调整完毕，退出循环。}}else{// 对称处理：如果父节点是祖父节点的右子节点。Node* uncle = grandfather->_left; // 获取叔叔节点。if (uncle && uncle->_col == RED) // 叔叔节点存在且为红色。{// 变色处理。parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather; // 继续向上调整。parent = cur->_parent;}else{// 叔叔节点不存在或为黑色。if (cur == parent->_right){// 单旋转：祖父节点成为新的根节点。RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{// 双旋转：先对父节点进行右旋，再对祖父节点进行左旋。RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break; // 调整完毕，退出循环。}}}_root->_col = BLACK; // 根节点始终保持黑色。return true; // 插入成功。}void InOrder(){_InOrder(_root);cout << endl;}int Height(){return _Height(_root);}int Size(){return _Size(_root);}Node* Find(const K& key){Node* cur = _root; // 从根节点开始查找。while (cur){if (cur->_kv.first < key){cur = cur->_right; // 如果当前节点的键值小于目标键值，移动到右子节点。}else if (cur->_kv.first > key){cur = cur->_left; // 如果当前节点的键值大于目标键值，移动到左子节点。}else{return cur; // 找到目标键值，返回当前节点。}}return nullptr; // 如果遍历完整棵树仍未找到目标键值，返回空指针。}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: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 && root->_parent->_col == RED){cout << root->_kv.first << "存在连续的红色节点" << endl;return false;}// 如果当前节点是黑色，增加黑色节点计数if (root->_col == BLACK){blackNum++;}// 递归检查左子树和右子树return Check(root->_left, blackNum, refNum)&& Check(root->_right, blackNum, refNum);}int _Size(Node* root){return root == nullptr ? 0 : _Size(root->_left) + _Size(root->_right) + 1;}int _Height(Node* root){if (root == nullptr)return 0;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}void RotateL(Node* parent){_rotateNum++;Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* parentParent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (parentParent == nullptr){_root = subR;subR->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}}void  RotateR(Node* parent){_rotateNum++;Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* parentParent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (parentParent == nullptr){_root = subL;subL->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}}void Destroy(Node* root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;}Node* Copy(Node* root){if (root == nullptr) return nullptr;Node* newRoot = new Node(root->_kv);newRoot->_left = Copy(root->_left);newRoot->_right = Copy(root->_right);return newRoot;}private:Node* _root = nullptr;public:int _rotateNum = 0;
};void TestRBTree1()
{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.IsBalance() << endl;
}

相关文章：

  • 北京网站建设多少钱？
  • 辽宁网页制作哪家好_网站建设
  • 高端品牌网站建设_汉中网站制作
  • SQL SERVER日常表碎片和统计信息优化脚本
  • 构建Dubbo工程详解
  • Android Studio Koala下载并安装，测试helloworld.
  • 力扣--1657.确定两个字符串是否接近
  • 氛围感视频素材高级感的去哪里找啊？带氛围感的素材网站库分享
  • 力扣45.跳跃游戏II
  • 通过ICMP判断网络故障
  • Qt：鼠标事件
  • 最近公共祖先（LCA），树上差分，树的直径总结
  • Python优化算法12——蝴蝶优化算法(BOA)
  • vscode解决运行程序无法从控制台输入问题
  • vue的vue.config.js中反向代理pathRewite的理解
  • html2canvas ios慎用和createImageBitmap ios慎用
  • 12、stm32通过dht11读取温湿度
  • TCP粘包和抓包
  • [case10]使用RSQL实现端到端的动态查询
  • ➹使用webpack配置多页面应用(MPA)
  • Bootstrap JS插件Alert源码分析
  • CSS 三角实现
  • Laravel Mix运行时关于es2015报错解决方案
  • leetcode388. Longest Absolute File Path
  • MySQL-事务管理（基础）
  • nodejs：开发并发布一个nodejs包
  • React 快速上手 - 06 容器组件、展示组件、操作组件
  • underscore源码剖析之整体架构
  • 笨办法学C 练习34：动态数组
  • - 概述 - 《设计模式（极简c++版）》
  • 回流、重绘及其优化
  • 使用阿里云发布分布式网站，开发时候应该注意什么？
  • 微信小程序填坑清单
  • 我是如何设计 Upload 上传组件的
  • 中文输入法与React文本输入框的问题与解决方案
  • 转载：[译] 内容加速黑科技趣谈
  • AI又要和人类“对打”，Deepmind宣布《星战Ⅱ》即将开始 ...
  • NLPIR智能语义技术让大数据挖掘更简单
  • PostgreSQL之连接数修改
  • #### golang中【堆】的使用及底层 ####
  • #DBA杂记1
  • （C语言）球球大作战
  • （DFS + 剪枝）【洛谷P1731】 [NOI1999] 生日蛋糕
  • （仿QQ聊天消息列表加载）wp7 listbox 列表项逐一加载的一种实现方式，以及加入渐显动画...
  • (每日持续更新）jdk api之StringBufferInputStream基础、应用、实战
  • （推荐）叮当——中文语音对话机器人
  • （万字长文）Spring的核心知识尽揽其中
  • （转）平衡树
  • (转载)在C#用WM_COPYDATA消息来实现两个进程之间传递数据
  • (自适应手机端)响应式服装服饰外贸企业网站模板
  • (自适应手机端)行业协会机构网站模板
  • ./include/caffe/util/cudnn.hpp: In function ‘const char* cudnnGetErrorString(cudnnStatus_t)’: ./incl
  • .bashrc在哪里，alias妙用
  • .net CHARTING图表控件下载地址
  • .Net Core/.Net6/.Net8 ，启动配置/Program.cs 配置
  • .NET Core中的去虚
  • .Net Framework 4.x 程序到底运行在哪个 CLR 版本之上
  • .NET 的程序集加载上下文