## 【数据结构】红黑树（RBTree）

news/2024/4/24 18:24:36/文章来源:https://blog.csdn.net/m0_73865858/article/details/136352322

## 介绍

### 性质

1. 每个结点不是红色就是黑色。
2. 根节点是黑色的。
3. 如果一个节点是红色的，则它的两个孩子结点是黑色的。（不能出现连续红色）
4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

## 红黑树的插入调整

### 情况一： cur为红，p为红，g为黑，u存在且为红

u存在且为红，p，u变黑，g变红。

### 情况二：cur为红，p为红，g为黑，u不存在/u存在且为黑（一定由情况一变化调整而来）

p为g的左孩子，cur为p的左孩子，则进行右单旋
p为g的右孩子，cur为p的右孩子，则进行左单旋

### 情况三：比情况二多了次旋转而已

``````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){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);if (kv.first > parent->_kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;while (parent && parent->_col == RED){Node* grandfather = parent->_parent;if (grandfather->_left == parent){Node* uncle = grandfather->_right;//u存在且为红，变色处理，并继续往上处理if (uncle && uncle->_col == RED){parent->_col = BlACK;uncle->_col = BlACK;grandfather->_col = RED;//continue to modifycur = grandfather;parent = cur->_parent;}//u不存在或u存在且为黑，旋转+变色else{//   g//  p  u//cif (cur == parent->_left){RotateR(grandfather);parent->_col = BlACK;grandfather->_col = RED;}else{//	  g//  p   u//    cRotateL(parent);RotateR(grandfather);parent->_col = RED;grandfather->_col = RED;cur->_col = BlACK;}break;}}else{Node* uncle = grandfather->_left;//u存在且为红，变色处理，并继续往上处理if (uncle && uncle->_col == RED){parent->_col = BlACK;uncle->_col = BlACK;grandfather->_col = RED;//continue to modifycur = grandfather;parent = cur->_parent;}//u不存在或u存在且为黑，旋转+变色else{//   g//  u  p//       cif (cur == parent->_right){RotateL(grandfather);parent->_col = BlACK;grandfather->_col = RED;}else{//	  g//  u   p//    cRotateR(parent);RotateL(grandfather);parent->_col = RED;grandfather->_col = RED;cur->_col = BlACK;}break;}}_root->_col = BlACK;}return true;}
``````

## 红黑树的拷贝构造

``````RBTree(const RBTree& rb){_root = CopyTree(rb._root, nullptr);}Node*  CopyTree(Node* rbroot,Node* parent){if (rbroot == nullptr)return nullptr;Node* newroot = new Node(rbroot->_kv);newroot->_col = rbroot->_col;newroot->_parent = parent;newroot->_left = CopyTree(rbroot->_left, newroot);newroot->_right = CopyTree(rbroot->_right, newroot);return newroot;}
``````

## set和map

### RBTree的Iterator

``````template<class T,class Ref,class Ptr>
struct __RBTreeIterator
{typedef RBTreeNode<T> Node;typedef __RBTreeIterator<T, Ref, Ptr> Self;Node* _node;__RBTreeIterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator != (const Self & s){return _node != s._node;}Self& operator++(){if (_node->_right){//1.右不为空，找右子树的最左节点Node* subleft = _node->_right;while (subleft->_left){subleft = subleft->_left;}_node = subleft;}else{//2.右为空，沿着到根的路径，找孩子是父亲左的那个祖先Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}Self& operator--(){if (_node->_left){//左不为空，找左子树的最右节点Node* subright = _node->_left;while (subright->_right){subright = subright->_right;}_node = subright;}else{//左为空，找孩子是父亲的右的祖先Node* cur = _node;Node* parent = cur->_parent;while (parent && parent->_left == cur){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}
};
template<class K,class T,class KeyOfT>
class RBTree
{typedef RBTreeNode<T> Node;
public:typedef __RBTreeIterator<T, T&, T*> iterator;typedef __RBTreeIterator<const T, const T&, const T*> const_iterator;iterator begin(){Node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return iterator(cur);}iterator end(){return iterator(nullptr);}``````

### 专家解读：2024年十大项目管理工具综合排名与评价

2024年涌现出一批新的项目管理工具&#xff0c;各具特色的功能和设计为企业解决了诸多的管理难题。今天我们就来盘点2024年的十款项目管理工具Zoho Projects、AgileMaster、PlanItAll、CommuniQ、WorkFlowRanger、GanttGenius、RiskAssessor、TeamHarmony、BudgetBoss、CloudCo…

### #QT（DEMO）

1.IDE&#xff1a;QTCreator 2.实验&#xff1a;打印"hello wolrd" 3.记录 &#xff08;1&#xff09;创建一个新工程&#xff1a; 新建好一个工程存放文件夹&#xff08;路径不能有中文&#xff09;,然后按下图配置 &#xff08;2&#xff09;点击widgets.ui拖入以…

### 如何查看前端的vue项目是vue2还是vue3项目

1. 检查package.json文件 在项目的根目录下&#xff0c;打开package.json文件&#xff0c;查找dependencies或devDependencies部分中的vue条目。版本号将告诉你是Vue 2还是Vue 3。例如&#xff1a; Vue 2.x: "vue": "^2.x.x"Vue 3.x: "vue": &…

### uipath调用js代码

1&#xff0c;调用js代码&#xff0c;不带参数&#xff0c;没有返回值 为了去掉按钮的disabled属性 function(){ document.getElementsByClassName(submitBtn)[0].removeAttribute(disabled); } 2&#xff0c;调用js代码&#xff0c;带参数&#xff0c;没有返回值 输入参数&a…

### Hololens 2应用开发系列（2）——MRTK基础知识及配置文件配置（上）

Hololens 2应用开发系列&#xff08;2&#xff09;——MRTK基础知识及配置文件配置 一、前言二、MRTK基础知识2.1 MRTK概述2.2 MRTK运行逻辑2.3 MRTK配置文件介绍2.4 MRTK服务 三、配置文件使用3.1 总配置文件3.2 相机配置3.3 其他配置 参考文献 一、前言 在前面的文章中&…

### 【CSP试题回顾】201503-3-节日

CSP-201503-3-节日 关键点&#xff1a;格式化输出 在C中&#xff0c;格式化输出通常利用iostream库中的功能&#xff0c;特别是iomanip头文件提供的一系列操作符。这些操作符用于控制输出格式&#xff0c;如宽度、填充、对齐方式等。在你提供的代码中&#xff0c;用于格式化输…