【C++】红黑树

server/2024/9/23 6:30:09/

 🌈个人主页：秦jh_-CSDN博客
🔥 系列专栏：https://blog.csdn.net/qinjh_/category_12575764.html?spm=1001.2014.3001.5482

 9efbcbc3d25747719da38c01b3fa9b4f.gif​ 

目录

前言

红黑树的概念

红黑树的性质

节点的定义

红黑树的插入操作 

 检测操作：

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

情况二: cur为红，p为红，g为黑，u不存在/u存在且为黑 

Insert 代码

 红黑树的验证

红黑树与AVL树的比较

 完整代码

前言

    💬 hello! 各位铁子们大家好哇。

             今日更新了红黑树的相关内容
    🎉 欢迎大家关注🔍点赞👍收藏⭐️留言📝

红黑树的概念

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

红黑树的性质

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

注意：这里的叶子节点指的是空节点，也就是上图中的NIL节点。NIL节点也方便我们数路径，有几个NIL节点，就有几条路径。 

最长路径<=最短路径*2  （最长路径就是一红一黑间隔，最短路径就是全黑）

节点的定义

 

红黑树的插入操作 

红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：

  1. 按照二叉搜索的树规则插入新节点
  2. 检测新节点插入后，红黑树的性质是否造到破坏 

新节点的默认颜色是红色，因此：如果其父亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的父亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论。

 检测操作：

约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

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

 

上图是抽象图，a/b/c/d/e代表每条路径有x个黑色节点的红黑子树，且x>=0。 

注意：这里所看到的树，可能是一棵完整的树，也可能是一棵子树。

假设此时x==0，cur就是新增节点。

解决方式：将p,u改为黑，g改为红，然后把g当成cur，继续向上调整。

如果g是根节点，调整完成后，将g改成黑色。

如果g是子树，g一定有父亲，如果父亲是红色，就继续往上调整，如果父亲是黑，就结束。

 

如果x==1，c/d/e就是m/n/p/q四种组合之一。此时新增节点的位置就是a和b的孩子之一。 

方法跟上面x==0的情况一样。

情况二: cur为红，p为红，g为黑，u不存在/u存在且为黑 

说明：u的情况有两种：

  1. 若u不存在，则cur就是新插入节点。因为如果cur不是新插入节点，cur和p一定有一个节点是黑色的，就不满足性质4：每条路径的黑色节点个数相同。
  2. 若u存在且为黑，则 cur原来的颜色一定是黑的，现在看到是红色是因为cur子树在调整过程中将cur的颜色由黑色改成红色，如下图：

解决方式：

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

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

p、g变色--p变黑，g变红

情况二的双旋情况：

解决方法：

p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；

相反， p为g的右孩子，cur为p的左孩子，则针对p做右单旋转。则转换成了情况2的单旋情况 ，再按照情况2单旋的方法解决。

Insert 代码

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->_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);cur->_col = RED;  //新增节点给红色if (parent->_kv.first > kv.first){parent->_left = cur;}else{parent->_right = 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){//      g//   p     u// c//单旋RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//     g//  p     u//    c//双旋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  //叔叔不存在，或者存在且为黑{//    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;
}

 红黑树的验证

 红黑树的检测分为两步：

  1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列）
  2. 检测其是否满足红黑树的性质

	bool IsBalance(){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);}

红黑树与AVL树的比较

红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O(logN)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数， 所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红 黑树更多。 

 完整代码

#pragma once enum Colour
{RED,BLACK
};template<class K,class V>
struct RBTreeNode
{RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;pair<K, V> _kv; Colour _col;RBTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}
};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->_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);cur->_col = RED;  //新增节点给红色if (parent->_kv.first > kv.first){parent->_left = cur;}else{parent->_right = 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){//      g//   p     u// c//单旋RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//     g//  p     u//    c//双旋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  //叔叔不存在，或者存在且为黑{//    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 RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR) //节点可能为空subLR->_parent = parent;subL->_right = parent; //旧父节点变成subL的右节点Node* ppNode = parent->_parent;  //该不平衡节点可能不是根节点，所以要找到它的父节点parent->_parent = subL;if (parent == _root)   //如果该节点是根节点{_root = subL;_root->_parent = nullptr;}else  //不平衡节点只是一棵子树{if (ppNode->_left == parent)  //如果旧父节点等于爷爷节点的左节点，新父节点为爷爷节点的左节点{ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;	//新父节点指向爷爷节点。}}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;Node* ppNode = parent->_parent;parent->_parent = subR;if (parent == _root){_root = subR;_root->_parent = nullptr;}else{if (ppNode->_right == parent){ppNode->_right = subR;}else{ppNode->_left = subR;}subR->_parent = ppNode;}}void InOrder(){_InOrder(_root);cout << endl;}bool IsBalance(){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);}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}private:Node* _root = nullptr;size_t _size = 0;
};void RBTreeTest1()
{//int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14,8, 3, 1, 10, 6, 4, 7, 14, 13 };RBTree<int, int> t1;for (auto e : a){t1.Insert({ e,e });//cout << "Insert:" << e << "->" << t1.IsBalance() << endl;}t1.InOrder();cout << t1.IsBalance() << endl; 
}


http://www.ppmy.cn/server/93679.html

相关文章

WinScp自动执行脚本

WinScp自动执行脚本

我们经常使用WinSCP工具通过sftp协议上传获取文件&#xff0c;本文描述通过bat批量处理文件。 首先&#xff0c;我们打开dos命令窗口使用 cd \d :D\WinSCP 打开WinSCP安装目录 上传文件&#xff1a; winscp.exe /console /command "option batch continue" "…
阅读更多...
探索机器学习之美：使用Scikit-learn进行模型可视化

探索机器学习之美：使用Scikit-learn进行模型可视化

探索机器学习之美&#xff1a;使用Scikit-learn进行模型可视化 在机器学习的世界里&#xff0c;模型的可视化是一个强大的工具&#xff0c;它可以帮助我们更好地理解模型的行为和决策过程。Scikit-learn&#xff0c;作为Python中最受欢迎的机器学习库之一&#xff0c;提供了多…
阅读更多...
在Python中创建和操作字典的全面指南

在Python中创建和操作字典的全面指南

在Python中创建和操作字典的全面指南 字典是Python中一种非常重要的数据结构，它以键值对的形式存储数据。字典的灵活性和高效性使其在数据处理和存储中非常受欢迎。在本文中，我们将详细介绍如何在Python中创建字典，并探讨字典的常用操作，包括添加、删除、查找和更新元素。…
阅读更多...
《Transformer Scale Gate for Semantic Segmentation》CVPR2023

《Transformer Scale Gate for Semantic Segmentation》CVPR2023

摘要 论文提出了一种名为Transformer Scale Gate&#xff08;TSG&#xff09;的模块&#xff0c;用于优化在语义分割任务中多尺度上下文信息的编码。现有的基于Transformer的分割模型在组合不同尺度的特征时没有进行选择&#xff0c;这可能导致次优尺度的特征降低分割的准确性…
阅读更多...
【React】实现消息列表的删除

【React】实现消息列表的删除

工作小记&#xff0c;第一次接触react项目 1.增加删除对话项的函数 hooks\use-conversation.ts // 删除对话项的函数const deleteConversation (id: string) > {setConversationList(prevList > prevList.filter(item > item.id ! id))}return {deleteConversation,.…
阅读更多...
AI学习指南机器学习篇-Q学习的优缺点

AI学习指南机器学习篇-Q学习的优缺点

AI学习指南机器学习篇-Q学习的优缺点 在强化学习领域&#xff0c;Q学习是一种经典的算法&#xff0c;被广泛应用于各种任务中。它通过不断更新一个状态动作值函数Q来选择最优的动作&#xff0c;从而实现对环境的学习和决策。虽然Q学习算法在很多问题上表现出色&#xff0c;但也…
阅读更多...
[ZJCTF 2019]NiZhuanSiWei1

[ZJCTF 2019]NiZhuanSiWei1

打开题目 php代码审计 .从代码中可以看出要求&#xff0c;以get方式传递text,file,password三个参数。 3.第一层验证if(isset($text)&&(file_get_contents($text,r)"welcome to the zjctf")) 传入text&#xff0c;而且file_get_contents($text,r)之后内容…
阅读更多...
前端：Vue学习 - 智慧商城项目

前端：Vue学习 - 智慧商城项目

前端&#xff1a;Vue学习 - 智慧商城项目 1. vue组件库 > vant-ui2. postcss插件 > vw 适配3. 路由配置4. 登录页面静态布局4.1 封装axios实例访问验证码接口4.2 vant 组件 > 轻提示4.3 短信验证倒计时4.4 登录功能4.5 响应拦截器 > 统一处理错误4.6 登录权证信息存…
阅读更多...
最新文章

Copyright @ 2022~2023