红黑树的插入

文章目录

  • 3.红黑树
    • 3.1概念
    • 3.2 性质
    • 3.3 RBTree的实现
      • 3.3.1 insert的框架
      • 3.3.2 insert的处理
      • 3.3.3 中序遍历
      • 3.3.4检查是否平衡和获取树的高度
    • 3.4完整代码

3.红黑树

3.1概念

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

image-20240730115620218

3.2 性质

  1. 每个结点不是红色就是黑色
  2. 根节点是黑色的
  3. 如果一个节点是红色的，则它的两个孩子结点是黑色的, 说明树里面不能出现连续的红色节点
  4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
  5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点), 这个性质是为了方便数树有几条路径

问题: 为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点个数的两倍？

解答: 根据性质3和性质4可知, 如果有一颗红黑树, 那么它的最短路径应是全黑节点, 最长路径应是一红一黑节点交替
于是, 我们可以得到一个结论, 假设每条路径有N个黑色节点, 那么每条路径的节点个数为[N, 2N]. 这样就满足了问题红黑树的特征, 即
最长路径中节点个数不会超过最短路径节点个数的两倍

3.3 RBTree的实现

3.3.1 insert的框架

与前面的avl树类似

#pragma once
enum Color
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{RBTreeNode(const pair<K, V>& kv) : _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(RED) {}RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;pair<K, V> _kv;Color _color;
};template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:bool insert(const pair<K, V>& kv){// a. 树为空，则直接新增节点，赋值给root指针if (_root == nullptr) {_root = new Node(kv);// 根节点是黑色的_root->_color = BLACK;return true;}// b. 树不空，按二叉搜索树性质查找插入位置，插入新节点Node* cur = _root, * 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为空,找到了一个合适的位置,此时需要链接,注意链接位置cur = new Node(kv);// cur->_color = ?? if (kv.first < parent->_kv.first) {parent->_left = cur;cur->_parent = parent;}else {parent->_right = cur;cur->_parent = parent;}// new code....return true;}
private:Node* _root = nullptr;
};

3.3.2 insert的处理

新增节点, 选择红色, 因为黑色会影响其他路径

  1. 新增节点的父亲是黑色的, 不需要处理
  2. 新增节点的父亲是红色的, 需要处理
    (变色)or(变色+旋转)

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

情况1: cur为红，p为红，g为黑， u 存在且为红 \textcolor{red}{u存在且为红} u存在且为红

image-20240731121943681

while (parent && parent->_color == RED) {Node* grandparent = parent->_parent;if (parent == grandparent->_left) {Node* uncle = grandparent->_right;// uncle存在且为红, 情况1if (uncle && uncle->_color == RED) {//        g(b)//     p(r)  u(r)//  c(r)// 变色parent->_color = uncle->_color = BLACK;grandparent->_color = RED;// 继续向上处理cur = grandparent;parent = cur->_parent;}}
}
// 处理后_root可能会变色, 在这里它置为黑色
_root = BLACK;

​

情况2:cur为红，p为红，g为黑， u 不存在 / u 存在且为黑 \textcolor{red}{u不存在/u存在且为黑} u不存在/u存在且为黑

image-20240805162910573

while (parent && parent->_color == RED) {Node* grandparent = parent->_parent;if (parent == grandparent->_left) {Node* uncle = grandparent->_right;// uncle存在且为红, 情况1if (uncle && uncle->_color == RED) {//        g(b)//     p(r)  u(r)//  c(r)// 变色parent->_color = uncle->_color = BLACK;grandparent->_color = RED;// 继续向上处理cur = grandparent;parent = cur->_parent;}// uncle为黑或者不存在else {// cur在parent的左边, 情况2, 单旋if (cur = parent->_left) {//        g(b)//     p(r)  u(b)//  c(r)RotateR(grandparent);parent->_color = BLACK;grandparent->_color = RED;}break;}}
}
// 处理后_root可能会变色, 在这里它置为黑色
_root = BLACK;

情况3:cur为红，p为红，g为黑， u 不存在 / u 存在且为黑 \textcolor{red}{u不存在/u存在且为黑} u不存在/u存在且为黑, cur的位置与前面不同

image-20240805171707446

while (parent && parent->_color == RED) {Node* grandparent = parent->_parent;if (parent == grandparent->_left) {Node* uncle = grandparent->_right;// uncle存在且为红, 情况1if (uncle && uncle->_color == RED) {//        g(b)//     p(r)  u(r)//  c(r)// 变色parent->_color = uncle->_color = BLACK;grandparent->_color = RED;// 继续向上处理cur = grandparent;parent = cur->_parent;}// uncle为黑或者不存在else {// cur在parent的左边, 情况2, 单旋if (cur = parent->_left) {//        g(b)//     p(r)  u(b)//  c(r)RotateR(grandparent);parent->_color = BLACK;grandparent->_color = RED;}// cur在parent的右边, 情况3, 双旋else {//         g(b)//     p(r)    u(b)//		   c(r)RotateL(parent);RotateR(grandparent);cur->_color = BLACK;grandparent->_color = RED;}break;}}
}
// 处理后_root可能会变色, 在这里它置为黑色
_root = BLACK;

完善else条件

while (parent && parent->_color == RED) {Node* grandparent = parent->_parent;if (parent == grandparent->_left) {Node* uncle = grandparent->_right;// uncle存在且为红, 情况1if (uncle && uncle->_color == RED) {//        g(b)//     p(r)  u(r)//  c(r)// 变色parent->_color = uncle->_color = BLACK;grandparent->_color = RED;// 继续向上处理cur = grandparent;parent = cur->_parent;}// uncle为黑或者不存在else {// cur在parent的左边, 情况2, 单旋if (cur = parent->_left) {//        g(b)//     p(r)  u(b)//  c(r)RotateR(grandparent);parent->_color = BLACK;grandparent->_color = RED;}// cur在parent的右边, 情况3, 双旋else {//         g(b)//     p(r)    u(b)//		   c(r)RotateL(parent);RotateR(grandparent);cur->_color = BLACK;grandparent->_color = RED;}break;}}// parent == grandparent->_rightelse {// uncle存在且为红, 情况1if (uncle && uncle->_color == RED) {//        g(b)//    u(r)   p(r)//               c(r)// 变色parent->_color = uncle->_color = BLACK;grandparent->_color = RED;// 继续向上处理cur = grandparent;parent = cur->_parent;}// uncle为黑或者不存在else {// cur在parent的右边, 情况2, 单旋if (cur = parent->_right) {//        g(b)//     u(b)  p(r)//			      c(r)RotateL(grandparent);parent->_color = BLACK;grandparent->_color = RED;}// cur在parent的右边, 情况3, 双旋else {//         g(b)//     u(r)    p(b)//		   c(r)RotateR(parent);RotateL(grandparent);cur->_color = BLACK;grandparent->_color = RED;}break;}}
}
// 处理后_root可能会变色, 在这里它置为黑色
_root = BLACK;
return true;

3.3.3 中序遍历

void InOrder()
{_InOrder(_root);cout << endl;
}
void _InOrder(Node* root)
{if (root == nullptr)	return;_InOrder(root->_left);cout << root->_kv.first << ' ';_InOrder(root->_right);
}

3.3.4检查是否平衡和获取树的高度

bool IsBalance()
{if (_root == nullptr)	return true;// 违反规则2if (_root->_color == RED)	return false;int refVal = 0;		// 参考值, 记录某一条路径上的黑色节点的数量Node* cur = _root;while (cur) {if (cur->_color == BLACK)refVal++;cur = cur->_left;}int blackNum = 0;return Check(_root, refVal, blackNum);
}bool Check(Node* root, const int& refVal, int blackNum)
{if (root == nullptr) { // cout << blackNum << endl;if(blackNum == refVal)return true; else {cout << "有路径黑色节点数量不一致" << endl;return false;}}if (root->_color == BLACK)	blackNum++;if (root->_color == RED && root->_parent->_color == RED) {// 违反规则3cout << "有连续的红色节点" << endl;return false;}return Check(root->_left, refVal, blackNum) && Check(root->_right, refVal, blackNum);
}

int GetHeight()
{return _GetHeight(_root);
}
int _GetHeight(Node* root)
{if (root == nullptr)	return 0;int left = _GetHeight(root->_left);int right = _GetHeight(root->_right);return left > right ? left + 1 : right + 1;
}

3.4完整代码

#pragma once
#include <iostream>
#include <vector>
using namespace std;
enum Color
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{RBTreeNode(const pair<K, V>& kv) : _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _color(RED) {}RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;pair<K, V> _kv;Color _color;
};template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:bool insert(const pair<K, V>& kv){// a. 树为空，则直接新增节点，赋值给root指针if (_root == nullptr) {_root = new Node(kv);// 根节点是黑色的_root->_color = BLACK;return true;}// b. 树不空，按二叉搜索树性质查找插入位置，插入新节点Node* cur = _root, *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为空,找到了一个合适的位置,此时需要链接,注意链接位置cur = new Node(kv);cur->_color = RED;		// 新增节点给红色if (parent->_kv.first < kv.first) {parent->_right = cur;cur->_parent = parent;}else {parent->_left = cur;cur->_parent = parent;}while (parent && parent->_color == RED) {Node* grandparent = parent->_parent;if (parent == grandparent->_left) {Node* uncle = grandparent->_right;// uncle存在且为红, 情况1if (uncle && uncle->_color == RED) {//        g(b)//     p(r)  u(r)//  c(r)// 变色parent->_color = uncle->_color = BLACK;grandparent->_color = RED;// 继续向上处理cur = grandparent;parent = cur->_parent;}// uncle为黑或者不存在else {// cur在parent的左边, 情况2, 单旋if (cur == parent->_left) {//        g(b)//     p(r)  u(b)//  c(r)RotateR(grandparent);parent->_color = BLACK;grandparent->_color = RED;}// cur在parent的右边, 情况3, 双旋else {//         g(b)//     p(r)    u(b)//		   c(r)RotateL(parent);RotateR(grandparent);cur->_color = BLACK;grandparent->_color = RED;}break;}}// parent == grandparent->_rightelse {Node* uncle = grandparent->_left;// uncle存在且为红, 情况1if (uncle && uncle->_color == RED) {//        g(b)//    u(r)   p(r)//               c(r)// 变色parent->_color = uncle->_color = BLACK;grandparent->_color = RED;// 继续向上处理cur = grandparent;parent = cur->_parent;}// uncle为黑或者不存在else {// cur在parent的右边, 情况2, 单旋if (cur == parent->_right) {//        g(b)//     u(b)  p(r)//			      c(r)RotateL(grandparent);parent->_color = BLACK;grandparent->_color = RED;}// cur在parent的左边, 情况3, 双旋else {//         g(b)//     u(r)    p(b)//		   c(r)RotateR(parent);RotateL(grandparent);cur->_color = BLACK;grandparent->_color = RED;}break;}}}// 处理后_root可能会变色, 在这里它置为黑色_root->_color = BLACK;return true;}void InOrder(){_InOrder(_root);cout << endl;}bool IsBalance(){if (_root == nullptr)	return true;// 违反规则2if (_root->_color == RED)	return false;int refVal = 0;		// 参考值, 记录某一条路径上的黑色节点的数量Node* cur = _root;while (cur) {if (cur->_color == BLACK)refVal++;cur = cur->_left;}int blackNum = 0;return Check(_root, refVal, blackNum);}// 获得树的高度size_t GetHeight(){return _GetHeight(_root);}// 获得节点数size_t GetSize(){return _GetSize(_root);}
private:Node* _root = nullptr;
protected:// 新节点插入较高右子树的右侧---右右：左单旋  void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;// 由于parent不一定是整棵树的根,后面更新subR的parent时需要用到parentParentNode* parentParent = parent->_parent;parent->_right = subRL;// 注意,subRL可能为nullptrif (subRL)subRL->_parent = parent;subR->_left = parent;parent->_parent = subR;if (parent == _root) {_root = subR;subR->_parent = nullptr;}// parent不是整棵树的根else {if (parentParent->_left == parent)parentParent->_left = subR;elseparentParent->_right = subR;}subR->_parent = parentParent;}// 新节点插入较高左子树的左侧---左左：右单旋  void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;Node* parentParent = parent->_parent;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;parent->_parent = subL;if (parent == _root) {_root = subL;subL->_parent = nullptr;}else {if (parent == parentParent->_left)parentParent->_left = subL;elseparentParent->_right = subL;subL->_parent = parentParent;}}void _InOrder(Node* root){if (root == nullptr)	return;_InOrder(root->_left);cout << root->_kv.first << ' ';_InOrder(root->_right);}bool Check(Node* root, const int& refVal, int blackNum){if (root == nullptr) { // cout << blackNum << endl;if(blackNum == refVal)return true; else {cout << "有路径黑色节点数量不一致" << endl;return false;}}if (root->_color == BLACK)	blackNum++;if (root->_color == RED && root->_parent->_color == RED) {// 违反规则3cout << "有连续的红色节点" << endl;return false;}return Check(root->_left, refVal, blackNum) && Check(root->_right, refVal, blackNum);}size_t _GetHeight(Node* root){if (root == nullptr)	return 0;size_t left = _GetHeight(root->_left);size_t right = _GetHeight(root->_right);return left > right ? left + 1 : right + 1;}size_t _GetSize(Node* root){if (root == nullptr)	return 0;else return _GetSize(root->_left) + _GetSize(root->_right) + 1;}
};

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

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

相关文章

07一阶电路和二阶电路的时域分析

07一阶电路和二阶电路的时域分析

一阶电路和二阶电路的时域分析 时域分析、频域分析、复频域分析本应该在信号与系统&#xff0c;或者数字信号处理这一章节里面进行处理的。 但在电路理论中也有这些知识&#xff0c;那就要好好掌握一下&#xff0c;打个底。详细细致的部分放到信号与系统里面去掌握
阅读更多...
【单片机开发软件】使用VSCode开发STM32环境搭建

【单片机开发软件】使用VSCode开发STM32环境搭建

&#x1f48c; 所属专栏&#xff1a;【单片机开发软件技巧】 &#x1f600; 作  者&#xff1a; 于晓超 &#x1f680; 个人简介&#xff1a;嵌入式工程师&#xff0c;专注嵌入式领域基础和实战分享 &#xff0c;欢迎咨询&#xff01; &#x1f496; 欢迎大家&#xff1…
阅读更多...
Java Web —— 第四天（HTTP协议，Tomcat）

Java Web —— 第四天（HTTP协议，Tomcat）

HTTP-概述 概念:Hyper Text Transfer Protocol&#xff0c;超文本传输协议&#xff0c;规定了浏览器和服务器之间数据传输的规则 特点: 1. 基于TCP协议:面向连接&#xff0c;安全 2.基于请求-响应模型的:一次请求对应一次响应 3. HTTP协议是无状态的协议: 对于事务处理没有…
阅读更多...
ASUS/华硕魔霸新锐2020 G512L系列 原厂win10系统 工厂文件 带F12 ASUS Recovery恢复

ASUS/华硕魔霸新锐2020 G512L系列 原厂win10系统 工厂文件 带F12 ASUS Recovery恢复

华硕工厂文件恢复系统 &#xff0c;安装结束后带隐藏分区&#xff0c;一键恢复&#xff0c;以及机器所有驱动软件。 系统版本&#xff1a;windows10 原厂系统下载网址&#xff1a;http://www.bioxt.cn 需准备一个20G以上u盘进行恢复 请注意&#xff1a;仅支持以上型号专用…
阅读更多...
【多线程】CAS、ABA问题详解

【多线程】CAS、ABA问题详解

一、什么是 CAS CAS&#xff1a;全称 Compare and swap&#xff0c;字⾯意思&#xff1a;⽐较并交换 比较内存和 CPU 中的内容&#xff0c;如果发现相同&#xff0c;就进行交换 交换的是内存和另一个寄存器的内容 一个内存的数据和两个寄存器中的数据进行操作&#xff08;寄…
阅读更多...
CSS 多按钮根据半圆弧度排列

CSS 多按钮根据半圆弧度排列

需求 多个按钮根据弧度&#xff0c;延边均匀排列。 实现 HTML 分两级&#xff1b;第一级&#xff0c;外层定义按钮的 compose-container 宽度&#xff1b;第二级&#xff0c;按钮集合&#xff0c;使用方法 styleBtn(index)&#xff0c;根据索引计算&#xff1b; <div c…
阅读更多...
青岛实训 8月9号 day25

青岛实训 8月9号 day25

mysql下载路径&#xff1a; MySQL :: MySQL Community Downloads [root2 ~]# vim py001.pya3b4print(ab)print(a**2b**2)[root2 ~]# python py001.py 725[root2 ~]# python3>>> import random>>> random<module random from /usr/lib64/python3.6/random…
阅读更多...
vue3、uniapp-vue3模块自动导入

vue3、uniapp-vue3模块自动导入

没有使用插件 使用插件,模块自动导入 安装: npm i -D unplugin-auto-importvite.config.js (uniapp没有此文件,在项目根目录下创建) import { defineConfig } from "vite"; import uni from "dcloudio/vite-plugin-uni"; import AutoImport from &qu…
阅读更多...
Mask-Rcnn

Mask-Rcnn

一 、FPN层 FPN层的基本作用 基本网络架构 基本思想 将多个阶段特征图融合在一起&#xff0c;这就相当于既有了高层的语义特征&#xff0c;也有了低层的轮廓特征 二、RPN层 三、ROI Align层
阅读更多...
Java环境安装与配置——eclipse

Java环境安装与配置——eclipse

目录 一、下载安装jdk 二、环境配置 三、下载安装eclipse软件 四、Java命名规则 一、下载安装jdk 1.下载页面 https://www.oracle.com/java/technologies/javase-jdk13-downloads.html 2.下载到本地安装 3.鼠标双击打开 4.选择安装路径并记住位置。建议&#xff1a;最好不…
阅读更多...
SQL Zoo 8.Using Null

SQL Zoo 8.Using Null

以下数据均来自SQL Zoo 1.List the teachers who have NULL for their department.&#xff08;列出所属部门为NULL的教师&#xff09; select name from teacher where dept is null 2.Note the INNER JOIN misses the teachers with no department and the departments wit…
阅读更多...
JVM -- 类加载器

JVM -- 类加载器

类加载器(ClassLoader)是Java虚拟机提供给应用程序去实现访问接口和类字节码数据的技术。类加载器只负责加载过程中的字节码获取并加载到内存的这一过程。 一、 类加载器的分类 类加载器的详细信息可以使用Arthas通过classloader命令查看&#xff1a; 1.启动类加载器(Boots…
阅读更多...
代码随想录打卡第五十三天

代码随想录打卡第五十三天

代码随想录–图论部分 day 53 图论第三天 文章目录 代码随想录--图论部分一、卡码网101--孤岛的总面积二、卡码网102--沉没孤岛三、卡码网103--水流问题四、卡码网104--建造最大岛屿 一、卡码网101–孤岛的总面积 代码随想录题目链接&#xff1a;代码随想录 给定一个由 1&…
阅读更多...
绘图仪 -- Web前端开发和Canvas绘图

绘图仪 -- Web前端开发和Canvas绘图

Canvas绘图介绍 Canvas绘图是HTML5中引入的一个非常强大的特性&#xff0c;它允许开发者使用JavaScript在网页上绘制图形、图表、动画等。<canvas>元素提供了一个通过JavaScript和Canvas API进行绘图的环境。 创建绘图仪对象 // 定义一个名为 XYPlotter 的函数&#x…
阅读更多...
Mapboxgl 实现弧线功能

Mapboxgl 实现弧线功能

更多精彩内容尽在 dt.sim3d.cn &#xff0c;关注公众号【sky的数孪技术】&#xff0c;技术交流、源码下载请添加VX&#xff1a;digital_twin123 代码如下&#xff1a; const mapCenter [-0.5, 51.8];// please use your own token! const map new mapboxgl.Map({container: …
阅读更多...
怎样才算精通 Excel？

怎样才算精通 Excel？

最强AI视频生成&#xff1a;小说文案智能分镜智能识别角色和场景批量Ai绘图自动配音添加音乐一键合成视频百万播放量https://aitools.jurilu.com/ 高赞回答很系统&#xff0c;但普通人这么学&#xff0c;没等精通先学废了&#xff01; 4年前&#xff0c;我为了学数据分析&#…
阅读更多...
iOS Object-C 创建类别(Category) 与使用

iOS Object-C 创建类别(Category) 与使用

有时候使用系统给出类或者第三方的类,但是呢它们自带的属性和方法又太少,不够我们的业务使用,这时候就需要给“系统的类或者第三方类”创建一个类别(Category),把自己的想添加的属性和方法写进来. Category模式用于向已经存在的类添加方法从而达到扩展已有类的目的 一:创建Ca…
阅读更多...
继承（二）

继承（二）

隐藏/重定义&#xff1a;子类和父类有同名的成员&#xff0c;子类成员隐藏了父类的成员。 重载&#xff1a;同一个作用域&#xff0c;重载了参数。 &#xff08;在实际中最好不要定义同名函数&#xff09; 子类对象不能初始化父类对象&#xff0c;用父类成员初始化子类成员。…
阅读更多...
开关电源之结构分析

开关电源之结构分析

如有技术问题及技术需求请加作者微信！ 开关电源之结构分析 1、开关电源的结构 常用开关电源，主要是为电子设备提供直流电源供电。电子设备所需要的直流电压，范围一般都在几伏到十几伏，而交流市电电源供给的电压为220V（110V），频率为50Hz（60Hz）。开关电源的作用就是把一…
阅读更多...
【Unity】线性代数基础：矩阵、矩阵乘法、转置矩阵、逆矩阵、正交矩阵等

【Unity】线性代数基础：矩阵、矩阵乘法、转置矩阵、逆矩阵、正交矩阵等

文章目录 矩阵&#xff08;Matrix&#xff09;矩阵能干啥&#xff1f;矩阵基本运算矩阵加减法矩阵和标量的乘法矩阵和矩阵的乘法矩阵的转置矩阵相等 特殊的矩阵方块矩阵对称矩阵对角元素&#xff08;Diagonal Elements&#xff09;对角矩阵&#xff08;Diagonal Matrix&#xf…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023