红黑树

  

目录

  红黑树

红黑树的概念

红黑树的性质

红黑树节点的定义

插入的代码实现

情况一

情况二

uncle不存在

uncle存在且为黑单旋

情况三

uncle存在且为黑的双旋情况

情况二和情况三的总代码 

以上是父亲在爷爷左边的情况,右边的情况也类似

左旋代码

右旋代码

红黑树的验证

总代码

红黑树

红黑树的概念

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

红黑树的性质

(路径是从根到空节点,上图是11个节点)                 不是红黑树

(最长路径：一黑一红相间的路径  最短：全黑路径)

1. 每个结点不是红色就是黑色

2. 根节点是黑色的 

3. 如果一个节点是红色的，则它的两个孩子结点是黑色的(任何路径没有连续的红色节点)

4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点 

5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

红黑树节点的定义

//枚举
//节点颜色
enum Colour
{RED,BLACK
};
//红黑树节点的定义
template<class K,class  V>
struct RBTreeNode
{RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _left;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){}
};

插入的代码实现

检测新节点插入后，红黑树的性质是否造到破坏

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

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

情况一

cur为红，p为红，g为黑，u存在且为红

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

举个例子：

 

//第一种情况父亲在爷爷的左边
if (parent == grandfather->_left)
{//定义叔叔节点，父亲在左，叔叔节点则在右Node* uncle = grandfather->_right;// u存在且为红if (uncle && uncle->_col == RED){// 变色，父亲和叔叔都变黑，爷爷变红parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续向上处理，因为有可能爷爷是子树节点，爷爷的父亲节点可能也是红色cur = grandfather;parent = cur->_parent;}
}

情况二

cur为红，p为红，g为黑，u不存在/u存在且为黑

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

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

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

举个例子

uncle不存在

	//uncle不存在，且插入的在父亲的左边if (cur == parent->_left){//     g//   p// c//右旋RotateR(grandfather);//变色parent->_col = BLACK;grandfather->_col = RED;}//cur在父亲右边时，需要双旋else{//     g//   p//		cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;
}

还有可能父亲在爷爷的右边

uncle存在且为黑单旋

(变色后，parent不能直接变黑，因为变黑后每个路径的黑节点不同了)

图上情况，插入后先变色，uncle为红色，然后再向上处理，发现uncle为黑色就需要旋转了，旋转后就不用调整了

情况三

uncle存在且为黑的双旋情况

cur为红，p为红，g为黑，u不存在/u存在且为黑

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

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

则转换成了情况2

//这种情况也是uncle为黑时，且需要旋转的，上面的是单旋的情况，这个是双旋的情况

情况二和情况三的总代码 

else // u不存在 或 存在且为黑
{//uncle不存在，且插入的在父亲的左边if (cur == parent->_left){//     g//   p// c//右旋RotateR(grandfather);//变色parent->_col = BLACK;grandfather->_col = RED;}//cur在父亲右边时，需要双旋else{//     g//   p//		cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;
}

以上是父亲在爷爷左边的情况,右边的情况也类似

	//父亲在爷爷右边else // parent == grandfather->_right{Node* uncle = grandfather->_left;// u存在且为红if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续向上处理cur = grandfather;parent = cur->_parent;}else{if (cur == parent->_right){// g//	p//       cRotateL(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else{// g//	  p// cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}
}

左旋代码

void RotateL(Node* parent)
{Node* cur = parent->_right;Node* curleft = cur->_left;parent->_right = curleft;if (curleft){curleft->_parent = parent;}cur->_left = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (parent == _root){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}
}

右旋代码

void RotateR(Node* parent)
{Node* cur = parent->_left;Node* curright = cur->_right;parent->_left = curright;if (curright)curright->_parent = parent;Node* ppnode = parent->_parent;cur->_right = parent;parent->_parent = cur;if (ppnode == nullptr){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}
}

红黑树的验证

红黑树的检测分为两步：

1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)

2. 检测其是否满足红黑树的性质

红黑树的删除

红黑树 - _Never_ - 博客园

红黑树与AVL树的比较

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

总代码

RBTree.h
#pragma once
#include<iostream>
#include<assert.h>
#include<vector>
//枚举
//节点颜色
enum Colour
{RED,BLACK
};
//红黑树节点的定义
template<class K,class  V>
struct RBTreeNode
{RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _left;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* 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);cur->_col = RED;if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}//连接上父子关系cur->_parent = parent;//parent存在且为红色时需要进行变色旋转，因为黑色的时候就不用做处理了while (parent && parent->_col == RED){//定义一下爷爷节点Node* grandfather = parent->_parent;//第一种情况父亲在爷爷的左边if (parent == grandfather->_left){//定义叔叔节点，父亲在左，叔叔节点则在右Node* uncle = grandfather->_right;// u存在且为红if (uncle && uncle->_col == RED){// 变色，父亲和叔叔都变黑，爷爷变红parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续向上处理，因为有可能爷爷是子树节点，爷爷的父亲节点可能也是红色cur = grandfather;parent = cur->_parent;}else // u不存在 或 存在且为黑{//uncle不存在，且插入的在父亲的左边if (cur == parent->_left){//     g//   p// c//右旋RotateR(grandfather);//变色parent->_col = BLACK;grandfather->_col = RED;}//cur在父亲右边时，需要双旋else{//     g//   p//		cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}//父亲在爷爷右边else // parent == grandfather->_right{Node* uncle = grandfather->_left;// u存在且为红if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续向上处理cur = grandfather;parent = cur->_parent;}else{if (cur == parent->_right){// g//	p//       cRotateL(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else{// g//	  p// cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}void RotateL(Node* parent){++_rotateCount;Node* cur = parent->_right;Node* curleft = cur->_left;parent->_right = curleft;if (curleft){curleft->_parent = parent;}cur->_left = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (parent == _root){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}void RotateR(Node* parent){++_rotateCount;Node* cur = parent->_left;Node* curright = cur->_right;parent->_left = curright;if (curright)curright->_parent = parent;Node* ppnode = parent->_parent;cur->_right = parent;parent->_parent = cur;if (ppnode == nullptr){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}bool CheckColour(Node* root, int blacknum, int benchmark){if (root == nullptr){if (blacknum != benchmark)return false;return true;}if (root->_col == BLACK){++blacknum;}if (root->_col == RED && root->_parent && root->_parent->_col == RED){cout << root->_kv.first << "出现连续红色节点" << endl;return false;}return CheckColour(root->_left, blacknum, benchmark)&& CheckColour(root->_right, blacknum, benchmark);}bool IsBalance(){return IsBalance(_root);}bool IsBalance(Node* root){if (root == nullptr)return true;if (root->_col != BLACK){return false;}// 基准值int benchmark = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK)++benchmark;cur = cur->_left;}return CheckColour(root, 0, benchmark);}int Height(){return Height(_root);}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;}private:Node* _root = nullptr;public:int _rotateCount = 0;
};

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

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

MySQL进阶-索引的组合索引

MySQL进阶-索引的组合索引

练习题目 题目链接难度SQL进阶-索引的组合索引★★★☆☆ SQL思路 SQL进阶-索引的组合索引 初始化数据 drop table if exists user_profile; CREATE TABLE user_profile ( id int NOT NULL, device_id int NOT NULL, gender varchar(14) NOT NULL, age int , university va…
阅读更多...
适用比亚迪汽车生产线的RFID高频读写器

适用比亚迪汽车生产线的RFID高频读写器

随着人工智能和物联网技术的发展&#xff0c;汽车产线正朝着高度自动化和智能化的方向发展&#xff0c;许多汽车制造商选择将RFID技术应用在其生产线上&#xff0c;以提高生产效率、降低劳动强度。例如比亚迪等汽车生产线上已经广泛应用RFID技术。 健永科技利用自身的研发能力…
阅读更多...
用Python实现中国象棋（详细教程 | 附代码）

用Python实现中国象棋（详细教程 | 附代码）

创建一个完整的中国象棋游戏是一个复杂的项目&#xff0c;涉及到游戏规则、用户界面、AI算法等多个方面。在这里&#xff0c;我将提供一个更完整的Python代码示例&#xff0c;包括基本的棋盘、棋子移动规则和简单的用户交互。但请注意&#xff0c;这仍然是一个简化的版本&#…
阅读更多...
力扣-Mysql-3308- 寻找表现最佳的司机（中等）

力扣-Mysql-3308- 寻找表现最佳的司机（中等）

一、题目来源 3308. 寻找表现最佳的司机 - 力扣&#xff08;LeetCode&#xff09; 二、数据表结构 表&#xff1a;Drivers ----------------------- | Column Name | Type | ----------------------- | driver_id | int | | name | varchar | | age …
阅读更多...
LeetCode 209.长度最小的子数组

LeetCode 209.长度最小的子数组

209.长度最小的子数组 思路&#x1f9d0;&#xff1a; 该题可以用滑动窗口进行解答&#xff0c;滑动窗口的意思是&#xff0c;我们判断一段区间的情况&#xff0c;再根据不同情况进行区间的更新。 这里要求满足总和大于等于target的子数组&#xff0c;那么我们可以用两个指针当…
阅读更多...
国网山东电力生产检修建设基地绿色低碳智慧用能项目获创新创意劳动竞赛一等奖

国网山东电力生产检修建设基地绿色低碳智慧用能项目获创新创意劳动竞赛一等奖

原标题&#xff1a;深化开展“供电能效服务”&#xff0c;全力推动全社会能效提升&#xff0c;国网山东电力生产检修建设基地绿色低碳智慧用能项目获得全省智慧综合能源服务项目创新创意劳动竞赛一等奖 11月14日,由山东省发展和改革委员会、山东省总工会、山东省能源局主办,山…
阅读更多...
AIHub： 模型和数据集的私有云存储库

AIHub： 模型和数据集的私有云存储库

AIStor 的最新功能之一是广受欢迎的开源项目 Hugging Face 的私有云版本。这篇文章详细介绍了 AIStor 的 AIHub 如何有效地创建一个完全由企业控制的 API 兼容的私有云版本的 Hugging Face。在我们开始之前&#xff0c;介绍 Hugging Face 是有意义的。Hugging Face 是面向 AI 工…
阅读更多...
【SAP FICO】财务三大报表_2-进阶（现金流量表-数据表结构、取数逻辑）

【SAP FICO】财务三大报表_2-进阶（现金流量表-数据表结构、取数逻辑）

系列文章目录 文章目录 系列文章目录前言一、现金流量表二、现金流量表的数据表结构1、核心数据表2、内部数据结构 三、现金流量表的取数逻辑1、获取用户输入2、获取数据3、处理数据 总结 前言 承接上篇财务三大报表_2-进阶&#xff08;利润表-数据表结构、取数逻辑&#xff0…
阅读更多...
【人工智能】深入解析！三种实现ChatGPT打字机效果的最佳方案

【人工智能】深入解析！三种实现ChatGPT打字机效果的最佳方案

在当今AI快速发展的时代&#xff0c;ChatGPT 凭借其强大的自然语言处理能力&#xff0c;已经成为众多开发者和企业的首选工具。然而&#xff0c;如何在前端页面中实现类似于ChatGPT的打字机效果&#xff0c;以提升用户交互体验&#xff0c;成为了一个广受关注的话题。今天&…
阅读更多...
C++：继承

C++：继承

一、什么是继承&#xff1f; 概念&#xff1a; 在我们认识模板之后&#xff0c;模板是写与类型无关的代码&#xff0c;是一种复用方法。今天讲解的是继承&#xff0c;继承也是代码复用的方法&#xff0c;是在原有的基础上进行增加新的类。由此继承体现了面向对象的层次结构&a…
阅读更多...
Java版本Spring Cloud+SpringBoot b2b2c：Java商城实现一件代发设置及多商家直播带货商城搭建

Java版本Spring Cloud+SpringBoot b2b2c：Java商城实现一件代发设置及多商家直播带货商城搭建

一、产品简介 我们的JAVA版多商家入驻直播带货商城系统是一款全*面的电子商务平台&#xff0c;它允许商家和消费者在一个集成的环境中进行互动。系统采用先进的JAVA语言开发&#xff0c;提供多商家入驻、直播带货、B2B2C等多种功能&#xff0c;帮助用户实现线上线下的无缝对接…
阅读更多...
【Linux】进程

【Linux】进程

目录 谈谈硬件冯诺依曼体系结构数据流向 谈谈软件(操作系统)什么是操作系统&#xff1f;为什么需要操作系统&#xff1f;操作系统如何管理&#xff1f; 谈谈进程管理进程PCB查看进程ps ajxprockill -9 PID 系统调用getpid()getppid()fork() 进程状态linux下的进程状态RSDT/tXZ …
阅读更多...
【comfyui教程】ComfyUI绘画|ComfyUI 本地部署（Windows系统）

【comfyui教程】ComfyUI绘画|ComfyUI 本地部署（Windows系统）

前言 关于 ComfyUI 的部署&#xff0c;推荐使用 Window系统 英伟达显卡 的搭配组合。 整合包下载⏬ 所有的AI设计工具&#xff0c;安装包、模型和插件&#xff0c;都已经整理好了&#xff0c;&#x1f447;获取~ PS&#xff1a;最好是下载到固态硬盘内&#xff0c;确保存储空…
阅读更多...
飞牛云fnOS本地部署1Panel服务器运维管理面板并搭建Halo个人博客

飞牛云fnOS本地部署1Panel服务器运维管理面板并搭建Halo个人博客

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…
阅读更多...
Python实现贪吃蛇 经典解压小游戏！附源码

Python实现贪吃蛇 经典解压小游戏！附源码

大家应该都玩过诺基亚上面的贪吃蛇吧&#xff0c;那是一段美好的童年回忆&#xff0c;本文将带你一步步用python语言实现一个snake小游戏&#xff01; 基础环境必备 版本&#xff1a;Python3 ●系统&#xff1a;Windows ●相关模块&#xff1a;pygame pip install pygame安…
阅读更多...
史上最强大的 S3 API？介绍 Prompt API。

史上最强大的 S3 API？介绍 Prompt API。

迄今为止&#xff0c;对象存储世界已由 PUT 和 GET 的 S3 API 概念定义。然而&#xff0c;我们现在生活的世界需要更多。鉴于 MinIO 的 S3 部署甚至比 Amazon 还多&#xff0c;因此我们不得不提出下一个出色的 S3 API。 这个新 API 就是 Prompt API&#xff0c;它很可能成为有…
阅读更多...
微信小程序 — 农产品供销系统

微信小程序 — 农产品供销系统

农产品供销系统 一&#xff1a;基本介绍开发环境功能模块图系统功能部分数据库表设计 二&#xff1a;部分系统页面展示小程序登录界面小程序首页水果分类列表 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/415514d6c40c461c91c1739a4f682fea.jpeg#pic_center)小程序…
阅读更多...
为什么说数字化转型需要用到RPA

为什么说数字化转型需要用到RPA

在现代商业环境中&#xff0c;数字化转型已成为企业追求创新、提高竞争力和适应市场变化的重要战略。然而&#xff0c;数字化转型不仅仅是简单地将纸质文档转化为电子文件或引入新的IT系统&#xff0c;而是要全面优化和重塑企业的业务流程、运营模式和客户体验。在这一过程中&a…
阅读更多...
海外媒体发稿：聚焦摩洛哥世界新闻 Morocco World News

海外媒体发稿：聚焦摩洛哥世界新闻 Morocco World News

关于摩洛哥世界新闻简介&#xff1a; 摩洛哥世界新闻&#xff1a;通过卓越的新闻报道倡导言论自由和深思熟虑的辩论 摩洛哥世界新闻致力于向广大受众提供摩洛哥和中东及北非地区的新闻&#xff0c;不带偏见或政治目的。摩洛哥世界新闻的愿景是成为言论自由的捍卫者&#xff0…
阅读更多...
快速建造高品质音乐厅：声学气膜馆打造专业降噪空间—轻空间

快速建造高品质音乐厅：声学气膜馆打造专业降噪空间—轻空间

随着音乐艺术在城市生活中的地位不断提升&#xff0c;各类音乐厅和演出场馆的需求量也逐年增加。然而&#xff0c;传统音乐厅的建设往往周期长、成本高&#xff0c;特别是在城市中心和文化聚集区&#xff0c;土地资源有限&#xff0c;建造优质的音乐厅面临诸多挑战。如何在有限…
阅读更多...
最新文章

Copyright @ 2022~2023