数据结构：红黑树的原理和实现

文章目录

  • 红黑树的概念
  • 红黑树的性质
  • 红黑树的模拟实现
    • 红黑树的平衡问题
  • 整体实现和测试

本篇用于进行红黑树的拆解和模拟实现，为之后的map和set的封装奠定基础

红黑树的概念

红黑树也是一种二叉搜索树，但是在每一个节点的内部新增了一个用以表示该节点颜色的值，有黑色和红色两种，通过对任何一条从根到叶子的路径上的各个节点着色方式的限制，红黑树可以保证没有一条路径可以比其他路径长出两倍，因此是平衡的

红黑树的基本模式如下图所示
在这里插入图片描述

红黑树的性质

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

为什么红黑树具有最长路径中节点的个数不超过最短路径个数的2倍？

其实原因在于红黑树的性质，在红黑树中可以存在两个相同黑色节点连在一起，但是绝对不会存在两个连在一起的红色节点，并且每个路径上的黑色节点数量是相同的，基于这两点原因，在红黑树中最长的路径不过是一个红节点穿插一个黑节点…而最短的路径就是所有黑节点是一个接着一个，基于这样的原因就可以保证上面的性质了

红黑树的模拟实现

基本的定义

enum Color
{RED,BLEAK
};template<class K, class V>
struct BSTreeNode
{BSTreeNode<K, V>* _left;BSTreeNode<K, V>* _right;BSTreeNode<K, V>* _parent;pair<K, V> _kv;Color _col;BSTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}
};

为什么这里在定义信息的时候，默认值使用的是RED？

由于红黑树的性质可以知道，一条路径中的黑节点的数量是确定的，当插入的是一个红色节点时，最多会影响的是当前路径的信息，但是如果插入的是一个黑色节点，那么势必会引起整个树中所有完整的路径中的异常，会破坏红黑树中的平衡

红黑树的平衡问题

在插入新节点后，红黑树的平衡可能会受到破坏，下面分情况来进行讨论

定义：当前节点为cur，父亲节点为parent，祖父节点为grandparent，叔叔节点为uncle，而红黑树的插入问题重点看叔叔

1. 如果双亲节点是黑色

在这里插入图片描述
最简单的一种情况，不需要做任何处理，只需要插入即可

2. cur为红色，parent为红色，grandfather为黑色，uncle存在并且是红色

在这里插入图片描述
此时，出现了两个红色节点相继出现的情况，这种情况是不被允许的，因此要做出调整：把parent和uncle都改成黑色，同时将grandfather改成红色

此时需要继续进行情况讨论，如果grandfather是根节点，那么就意味着此时调整已经完毕了，不需要再进行调整，因此把根节点置为黑色，而如果grandfather不为根节点，并且上面一个节点还是红色，那么此时又有两个红色节点相继出现了，此时就需要继续进行调整，把grandfather当成cur，然后进行调整即可

在这里插入图片描述
3. cur为红色，parent为红色，grandfather为黑色，uncle不存在或者是黑色

根据uncle的情况来进行分析：

  1. 如果uncle节点不存在，那么就说明cur一定是新插入的节点，这是因为路径下的黑色节点必定要相同，此时又有两种情况，可能插入在parent的左右两边

在这里插入图片描述

  1. 如果uncle节点存在，并且是黑色，那么就意味着cur节点一定是黑的，现在体现为红色是因为cur子树在调整的过程中把cur的节点变成红色了，如果cur是新插入节点，那么红黑树原来就是错的，因为下面的场景不存在
    在这里插入图片描述
    所以一定是这样的情景：

在这里插入图片描述

而此时cur并不是新插入的节点，新插入节点是cur的左右子树中的一个，现在体现为红色是因为下面子树的调整把cur变成红色了，它原来是黑色的

那么此时就要进行旋转了：令grandparent右旋即可完成降高度的效果，再进行变色即可

在这里插入图片描述
因此将上述的过程都综合起来，就可以完成代码的实现了

	bool insert(const pair<K, V>& kv){Node* cur = _root;Node* parent = nullptr;// 根据搜索二叉树的基本逻辑完成if (_root == nullptr){_root = new Node(kv);}else{// 插入数据while (cur){if (cur->_kv.second > kv.second){// 插入元素小于当前节点元素，插入到左边parent = cur;cur = cur->_left;}else if (cur->_kv.second < kv.second){// 插入元素大于当前节点元素，插入到右边parent = cur;cur = cur->_right;}else{return false;}}// 此时parent指向最后一个节点，cur为空cur = new Node(kv);if (parent->_kv.second > cur->_kv.second){// 如果插入节点小于它的父亲，就插入到左边parent->_left = cur;cur->_parent = parent;}else if (parent->_kv.second < cur->_kv.second){// 如果插入节点大于它的父亲，就插入到右边parent->_right = cur;cur->_parent = parent;}else{return false;}}// 至此，普通二叉搜索树的插入已经完成，该进行红黑树的高度调整了// 终止条件是parent为空，或者parent已经是黑色了，就意味着不需要调整了// parent是红色，意味着grandparent一定存在while (parent && parent->_col == RED){// 更变的核心是舅舅，因此要先找到舅舅// 整体来说还有两种情况，parent可能是grandparent的左或者右，舅舅就是另外一边Node* grandparent = parent->_parent;if (parent == grandparent->_left){Node* uncle = grandparent->_right;// 1. 舅舅存在，并且是红色if (uncle && uncle->_col == RED){//     g//   p   u// c// 变色parent->_col = uncle->_col = BLACK;grandparent->_col = RED;// 向上处理cur = grandparent;parent = cur->_parent;}// 2. 舅舅不存在else{// 如果cur是左孩子if (cur == parent->_left){//     g//   p// c// 对grandparent进行右旋RotateR(grandparent);// 变色cur->_col = grandparent->_col = RED;parent->_col = BLACK;}// 如果cur是右孩子else{//     g               g//  p       -->     c         -->    c//    c           p                p   g// 对parent左旋，对grandparent右旋RotateL(parent);RotateR(grandparent);// 变色cur->_col = BLACK;parent->_col = grandparent->_col = RED;}// 更新之后parent和grandparent顺序乱了，而且也不需要继续调整了，直接breakbreak;}}// parent是grandparent的右孩子，相同的逻辑再进行一次else{Node* uncle = grandparent->_left;if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandparent->_col = RED;// 继续往上处理cur = grandparent;parent = cur->_parent;}else{if (cur == parent->_right){//   g//      p//         cRotateL(grandparent);parent->_col = BLACK;grandparent->_col = RED;}else{//     g//       p //     cRotateR(parent);RotateL(grandparent);cur->_col = BLACK;grandparent->_col = RED;}break;}}}// 不管上面怎么变都无所谓，只需要保证根节点是黑的就可以了_root->_col = BLACK;return true;}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;subR->_left = parent;Node* parentParent = parent->_parent;parent->_parent = subR;if (subRL)subRL->_parent = parent;if (_root == parent){_root = subR;subR->_parent = nullptr;}else{if (parentParent->_left == parent){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* parentParent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (_root == parent){_root = subL;subL->_parent = nullptr;}else{if (parentParent->_left == parent){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}}

整体实现和测试

enum Color
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{RBTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;pair<K, V> _kv;Color _col;
};template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:RBTree():_root(nullptr){}bool insert(const pair<K, V>& kv){Node* cur = _root;Node* parent = nullptr;// 根据搜索二叉树的基本逻辑完成if (_root == nullptr){_root = new Node(kv);}else{// 插入数据while (cur){if (cur->_kv.second > kv.second){// 插入元素小于当前节点元素，插入到左边parent = cur;cur = cur->_left;}else if (cur->_kv.second < kv.second){// 插入元素大于当前节点元素，插入到右边parent = cur;cur = cur->_right;}else{return false;}}// 此时parent指向最后一个节点，cur为空cur = new Node(kv);if (parent->_kv.second > cur->_kv.second){// 如果插入节点小于它的父亲，就插入到左边parent->_left = cur;cur->_parent = parent;}else if (parent->_kv.second < cur->_kv.second){// 如果插入节点大于它的父亲，就插入到右边parent->_right = cur;cur->_parent = parent;}else{return false;}}// 至此，普通二叉搜索树的插入已经完成，该进行红黑树的高度调整了// 终止条件是parent为空，或者parent已经是黑色了，就意味着不需要调整了// parent是红色，意味着grandparent一定存在while (parent && parent->_col == RED){// 更变的核心是舅舅，因此要先找到舅舅// 整体来说还有两种情况，parent可能是grandparent的左或者右，舅舅就是另外一边Node* grandparent = parent->_parent;if (parent == grandparent->_left){Node* uncle = grandparent->_right;// 1. 舅舅存在，并且是红色if (uncle && uncle->_col == RED){//     g//   p   u// c// 变色parent->_col = uncle->_col = BLACK;grandparent->_col = RED;// 向上处理cur = grandparent;parent = cur->_parent;}// 2. 舅舅不存在else{// 如果cur是左孩子if (cur == parent->_left){//     g//   p// c// 对grandparent进行右旋RotateR(grandparent);// 变色cur->_col = grandparent->_col = RED;parent->_col = BLACK;}// 如果cur是右孩子else{//     g               g//  p       -->     c         -->    c//    c           p                p   g// 对parent左旋，对grandparent右旋RotateL(parent);RotateR(grandparent);// 变色cur->_col = BLACK;parent->_col = grandparent->_col = RED;}// 更新之后parent和grandparent顺序乱了，而且也不需要继续调整了，直接breakbreak;}}// parent是grandparent的右孩子，相同的逻辑再进行一次else{Node* uncle = grandparent->_left;if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandparent->_col = RED;// 继续往上处理cur = grandparent;parent = cur->_parent;}else{if (cur == parent->_right){//   g//      p//         cRotateL(grandparent);parent->_col = BLACK;grandparent->_col = RED;}else{//     g//       p //     cRotateR(parent);RotateL(grandparent);cur->_col = BLACK;grandparent->_col = RED;}break;}}}// 不管上面怎么变都无所谓，只需要保证根节点是黑的就可以了_root->_col = BLACK;return true;}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;subR->_left = parent;Node* parentParent = parent->_parent;parent->_parent = subR;if (subRL)subRL->_parent = parent;if (_root == parent){_root = subR;subR->_parent = nullptr;}else{if (parentParent->_left == parent){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* parentParent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (_root == parent){_root = subL;subL->_parent = nullptr;}else{if (parentParent->_left == parent){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}}void inorder(){_inorder(_root);cout << endl;}bool isbalance(){return _isbalance(_root);}private:bool _check(Node* root, int blacknum, const int RefVal){// 判断黑色路径数量是否相等if (root == nullptr){if (blacknum != RefVal){cout << "黑色节点数量不相等" << endl;return false;}return true;}// 判断是否有连续的红色节点if (root->_col == RED && root->_parent->_col == RED){cout << "有连续的红色节点" << endl;return false;}if (root->_col == BLACK){blacknum++;}return _check(root->_left, blacknum, RefVal)&& _check(root->_right, blacknum, RefVal);}// 判断红黑树是否平衡bool _isbalance(Node* root){// 如果根节点是红的，说明错了if (root->_col == RED){cout << "根节点是红色" << endl;return false;}// 统计一下路径中有多少黑色节点int RefVal = 0;Node* cur = root;while (cur){if (cur->_col == BLACK)RefVal++;cur = cur->_left;}// 判断路径中的黑色节点是否相等return _check(root, 0, RefVal);}void _inorder(Node* root){if (root == nullptr)return;_inorder(root->_left);cout << root->_kv.second << " ";_inorder(root->_right);}Node* _root = nullptr;
};

int main()
{const int N = 100000;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 (auto e : v){cout << "Insert:" << e << "->";t.insert(make_pair(e, e));cout << t.isbalance() << endl;}cout << t.isbalance() << endl;return 0;
}

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

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

相关文章

pytorch框架学习(tensorboard的使用)

pytorch框架学习(tensorboard的使用)

什么是tensorboard&#xff1f; tensorboard是一个可视化工具&#xff0c;它可以把训练过程中的数据变化以图像的形式绘制出来&#xff0c;或者记录训练过程中使用的图片 tensorboard的安装&#xff1a; 在pycharm的终端中输出安装命令后自动安装—— pip install tensorbo…
阅读更多...
IP地址查询在社交行业中的崭新应用

IP地址查询在社交行业中的崭新应用

在社交媒体蓬勃发展的今天&#xff0c;IP地址查询技术IP66_ip归属地在线查询_免费ip查询_ip精准定位平台正在成为社交行业中的一项强大工具。这项技术不仅为社交平台提供了更多个性化服务的可能&#xff0c;还在用户安全和内容管理等方面发挥了关键作用。本文将深入探讨IP地址查…
阅读更多...
什么是集成测试？集成的方法有哪些？

什么是集成测试？集成的方法有哪些？

前言 综合测试整合测试非常复杂&#xff0c;需要一些开发和逻辑技能。的确如此&#xff01;那么把这个测试整合到我们的测试策略中的目的是什么呢&#xff1f;这个问题我们先不着急回答&#xff0c;让我们一步步往下看你就知道了。 为什么要进行集成测试&#xff1f; 以下是一…
阅读更多...
UE4动作游戏实例RPG Action解析四：装备系统

UE4动作游戏实例RPG Action解析四：装备系统

导语： 以加血道具为例，详细分析拆解ActionRPG的装备系统，包含装备系统需求和数据结构设计，以及实现 一、装备系统需求： 装备槽： 已获取装备和未获取装备： 当已经装备一个道具时，再次捡到道具，会把道具放在装备库，不会放在装备槽中， 当没有装备道具时，会拾取道具…
阅读更多...
算法通关村第十六关青铜挑战——原来滑动窗口如此简单！

算法通关村第十六关青铜挑战——原来滑动窗口如此简单！

大家好&#xff0c;我是怒码少年小码。 从本篇开始&#xff0c;我们就要开始算法的新篇章了——四大思想&#xff1a;滑动窗口、贪心、回溯、动态规划。现在&#xff0c;向我们迎面走来的是——滑动窗口思想&#xff01;&#x1f61d; 滑动窗口思想 概念 在数组双指针里&am…
阅读更多...
别试错了，是该关注一下软件内在质量了

别试错了，是该关注一下软件内在质量了

太多这种例子了&#xff0c;老板们早上出的新想法&#xff0c;恨不得第二天就能上线。。每个互联网公司都试图突破固定领地&#xff0c;不断地尝试新的业务&#xff0c;一旦发现不行&#xff0c;就立刻砍掉&#xff0c;名曰“试错”。 研发部门&#xff0c;为了应对压力&#…
阅读更多...
vue中通过.style.animationDuration属性，根据数据长度动态设定元素的纵向滚动时长的demo

vue中通过.style.animationDuration属性，根据数据长度动态设定元素的纵向滚动时长的demo

根据数据长度动态设定元素的animation 先看看效果&#xff0c;是一个纯原生div标签加上css实现的表格纵向滚动动画&#xff1a; 目录 根据数据长度动态设定元素的animationHTMLjs逻辑1、判断是数据长度是否达到滚动要求2、根据数据长度设置滚动速度 Demo完整代码 HTML 1、确…
阅读更多...
【机试题】LazyIterator迭代器懒加载问题

【机试题】LazyIterator迭代器懒加载问题

将下面这个未完成的Java工具类补充完成&#xff0c;实现懒加载的功能&#xff0c;该类需要实现Iterable接口&#xff0c;能够遍历所有数据。具体要求如下&#xff1a; 工具类提供了一个ValueLoader接口&#xff0c;用于获取数据&#xff0c;其中ValueLoader的接口定义为&#x…
阅读更多...
【Python】一文带你掌握数据容器之集合，字典

【Python】一文带你掌握数据容器之集合，字典

目录&#xff1a; 一、集合 思考&#xff1a;我们目前接触到了列表、元组、字符串三个数据容器了。基本满足大多数的使用场景为何又需要学习新的集合类型呢? 通过特性来分析: &#xff08;1&#xff09;列表可修改、支持重复元素且有序 &#xff08;2&#xff09;元组、字符…
阅读更多...
asp.net图书管理系统

asp.net图书管理系统

asp.net图书管理系统 基本操作图书管理 读者管理 借书 修改资料 修改密码 说明文档 运行前附加数据库.mdf&#xff08;或sql生成数据库&#xff09; 主要技术&#xff1a; 基于C#winform架构和sql server数据库 功能模块&#xff1a; 图书管理 读者管理 借书 修改资料 修改…
阅读更多...
JavaScript概述

JavaScript概述

一、JavaScript简介&#xff1a; JavaScript是互联网上流行的脚本语言&#xff0c;可用于HTML和web&#xff0c;可广泛应用于服务器、PC、笔记本、平板电脑和智能手机等设备。 JavaScript是一种轻量级的编程语言&#xff0c;可插入HTML页面的编程代码&#xff0c;插入HTML页面后…
阅读更多...
千兆路由只有200M，原来是模式选择不对，也找到了内网不能通过动态域名访问内部服务的原因

千兆路由只有200M，原来是模式选择不对，也找到了内网不能通过动态域名访问内部服务的原因

本来1000M的宽带接入的&#xff0c;但是一测试发现只有200M&#xff0c;把电信叼了过来&#xff0c; 一测试发现宽带没问题&#xff0c;网线正常&#xff0c;网卡正常&#xff0c;只有可能是路由器的问题了&#xff0c;尴尬了&#xff0c;赶紧给满意好评放他走。回头好好研究一…
阅读更多...
Springboot项目返回数据统一封装

Springboot项目返回数据统一封装

Springboot项目返回数据统一封装,支持swagger。 正常swagger会根据数据库表的注释显示对应的参数释义等。但当我们使用统一接口返回map时&#xff0c;部分注释等信息会被掩盖消失。在此提供三个java类即可满足统一封装返回接口&#xff0c;也可显示对应的swagger释义等。 1.Er…
阅读更多...
包教包会：Mysql主从复制搭建

包教包会：Mysql主从复制搭建

笑小枫的专属目录 一、无聊的理论知识1. 主从复制原理2. 主从复制的工作过程3. MySQL四种同步方式 二、docker下安装、启动mysql1. 安装主库2. 安装从库 三、配置Master(主)四、配置Slave(从)五、链接Master(主)和Slave(从)六、主从复制排错1. 错误&#xff1a;error connectin…
阅读更多...
链表的逆置

链表的逆置

方法1&#xff1a; 依次将指针反向&#xff0c;最后令头指针指向尾元素。 逆置过程如下&#xff1a; 当q指针为空时&#xff0c;循环结束。 //试写一算法&#xff0c;对单链表实现就地逆置&#xff0c; void Reverse1(List plist)//太复杂,不用掌握 {assert(plist ! NULL);i…
阅读更多...
linux 信号

linux 信号

信号的定义 在计算机科学中&#xff0c;信号是Unix、类Unix以及其他POSIX兼容的操作系统中进程间通讯的一种有限制的方式。它是一种异步的通知机制&#xff0c;用来提醒进程一个事件已经发生。当一个信号发送给一个进程&#xff0c;操作系统中断了进程正常的控制流程&#xff…
阅读更多...
五、nacos安装指南

五、nacos安装指南

Nacos安装指南 1.Windows安装 开发阶段采用单机安装即可。 1.1.下载安装包 在Nacos的GitHub页面&#xff0c;提供有下载链接&#xff0c;可以下载编译好的Nacos服务端或者源代码&#xff1a; GitHub主页&#xff1a;https://github.com/alibaba/nacos GitHub的Release下载…
阅读更多...
自然语言处理（NLP）-spacy简介以及安装指南（语言库zh_core_web_sm）

自然语言处理（NLP）-spacy简介以及安装指南（语言库zh_core_web_sm）

spacy 简介 spacy 是 Python 自然语言处理软件包&#xff0c;可以对自然语言文本做词性分析、命名实体识别、依赖关系刻画&#xff0c;以及词嵌入向量的计算和可视化等。 1.安装 spacy 使用 “pip install spacy" 报错&#xff0c; 或者安装完 spacy&#xff0c;无法正…
阅读更多...
【差旅游记】启程-新疆哈密（1）

【差旅游记】启程-新疆哈密（1）

哈喽&#xff0c;大家好&#xff0c;我是雷工。 最近有个新疆罗布泊的项目要去现场&#xff0c;领导安排我过去&#xff0c;这也算第一次到新疆&#xff0c;记录下去新疆的过程。 01、天有不测风云 本来预定的是11月2号石家庄飞成都&#xff0c;成都转机到哈密&#xff0c;但…
阅读更多...
vmware 修改主机名称 hadoop 服务器环境配置(一)

vmware 修改主机名称 hadoop 服务器环境配置(一)

如何在虚拟机配置主机名称&#xff1a; 1. 如图所示在/etc 文件夹下有个hosts文件。追加映射关系&#xff1a; #关系 ip地址 名称 192.168.164.20 hadoop20 2. 保存后&#xff0c;重启reboot即可
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023