【简易版tinySTL】 红黑树- 定义, 插入, 构建

文章目录

    • 旋转
      • 左旋
      • 右旋
    • 左旋右旋代码实现
    • 红黑树的基本性质
    • 红黑树的插入
    • 红黑树的插入示例
    • 红黑树修复代码实现
    • 参考资料

旋转

image-20240613095136796

对于一个平衡二叉搜索树,左子树高度为4,右子树高度为2,它们的高度差为2,破坏了平衡性(高度差<2才算平衡,因此需要调整二叉树使其平衡)

二叉树最基本的调整方式包括左旋、右旋:

左旋

  • 不平衡点没有左子树

image-20240613095515121

  • 不平衡点有左子树

image-20240613095615583

当结点5左旋时,由于有左子树3,会和结点6冲突,阻碍旋转,我们需要将"冲突的左孩变右孩",即将结点6连在被旋转点5的右孩子上

右旋

  • 不平衡点没有右子树

image-20240613095954955

  • 不平衡点有右子树

image-20240613100021786

当结点14右旋时,由于有右子树17,会和结点9冲突,阻碍旋转,我们需要将"冲突的右孩变左孩",即将结点9连在被旋转点14的左孩子上

左旋右旋代码实现

Node* rightRotate(Node* node)
{// node为失衡节点Node* l_son = node->left;// 不管是否会发生冲突,都把冲突的右孩变左孩node->left = l_son->right;// 右孩变左孩后,更新父节点(前提它不是空节点)if(node->left){node->left->parent = node;}// 更新旋转中心的父节点指向l_son->parent = node->parent;// 如果当前节点(node)是根节点,则更新根节点为 l_sonif(l_son->parent == nullptr){root = l_son;}// 如果node是父结点的左子节点else if(node->parent->left == node){node->parent->left = l_son;}else{// 如果node是父结点的右子节点node->parent->right = l_son;}// 把node结点接在l_son右边node->parent = l_son;l_son->right = node;return l_son;
}Node* leftRotate(Node* node)
{Node* r_son = node->right;// 提前断掉右结点node->right = r_son->left;if(r_son->left){node->right = r_son->left;r_son->left->parent = node;}r_son->parent = node->parent;if(r_son->parent == nullptr){root = r_son;}else if(node->parent->left == node){node->parent->left = r_son;}else{node->parent->right = r_son;}r_son->left = node;node->parent = r_son;return r_son;
}

红黑树的基本性质

空结点也是红黑树的叶子结点,也属于黑结点

  • 根叶黑:根和叶子结点默认为黑色
  • 不红红:不存在连续2个红色结点
  • 黑路同:任一结点到叶子结点的所有路径,黑结点的数量相同(包括空结点/叶子结点)

image-20240613100233691

红黑树的插入

要求:

  1. 默认插入的都是红色
  2. 插入情况讨论:
    • 插入的结点是根结点:直接变黑
    • 插入结点的叔叔结点是红色:叔父爷变色,当前指针指向爷爷结点,修复爷爷结点的红黑树性质
    • 插入结点的叔叔结点是黑色:先旋转(LL、RR、LR、RL),后变色

image-20240620191458222

image-20240620191519731

image-20240620192947162

红黑树的插入示例

假设我们要依次插入:17、18、23、34、27、15、9、6、8、5、25

我们每次插入之后,都要检查是否满足红黑树的性质

微信图片_20240620192221

红黑树修复代码实现

/*O/O /O	<= target
*/
void insertFixup(Node* target) // target是当前插入的结点
{// 父结点存在,且出现红红while(target->parent && target->parent->color == Color::RED){Node* father = target->parent;Node* g_father;if(father)g_father = father->parent;// 父是爷的左孩子if(g_father && g_father->left == father){Node* uncle = g_father->right;// 如果叔结点存在,且颜色为红色if(uncle && uncle->color == Color::RED){// 叔父爷变色uncle->color = Color::BLACK;father->color = Color::BLACK;g_father->color = Color::RED;// 将当前指针指向爷结点target = g_father;}// 叔结点不存在或者颜色为黑色(LL/LR)else{// LRif(target == g_father->left->right){// 先左旋,旋转函数的输入结点是失衡点leftRotate(father);}// RR和LR后面的步骤都是一样的Node* t = rightRotate(g_father);// 变色t->color = Color::BLACK;t->right->color = Color::RED;t->left->color = Color::RED;return;}}if(g_father && g_father->right == father){Node* uncle = g_father->left;if(uncle && uncle->color == Color::RED){g_father->color = Color::RED;father->color = Color::BLACK;uncle->color = Color::BLACK;target = g_father;}else{// RLif(target == g_father->right->left){// !不是旋转父结点rightRotate(father);}// LL和RL后续都一样Node* t = leftRotate(g_father);t->color = Color::BLACK;t->left->color = Color::RED;t->right->color = Color::RED;return;}}root->color = Color::BLACK;}
}void insert(Key k, Value v)
{Node* node = new Node(k, v);Node* p = nullptr;Node* cur = root;if(this->size == 0){root = node;size++;return;}// 找到插入点while(cur){p = cur;if(k > cur->key){cur = cur->right;}else if(k < cur->key){cur = cur->left;}else{std::cout << "the key was in the tree" << std::endl;delete node;return;}}// 插入新结点size++;if(k > p->key){p->right = node;}else{p->left = node;}node->parent = p;if(!p){root = node;}// 修复红黑树insertFixup(node);
}

参考资料

红黑树 - 定义, 插入, 构建

红黑树 - 删除

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

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

相关文章

在我们的大数据平台(XSailbaot)上进行企业级数据建模的思路

1. 背景 笔者所在的公司是差不多二十年前搞CIM&#xff08;公共信息模型的&#xff09;起家的。当时公司的前辈搞了基于CIS协议的模型服务器、数据服务器、模式编辑器等&#xff0c;形成了一套基于公共信息模型建模的平台系统。其中可视化建模&#xff0c;建好了模式类以后&am…

SCI二区|北极海鹦优化算法(APO)原理及实现【免费获取Matlab代码】

目录 1.背景2.算法原理2.1算法思想2.2算法过程 3.结果展示4.参考文献5.代码获取 1.背景 2024年&#xff0c;W Wang受到北极海鹦的生存和捕食行为启发&#xff0c;提出了北极海鹦优化算法&#xff08;Arctic Puffin Optimization, APO&#xff09;。 2.算法原理 2.1算法思想 …

全局静态变量、全局变量以及atexit回调的执行顺序

版本 gcc version 7.5.0 (Ubuntu 7.5.0-6ubuntu2) Linux UM480XT 5.15.0-107-generic #117~20.04.1-Ubuntu SMP Tue Apr 30 10:35:57 UTC 2024 x86_64 x86_64 x86_64 GNU/Linux Microsoft Visual Studio Enterprise 2019, _MSC_VER 1929 #include <stdio.h> #include…

tomcat8.5在windows下运行出现日志中文乱码

更多ruoyi-nbcio功能请看演示系统 gitee源代码地址 前后端代码&#xff1a; https://gitee.com/nbacheng/ruoyi-nbcio 演示地址&#xff1a;RuoYi-Nbcio后台管理系统 http://218.75.87.38:9666/ 更多nbcio-boot功能请看演示系统 gitee源代码地址 后端代码&#xff1a; h…

基于SpringBoot漫画网站系统设计和实现(源码+LW+调试文档+讲解等)

&#x1f497;博主介绍&#xff1a;✌全网粉丝10W,CSDN作者、博客专家、全栈领域优质创作者&#xff0c;博客之星、平台优质作者、专注于Java、小程序技术领域和毕业项目实战✌&#x1f497; &#x1f31f;文末获取源码数据库&#x1f31f; 感兴趣的可以先收藏起来&#xff0c;…

React@16.x(44)路由v5.x(9)源码(1)- path-to-regexp

目录 1&#xff0c;作用2&#xff0c;实现获取 match 对象2.1&#xff0c;match 对象的内容2.2&#xff0c;注意点2.3&#xff0c;实现 1&#xff0c;作用 之前在介绍 2.3 match 对象 时&#xff0c;提到了 react-router 使用第3方库 path-to-regexp 来匹配路径正则。 我们也…

《昇思25天学习打卡营第17天 | 昇思MindSporeCycleGAN图像风格迁移互换》

17天 本节学习了CycleGAN图像风格迁移互换。 CycleGAN即循环对抗生成网络&#xff0c;该模型实现了一种在没有配对示例的情况下学习将图像从源域 X 转换到目标域 Y 的方法。该模型一个重要应用领域是域迁移&#xff0c;可以通俗地理解为图像风格迁移。其实在 CycleGAN 之前&a…

打破生态「孤岛」,Catizen将开启Telegram小游戏2.0时代?

Catizen&#xff1a;引领Telegram x TON生态的顶级猫咪链游 在区块链游戏领域&#xff0c;吸引玩家的首要因素往往是游戏的趣味性。然而&#xff0c;仅靠趣味性无法评估一个项目的长期价值和发展潜力。真正能在区块链游戏市场中取得长久成功的项目&#xff0c;无一例外都依靠扎…

Mozilla Firefox正在尝试集成ChatGPT等帮助用户总结或改写网页内容

Mozilla基金会开启了一项新计划&#xff1a;在接下来几个月里尝试在Firefox浏览器里集成 ChatGPT 等 AI 服务&#xff0c;帮助用户在网页上总结内容或者改写内容等。Firefox浏览器集成的 AI 服务包括但不限于 ChatGPT、Google Gemini、HuggingChat 等&#xff0c;当然这并不是把…

计算机网络之数据通信原理(下)

上一讲内容&#xff1a;数据传输方式、数据传输形式、传输差错处理、常用差错检测方法 数据通信过程中&#xff0c;一个很重要的问题就是如何控制数据的传输&#xff0c;就涉及到了传输控制规程&#xff08;协议&#xff09; 下面介绍两种&#xff1a; ①BSC&#xff1a;面向…

AI模型的奥运会:谁将在OlympicArena中夺冠?

获取本文论文原文PDF&#xff0c;请在公众号【AI论文解读】留言&#xff1a;论文解读 引言&#xff1a;AI模型的奥林匹克级评测 评估和比较不同AI模型的性能始终是一个核心话题。随着技术的不断进步&#xff0c;这些模型在处理复杂任务的能力上有了显著的提升。为了更精确地衡…

pytest测试框架pytest-random-order插件随机执行用例顺序

Pytest提供了丰富的插件来扩展其功能&#xff0c;本章介绍下pytest-random-order插件&#xff0c;随机设置pytest测试用例的运行顺序&#xff0c;并对随机性进行一些控制。 官方文档&#xff1a; https://pytest-cov.readthedocs.io/en/latest/index.html 适配版本说明&#x…

istitle()方法——判断首字母是否大写其他字母小写

自学python如何成为大佬(目录):https://blog.csdn.net/weixin_67859959/article/details/139049996?spm1001.2014.3001.5501 语法参考 istitle()方法用于判断字符串中所有的单词首字母是否为大写而其他字母为小写。istitle()方法的语法格式如下&#xff1a; str.istitle() …

【超级简单】植物大战僵尸杂交版V2.1,手机上最简单的安装方法~!

大家好&#xff0c;我是坤坤黑科技&#xff01;之前给大家分享了植物大战僵尸杂交版手机的安装方法&#xff0c;但是很多朋友还是因为操作难度大所以没有玩到。今天发现一个更加简单的在手机上玩植物大战僵尸杂交版的方法&#xff0c;直接安装就可以玩到最新的2.1版本~ 植物大…

基于UDP的网络聊天室(多线程实现收和发消息)

要求&#xff1a;1.有新用户登录&#xff0c;其他在线的用户可以收到登录信息 2.有用户群聊&#xff0c;其他在线的用户可以收到群聊信息 3.有用户退出&#xff0c;其他在线的用户可以收到退出信息 4.服务器可以发送系统信息 效果图&#xff1a; service.c #include <head…

【NodeJs】入门

目录 一、前导 二、 url模块 三、path模块 四、buffer模块 五、fs模块 六、stream流模块 七、os模块 八、crypto模块 九、util模块 十、http模块 nodejs官网 Node.js — 在任何地方运行 JavaScript nmp是Node.js包管理器&#xff0c;用来安装各种库、框架和工具&…

音视频开发30 FFmpeg 视频编码- 流程以及重要API,H264编码原理说明,该章节使用h264编码说明

一.H264编码原理 1 视频为什么需要进行编码压缩 ◼ 一张为 720x480 的图像&#xff0c;用 YUV420P 的格式来表示&#xff0c;其大小为&#xff1a; 720*480*1.5 约等于 0.5MB 。 ◼ 如果是 25 帧&#xff0c; 10 分钟的数据量 0.5M*10*60*25 7500MB -> 7GB 多 ◼ …

Open3D(C++) 删除点云中重复的点

目录 一、算法原理1、重叠点2、主要函数二、代码实现三、结果展示本文由CSDN点云侠原创,原文链接。如果你不是在点云侠的博客中看到该文章,那么此处便是不要脸的爬虫与GPT。 一、算法原理 1、重叠点 原始点云克隆一份   构造重叠区域   合并点云获得重叠点 2、主要…

2024 Parallels Desktop for Mac 功能介绍

Parallels Desktop的简介 Parallels Desktop是一款由Parallels公司开发的桌面虚拟化软件&#xff0c;它允许用户在Mac上运行Windows和其他操作系统。通过强大的技术支持&#xff0c;用户无需重新启动电脑即可在Mac上运行Windows应用程序&#xff0c;实现了真正的无缝切换。 二…

Python变量的命名规则与赋值方式

第二章&#xff1a;Python 基础语法 第一节&#xff1a;变量的命名规则与赋值方式 2.1.1 引言 在编程中&#xff0c;变量是存储数据的基本单元。变量的命名和赋值是编程语言中表达和操作数据的基础。了解和遵循变量命名规则对于编写清晰、可维护的代码至关重要。 2.1.2 变量…