c++进阶之------红黑树

embedded/2025/3/29 8:56:08/

一、概念

红黑树（Red-Black Tree）是一种自平衡二叉查找树，它在计算机科学的许多领域中都有广泛应用，比如Java中的TreeMap和C++中的set/map等数据结构的底层实现。红黑树通过在每个节点上增加一个颜色属性（红色或黑色），并遵循一定的规则来确保树的平衡性，从而保证了各项操作的时间复杂度为O(log n)。

二、性质

红黑树具有以下性质：

  1. 每个节点是红色或黑色。

  2. 根节点是黑色。

  3. 所有叶子节点（NIL节点）是黑色。

  4. 如果一个节点是红色，则它的两个子节点都是黑色。（注：这条规则保证了从任一节点到其每个叶子节点的所有路径上不会出现两个连续的红色节点）

  5. 从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。

三、构建红黑树

3.1 树的基本结构

#pragma once// 枚举值表示颜色
enum color
{RED,BLACK
};
// 这里我们默认按key/value结构实现
template<class K,class V>
struct RBTreeNode
{// 这里更新控制平衡也要加入parent指针pair<k, v> _kv;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;color _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:
private:Node* _root = nullptr;
};

3.2 树的插入

在红黑树中插入一个节点后，可能会破坏红黑树的性质，因此需要通过旋转和重新着色来恢复红黑树的平衡。插入操作的具体步骤如下：

  1. 插入节点：按照普通二叉查找树的插入方式插入新节点，并将新节点着色为红色。

  2. 检查平衡性：检查插入新节点后是否破坏了红黑树的性质。如果插入的新节点是根节点，则直接将其着色为黑色；如果新节点的父节点是黑色，则红黑树的性质未被破坏，插入结束；如果新节点的父节点是红色，则需要进行修复。

  3. 修复红黑树性质：根据新节点的父节点和叔叔节点的颜色以及它们的位置关系，分为以下几种情况：

    • 情况一：叔叔节点是红色：将父节点和叔叔节点着色为黑色，祖父节点着色为红色，然后将祖父节点作为新的当前节点，继续检查。

    • 情况二：叔叔节点是黑色，且当前节点是父节点的左孩子：此时要进行旋转来解决，单纯的变色已经不能解决问题了，以爷爷结点为基准右旋之后在变色

    • 情况三：叔叔节点是黑色，且当前节点是父节点的右孩子：此时要进行左右双旋转，具体参见代码

注：情况123均需要考虑u  p 还是p  u 的问题！！！ 

 代码显示：

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);//要是插入黑节点会导致性质5不符合，所以插红的cur->_col = RED;//考虑做左孩子还是右孩子if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;      //别忘了把_parent给到parent,否则下文的parent还是空！//由于我插入的结点必须为红，而红黑树又要求不能有两个连着的红结点//所以我们要判断一下父节点的颜色while (parent && parent->_col == RED){//父节点为红色Node* grandfather = parent->_parent;if (parent == grandfather->_left)                    //parent为左孩子   {//   g                      黑// p   u                 红     红Node* uncle = grandfather->_right;// 叔叔存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;   //g和u都为红，那么一起变色就o而k之grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent;}else{// 叔叔不存在或者存在且为黑//      g                  黑//   p     u            红    黑//c                  红if (cur == parent->_left){RotateR(grandfather);          //单纯变色无法解决，旋转一下parent->_col = BLACK;grandfather->_col = RED;}else{//      g//   p     u//      cRotateL(parent);RotateR(grandfather);grandfather->_col = RED;cur->_col = BLACK;}break;              //处理的是一个子树，这个符合了上面的也就Ok了}}     else                    //parent为右孩子{//   g                   黑// u   p             红      红Node* 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            黑     红//             c       红if (cur == parent->_right){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;
}

3.3 遍历红黑树

 我们还是使用中序遍历遍历红黑树，代码如下：

	void InOrder(){_InOrder(_root);cout << endl;}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << " ";_InOrder(root->_right);}

3.4 检查红黑树

 检查的方法很简单，就是通过随便跑一条路，数一下黑色节点，并将其作为参考值，之后在遍历整棵树，看看是不是每条路上的黑色节点数都是等于参考值的，换句话说，如果我们的树满足红黑树的性质，那么就o而k之,否则就不o而k之~

	// 前序递归遍历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);}bool IsBalanceTree(){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);}

3.5 代码测试

#include<iostream>
#include<vector>
using namespace std;#include"RBTree.h"// 测试代码
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.IsBalanceTree() << endl;
}void TestRBTree2()
{const int N = 10000000;vector<int> v;v.reserve(N);srand(time(0));for (size_t i = 0; i < N; i++){v.push_back(rand() + i);}RBTree<int, int> t;for (size_t i = 0; i < v.size(); ++i){t.Insert(make_pair(v[i], v[i]));}cout << t.IsBalanceTree() << endl;
}int main()
{TestRBTree1();TestRBTree2();return 0;
}

3.6 代码汇总

这里只放.h文件的！

#pragma once
#include<iostream>
#include<utility>
using namespace std;
// 枚举值表示颜色
enum color
{RED,BLACK
};
// 这里我们默认按key/value结构实现
template<class K,class V>
struct RBTreeNode
{// 这里更新控制平衡也要加入parent指针pair<K, V> _kv;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;color _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: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);//要是插入黑节点会导致性质5不符合，所以插红的cur->_col = RED;//考虑做左孩子还是右孩子if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;      //别忘了把_parent给到parent,否则下文的parent还是空！//由于我插入的结点必须为红，而红黑树又要求不能有两个连着的红结点//所以我们要判断一下父节点的颜色while (parent && parent->_col == RED){//父节点为红色Node* grandfather = parent->_parent;if (parent == grandfather->_left)                    //parent为左孩子   {//   g                      黑// p   u                 红     红Node* uncle = grandfather->_right;// 叔叔存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;   //g和u都为红，那么一起变色就o而k之grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent;}else{// 叔叔不存在或者存在且为黑//      g                  黑//   p     u            红    黑//c                  红if (cur == parent->_left){RotateR(grandfather);          //单纯变色无法解决，旋转一下parent->_col = BLACK;grandfather->_col = RED;}else{//      g//   p     u//      cRotateL(parent);RotateR(grandfather);grandfather->_col = RED;cur->_col = BLACK;}break;              //处理的是一个子树，这个符合了上面的也就Ok了}}     else                    //parent为右孩子{//   g                   黑// u   p             红      红Node* 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            黑     红//             c       红if (cur == parent->_right){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;}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;subL->_right = parent;if (subLR)subLR->_parent = parent;Node* parentParent = parent->_parent;parent->_parent = subL;//if (parentParent == nullptr)if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (parentParent->_left == parent){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}}void RotateL(Node* parent){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 InOrder(){_InOrder(_root);cout << endl;}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << " ";_InOrder(root->_right);}// 前序递归遍历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);}bool IsBalanceTree(){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;
};

四、总结及应用

在红黑树中，我们省去了ALV树的平衡因子，而换用颜色来判断树的平衡，这样使得代码的逻辑变得简单明了 ，后续我们对map和set的封装（实现mymap和myset)便会用到红黑树的思想与结构！

红黑树通过其自平衡的特性，确保了在插入、删除和查找操作中的高效性，使其成为许多实际应用中不可或缺的数据结构。

 


http://www.ppmy.cn/embedded/176012.html

相关文章

数据库三级选择题（1）

数据库三级选择题（1）

7D人机界面的设计可采用原型迭代法&#xff0c;首先进行初步设计&#xff0c;再进行用户界面细节设计&#xff0c;最后是原型设计与改进。 11&#xff1f;在一台正在运行的SQL Server 2008中&#xff0c;现需使用复制数据库文件的方法将某数据库从一台服务器移动到另一台服务器…
阅读更多...
基于python+django的酒店预定网站-酒店管理系统源码+运行步骤+课程学习

基于python+django的酒店预定网站-酒店管理系统源码+运行步骤+课程学习

该系统是基于pythondjango开发的酒店预定管理系统。适用场景&#xff1a;大学生、课程作业、毕业设计。学习过程中&#xff0c;如遇问题可在github给作者留言。共同学习技术 演示地址 前台地址&#xff1a; http://hotel.gitapp.cn 后台地址&#xff1a; http://hotel.gitapp…
阅读更多...
能源监控软件UI界面设计：平衡功能性与审美性的艺术

能源监控软件UI界面设计：平衡功能性与审美性的艺术

在当今社会&#xff0c;能源作为推动经济发展的重要基石&#xff0c;其高效管理和合理利用显得尤为重要。随着科技的进步&#xff0c;能源监控软件应运而生&#xff0c;成为连接能源使用者与管理者之间的桥梁。而软件的UI&#xff08;用户界面&#xff09;设计&#xff0c;作为…
阅读更多...
《基于Spring Boot+Vue的智慧养老系统的设计与实现》开题报告

《基于Spring Boot+Vue的智慧养老系统的设计与实现》开题报告

个人主页：@大数据蟒行探索者 一、研究背景及国内外研究现状 1.研究背景 根据1982年老龄问题世界大会联合国制定的标准，如果一个国家中超过65岁的老人占全国总人口的7%以上，或者超过60岁的老人占全国总人口的10%以上，那么这个国家将被定义为“老龄化社会”[1]。 随着国…
阅读更多...
学习记录-Ajax-图书列表渲染

学习记录-Ajax-图书列表渲染

目录 图书列表渲染功能描述图书列表渲染实现步骤1.准备工作2.数据渲染3.数据添加4.数据删除5.数据编辑 完整实例代码 图书列表渲染功能描述 页面刷新时&#xff0c;列表自动渲染图书列表数据已渲染的图书列表数据可以进行编辑和删除功能点击添加按钮&#xff0c;可以添加图书信…
阅读更多...
Rust语言学习

Rust语言学习

Rust语言学习 通用编程概念所有权所有权引用和借用slice struct(结构体)定义并实例化一个结构体使用结构体方法语法 枚举 enums定义枚举match控制流运算符if let 简单控制流 使用包、Crate和模块管理不断增长的项目&#xff08;模块系统&#xff09;包和crate定义模块来控制作用…
阅读更多...
纯血鸿蒙：中国操作系统自主创新的里程碑

纯血鸿蒙：中国操作系统自主创新的里程碑

引言&#xff1a;破局者登场 2024 年 10 月&#xff0c;搭载纯血鸿蒙操作系统&#xff08;HarmonyOS NEXT&#xff09;的华为 Mate 70 系列正式发布&#xff0c;首日预约量突破 330 万。这场现象级热度的背后&#xff0c;不仅是消费者对硬件创新的期待&#xff0c;更是中国科技…
阅读更多...
在大数据开发中hive是指什么？

在大数据开发中hive是指什么？

hello宝子们...我们是艾斯视觉擅长ui设计和前端数字孪生、大数据、三维建模、三维动画10年经验!希望我的分享能帮助到您!如需帮助可以评论关注私信我们一起探讨!致敬感谢感恩! 在大数据技术的浩瀚星空中&#xff0c;Apache Hive犹如一座桥梁&#xff0c;连接着传统数据仓库理念…
阅读更多...
最新文章

Copyright @ 2022~2023