移情别恋c++ ദ്ദി˶ｰ̀֊ｰ́ ) ——15.红黑树

1.红黑树的概念

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

 

 2.红黑树的性质！！！！！

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

2. 根节点是黑色的 

3. 如果一个节点是红色的，则它的两个孩子结点是黑色的 

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

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

3.红黑树节点的定义 

enum color
{RED,BLACK
};  //列举color的各种可能情况template<class K, class V>
struct RBTtreenode
{RBTtreenode<K, V>* _left;RBTtreenode<K, V>* _right;RBTtreenode<K, V>* _parent;pair<K, V> kv;color col;RBTtreenode(const pair<K, V>& _kv):_left(nullptr)     //左孩子, _right(nullptr)   //右孩子, _parent(nullptr)  //父亲, kv(_kv), col(RED){}
};

 4.红黑树结构

 为了后续实现关联式容器简单，红黑树的实现中增加一个头结点，因为跟节点必须为黑色，为了 与根节点进行区分，将头结点给成黑色，并且让头结点的 pParent 域指向红黑树的根节点，pLeft 域指向红黑树中最小的节点，_pRight域指向红黑树中最大的节点，如下：

5.红黑树的插入！！！！

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

5.1按照二叉搜索的树规则插入新节点

 

if (root == nullptr)
{root = new node(_kv);root->col = BLACK;//规定根必须是黑的return true;
}
node* parent = nullptr; //比bst多了一个parent
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;

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

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

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

 

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

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

2.情况二（单旋+变色）: cur为红，p为红，g为黑，u不存在/u存在且为黑  （左左和右右）

细分就是：(1)g->left==p,p->left==cur;左左

(2)g->right==p,p->right==cur；右右

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

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

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

3.情况三（双旋+变色）: cur为红，p为红，g为黑，u不存在/u存在且为黑  （左右和右左）

 

 

细分就是：(1)g->left==p,p->right==cur;左右

(2)g->right==p,p->left==cur；右左

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

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

则转换成了情况2！！！！！，然后再用情况2的旋转处理一下就行了

 针对每种情况进行相应的处理即可。

while (parent&&parent->col == RED)//parent为黑不需要调整,如果cur变成root，parent就不存在退出循环
{node* grandparent = parent->_parent;//祖父一定存在，因为只有根节点是没有祖父的，而根节点一定是黑色的if (parent==grandparent->_left){//      g//    p   unode* uncle = grandparent->_right;  //父亲在左则叔叔在右if (uncle && uncle->col == RED)     //情况一.如果叔叔存在且为红色{//变色parent->col = uncle->col = BLACK;grandparent->col = RED;//重置cur，parent，继续向上处理cur = grandparent;//变为祖父parent = cur->_parent;}else //叔叔不存在或为黑色，旋转加变色{//   g//  p// cif (cur == parent->_left)  //情况二.单旋{rotateR(grandparent);parent->col = BLACK;grandparent->col = RED;}//   g//  p//   celse      //情况三.cur==parent->_right,双旋{rotateL(parent);//经历一次左旋后变成情况二!!!!!!!!!!!(cur和parent换位置）rotateR(grandparent);cur->col = BLACK;grandparent->col = RED;}break;//调整一次就结束了，所以经历过旋转后不需要重置cur，parent，grandparent}}else{//      g//    u   p//node* uncle = grandparent->_left;  //父亲在右则叔叔在左if (uncle && uncle->col == RED){parent->col = uncle->col = BLACK;grandparent->col = RED;//cur = grandparent;parent = cur->_parent;}else{//    g//  u   p//        cif (cur == parent->_right){rotateL(grandparent);parent->col = BLACK;grandparent->col = RED;}else{//   g// u   p//    crotateR(parent);rotateL(grandparent);cur->col = BLACK;grandparent->col = RED;}break;//调整一次就结束了，所以经历过旋转后不需要重置cur，parent，grandparent}}

6.红黑树的验证 

红黑树的检测分为两步：

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

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

 1.中序输出

void inorder()
{_inorder(root);
}void _inorder(node* root)
{if (root == nullptr)return;_inorder(root->_left);cout << root->kv.first << " ";_inorder(root->_right);
}

2.判断性质 （性质3和性质4）

bool check(node* it,int blacknum,int flag)
{if (it == nullptr){if (blacknum == flag)return true;elsereturn false;}else if (it->col == RED && it->_parent->col == RED)//十分巧妙，因为孩子的情况有很多，但父亲不是红就是黑，所以判断父亲更合适return false;else if (it->col == BLACK)blacknum++;return check(it->_left,blacknum,flag) && check(it->_right,blacknum,flag);
}bool isbalance()
{return _isbalance(root);
}bool _isbalance(node* root)
{if (root == nullptr)return true;else if (root->col == RED)return false;int blacknum = 0;int flag = 0;node* k = root;while (k){if (k->col == BLACK)flag++;k = k->_left;//这里十分巧妙，因为如果为红黑树，从某一节点到空的所有路径上的黑节点数量是一致的，所以可以先随便选一条路径，算出这一条路径上的黑节点数作为基准值，在由递归去和其他路径比较}return check(root,blacknum,flag);
}

7.红黑树的删除

 可参考：《算法导论》或者《STL源码剖析》

红黑树 - _Never_ - 博客园

8 红黑树与AVL树的比较

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

 9 红黑树的应用

1. C++ STL库 -- map/set

2. Java 库

3. linux内核

4. 其他一些库

10.代码全览

rbt.h:

enum color
{RED,BLACK
};  //列举color的各种可能情况template<class K, class V>
struct RBTtreenode
{RBTtreenode<K, V>* _left;RBTtreenode<K, V>* _right;RBTtreenode<K, V>* _parent;pair<K, V> kv;color col;RBTtreenode(const pair<K, V>& _kv):_left(nullptr), _right(nullptr), _parent(nullptr), kv(_kv), col(RED){}
};template<class K, class V>
class RBTtree
{
public:typedef RBTtreenode<K, V> node;bool insert(const pair<K, V>& _kv){if (root == nullptr){root = new node(_kv);root->col = BLACK;//规定根必须是黑的return true;}node* parent = nullptr; //比bst多了一个parentnode* 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)//parent为黑不需要调整,如果cur变成root，parent就不存在退出循环{node* grandparent = parent->_parent;//祖父一定存在，因为只有根节点是没有祖父的，而根节点一定是黑色的if (parent==grandparent->_left){//      g//    p   unode* uncle = grandparent->_right;  //父亲在左则叔叔在右if (uncle && uncle->col == RED)     //情况一.如果叔叔存在且为红色{//变色parent->col = uncle->col = BLACK;grandparent->col = RED;//重置cur，parent，继续向上处理cur = grandparent;//变为祖父parent = cur->_parent;}else //叔叔不存在或为黑色，旋转加变色{//   g//  p// cif (cur == parent->_left)  //情况二.单旋{rotateR(grandparent);parent->col = BLACK;grandparent->col = RED;}//   g//  p//   celse      //情况三.cur==parent->_right,双旋{rotateL(parent);//经历一次左旋后变成情况二!!!!!!!!!!!(cur和parent换位置）rotateR(grandparent);cur->col = BLACK;grandparent->col = RED;}break;//调整一次就结束了，所以经历过旋转后不需要重置cur，parent，grandparent}}else{//      g//    u   p//node* uncle = grandparent->_left;  //父亲在右则叔叔在左if (uncle && uncle->col == RED){parent->col = uncle->col = BLACK;grandparent->col = RED;//cur = grandparent;parent = cur->_parent;}else{//    g//  u   p//        cif (cur == parent->_right){rotateL(grandparent);parent->col = BLACK;grandparent->col = RED;}else{//   g// u   p//    crotateR(parent);rotateL(grandparent);cur->col = BLACK;grandparent->col = RED;}break;//调整一次就结束了，所以经历过旋转后不需要重置cur，parent，grandparent}}}//1.如果parent和uncle都为RED，则可以一起变黑// 2.parent为黑不处理// 3.uncle为黑或不存在，parent为红，旋转+变色root->col = BLACK;//最后以防万一让根变为黑return true;}void rotateL(node* parent)//左旋，（新节点插入到较高右子树的右侧）//   1.右右{node* subr = parent->_right;node* subrl = subr->_left;parent->_right = subrl;subr->_left = parent;node* ppnode = parent->_parent;parent->_parent = subr;if (subrl) //subrl可能为空！！！！！！！{subrl->_parent = parent;}if (parent == root) //即如果parent->_parent==nullptr{root = subr;subr->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subr;}else if (ppnode->_right == parent){ppnode->_right = subr;}subr->_parent = ppnode;}}void rotateR(node* parent)//右旋，（新节点插入到较高左子树的左侧）//   2.左左{node* subl = parent->_left;node* sublr = subl->_right;parent->_left = sublr;if (sublr)               //sublr可能为空！！！！！！！sublr->_parent = parent;node* ppnode = parent->_parent;subl->_right = parent;parent->_parent = subl;if (root == parent){root = subl;subl->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subl;}else if (ppnode->_right == parent){ppnode->_right = subl;}subl->_parent = ppnode;}}void inorder(){_inorder(root);}void _inorder(node* root){if (root == nullptr)return;_inorder(root->_left);cout << root->kv.first << " ";_inorder(root->_right);}bool check(node* it,int blacknum,int flag){if (it == nullptr){if (blacknum == flag)return true;elsereturn false;}else if (it->col == RED && it->_parent->col == RED)//十分巧妙，因为孩子的情况有很多，但父亲不是红就是黑，所以判断父亲更合适return false;else if (it->col == BLACK)blacknum++;return check(it->_left,blacknum,flag) && check(it->_right,blacknum,flag);}bool isbalance(){return _isbalance(root);}bool _isbalance(node* root){if (root == nullptr)return true;else if (root->col == RED)return false;int blacknum = 0;int flag = 0;node* k = root;while (k){if (k->col == BLACK)flag++;k = k->_left;//这里十分巧妙，因为如果为红黑树，从某一节点到空的所有路径上的黑节点数量是一致的，所以可以先随便选一条路径，算出这一条路径上的黑节点数作为基准值，在由递归去和其他路径比较}return check(root,blacknum,flag);}private:node* root = nullptr;
};

test.cpp:

#include<iostream>
using namespace std;#include"RBT.h"int main()
{int arr[] = { 790,760,969,270,31,424,377,24,702 };//int arr[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };RBTtree<int, int> it;for (auto i : arr){it.insert(make_pair(i, i));}it.inorder();cout << endl << it.isbalance() << endl;return 0;
}

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

【C++】类与对象（一）

【C++】类与对象（一）

「前言」 &#x1f308;个人主页&#xff1a; 代码探秘者 &#x1f308;C语言专栏&#xff1a;C语言 &#x1f308;C专栏&#xff1a; C &#x1f308;喜欢的诗句:天行健,君子以自强不息. 目录 [一、面向过程和面向对象初步认识][Link 2] 二、类的引入 三、类的定义 四、类…
阅读更多...
李宏毅机器学习2022-HW8-Anomaly Detection

李宏毅机器学习2022-HW8-Anomaly Detection

文章目录 TaskBaselineReportQuestion2 Code Link Task 异常检测Anomaly Detection 将data经过Encoder&#xff0c;在经过Decoder&#xff0c;根据输入和输出的差距来判断异常图像。training data是100000张人脸照片&#xff0c;testing data有大约10000张跟training data相同…
阅读更多...
值传递和引用传递

值传递和引用传递

值传递和引用传递是函数参数传递的两种类型&#xff0c;一般而言&#xff0c;基本数据类型都是值传递&#xff0c;数组和对象采用引用传递减少对象复制开销&#xff0c;但也有特例。 值和引用传递本质一样 值传递是拷贝值到函数参数&#xff0c;引用传递是拷贝引用(或者对象的指…
阅读更多...
第十三届蓝桥杯真题Java c组C.纸张尺寸(持续更新)

第十三届蓝桥杯真题Java c组C.纸张尺寸(持续更新)

博客主页&#xff1a;音符犹如代码系列专栏&#xff1a;蓝桥杯关注博主&#xff0c;后期持续更新系列文章如果有错误感谢请大家批评指出&#xff0c;及时修改感谢大家点赞&#x1f44d;收藏⭐评论✍ 【问题描述】 在 ISO 国际标准中定义了 A0 纸张的大小为 1189mm 841mm&#…
阅读更多...
jenkins项目发布基础

jenkins项目发布基础

随着软件开发需求及复杂度的不断提高,团队开发成员之间如何更好地协同工作以确保软件开发的质量已经慢慢成为开发过程中不可回避的问题。Jenkins 自动化部署可以解决集成、测试、部署等重复性的工作,工具集成的效率明显高于人工操作;并且持续集成可以更早的获取代码变更的信息,…
阅读更多...
博弈论（学习笔记）

博弈论（学习笔记）

定义何为最优&#xff01; 最优解是均衡&#xff01;&#xff08;&#xff09; 一次博弈 --- 一面之缘 复杂动态博弈&#xff1b; 路怒症----陌生人&#xff0c;一次性博弈。 一次性博弈最能暴露人性。 重复博弈太压抑了。 沙普利求解合作博弈的著名理论---如何为参与者制定利益…
阅读更多...
SQL第11课——使用子查询

SQL第11课——使用子查询

11.1 子查询 查询&#xff08;query): 任何SQL语句都是查询&#xff0c;但此术语一般指select语句。 select语句是SQL的查询&#xff0c;迄今为止所有的select语句都是简单查询&#xff0c;即从单个数据库表中检索数据的单条语句。 SQL还允许创建子查询&#xff08;subquer…
阅读更多...
浪 得 虚 名 ？RAG接入知识图谱！全局数据关系表示！指哪打哪！

浪 得 虚 名 ？RAG接入知识图谱！全局数据关系表示！指哪打哪！

在学知识图谱系列的朋友就知道&#xff01; 知识图谱RAG&#xff01;最大优势&#xff1a; 全局数据关系表示&#xff01; 相似文本散落在–>不规则不相邻文本块&#xff01; 传统RAG只能找到top-k个文本块&#xff0c;一旦文本块过多&#xff0c;超出llm上下文限制&…
阅读更多...
uni-app canvas文本自动换行

uni-app canvas文本自动换行

封装 支持单行文本超出换行。多行文本顺位排版 // 填充自动换行的文本function fillFeedText({ctx, text, x, y, maxWidth, lineHeight, color, size}) {// 文本配置ctx.setFontSize(size);ctx.setFillStyle(color);// 计算文本换行宽高&#xff0c;换行逻辑const words text…
阅读更多...
C++里的随机数

C++里的随机数

想用C做最基础的猜数字,肯定少不了随机数; srand(unsigned(time(NULL))); rand() //是生成一个随机数 rand()%1001//就是一个从一到一百的随机数 合体: #include <iostream> #include <cstdlib> #include <time.h> int main() { int g 0; while (g < …
阅读更多...
虚拟机、ubantu不能连接网络，解决办法

虚拟机、ubantu不能连接网络，解决办法

虚拟机、ubantu不能连接网络&#xff0c;解决办法 物理机OS&#xff1a; [Windows10 专业版](https://so.csdn.net/so/search?qWindows10 专业版&spm1001.2101.3001.7020) 虚拟机平台&#xff1a; VMware Workstation 16 Pro 虚拟机OS&#xff1a; Ubuntu 18.04 自动配…
阅读更多...
pip install kaggle-environments ISSUE:Failed to build vec-noise

pip install kaggle-environments ISSUE:Failed to build vec-noise

ISSUE: error: Microsoft Visual C 14.0 or greater is required. Get it with “Microsoft C Build Tools”: https://visualstudio.microsoft.com/visual-cpp-build-tools/ [end of output]Failed to build vec-noiseC:\ProgramData\miniconda3\include\pyconfig.h(59): fat…
阅读更多...
新农人的求索：既要种菜，也要种钱

新农人的求索：既要种菜，也要种钱

澎湃新闻记者 何惠子 灯下立着一个玻璃瓶&#xff0c;内里空无一物&#xff0c;清晰透亮。 一只手握住瓶身。“就像这个瓶子。前途一片光明&#xff0c;但其实都在瓶子里。” 解晓巍说的是音乐——他曾梦想以此维生。事实上&#xff0c;这也适合描述农业。 在没有任何收入的202…
阅读更多...
XFTP-8下载安装教程

XFTP-8下载安装教程

下载地址 https://www.xshell.com/zh/free-for-home-school/ 新建XFTP文件夹 安装过程 选择新建的文件夹 此处默认即可 填写信息提交注册 点击生成的链接 点击后来&#xff0c;完成安装
阅读更多...
防止电脑电池老化，禁止usb或者ac接口调试时充电

防止电脑电池老化，禁止usb或者ac接口调试时充电

控制android系统&#xff0c;开发者模式&#xff0c;开启和禁止充电 连接 Android 手机到电脑的 USB 端口。 下载并安装 Android Debug Bridge (ADB) 工具[1]。 USB&#xff1a; 在命令行中输入 adb shell dumpsys battery set usb 0&#xff0c;以禁止 USB 充电。 在命令…
阅读更多...
2024年健康经济与大数据研讨会（HEBD 2024）2024 Seminar on Health Economics and Big Data

2024年健康经济与大数据研讨会（HEBD 2024）2024 Seminar on Health Economics and Big Data

在线投稿&#xff1a;学术会议-学术交流征稿-学术会议在线-艾思科蓝 2024年经济决策与人工智能国际学术会议 &#xff08;EDAI 2024&#xff09;将在2024年11月08-10日在广东省广州市隆重举行。大会邀请来自国内外高等院校、科学研究所、企事业单位的专家、教授、学者、工程师…
阅读更多...
线程池：线程池的实现 | 日志

线程池：线程池的实现 | 日志

&#x1f308;个人主页&#xff1a; 南桥几晴秋 &#x1f308;C专栏&#xff1a; 南桥谈C &#x1f308;C语言专栏&#xff1a; C语言学习系列 &#x1f308;Linux学习专栏&#xff1a; 南桥谈Linux &#x1f308;数据结构学习专栏&#xff1a; 数据结构杂谈 &#x1f308;数据…
阅读更多...
spark计算引擎-架构和应用

spark计算引擎-架构和应用

一Spark 定义&#xff1a;Spark 是一个开源的分布式计算系统&#xff0c;它提供了一个快速且通用的集群计算平台。Spark 被设计用来处理大规模数据集&#xff0c;并且支持多种数据处理任务&#xff0c;包括批处理、交互式查询、机器学习、图形处理和流处理。 核心架构&#x…
阅读更多...
【Linux】Linux环境基础开发工具使用

【Linux】Linux环境基础开发工具使用

Linux开发工具 Linux编辑器-vim使用 1. vim的基本概念 vim的三种模式&#xff0c;分别是命令模式&#xff08;command mode&#xff09;、插入模式&#xff08;Insert mode&#xff09;和底行模式&#xff08;last line mode&#xff09;。 正常/普通/命令模式&#xff1a; …
阅读更多...
如果您忘记了 Apple ID 和密码，按照指南可重新进入您的设备

如果您忘记了 Apple ID 和密码，按照指南可重新进入您的设备

即使您的 iPhone 或 iPad 由于各种原因被锁定或禁用&#xff0c;也可以使用 iTunes、“查找我的”、Apple 支持和 iCloud 解锁您的设备。但是&#xff0c;此过程需要您的 Apple ID 和密码来验证所有权并移除激活锁。如果您忘记了 Apple ID 和密码&#xff0c;请按照我们的指南重…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023