当前位置: 首页 > news >正文

红 黑 树

文章目录

  • 一、红黑树的概念
  • 二、红黑树的实现
    • 1. 红黑树的存储结构
    • 2. 红黑树的插入

一、红黑树的概念

在 AVL 树中删除一个结点,旋转可能要持续到根结点,此时效率较低

红黑树也是一种二叉搜索树,通过在每个结点中增加一个位置来存储红色或黑色,并对结点的着色进行限制,使得该二叉搜索树的最长路径不超过最短路径的两倍,即红黑树是一颗近似平衡的二叉搜索树,他不像 AVL 树的平衡那么严格,所以红黑树在插入和删除时,也不需要大量的旋转,并且搜索效率差不了 AVL 多少

红黑树是一颗二叉搜索树并且满足如下规则:

  • 每个节点不是红色就是黑色
  • 根结点是黑色的
  • 每个红结点的左右孩子一定是黑色
  • 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点
  • 叶结点都是黑色的(这里的叶结点指的是空节点)

根据上述规则可以得到:最短路径:全黑结点的路径,最长路径:一黑一红的路径,所以红黑树可以保证最长路径不超过最短路径的一半

在这里插入图片描述

二、红黑树的实现

1. 红黑树的存储结构

// 结点的颜色
enum Color { RED, BLACK };// 红黑树的结点
template<class K, class V>
struct RBTreeNode
{std::pair<K, V> _kv;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Color _color;	// 结点的颜色RBTreeNode<K, V>(const std::pair<K, V>& kv = std::pair<K, V>(K(), V())): _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _color(RED)	// 为了方便树的结构调整,新结点默认为红色{}
};// 红黑树
template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:RBTree<K, V>(): _root(nullptr){}private:Node* _root;
};

2. 红黑树的插入

首先按照二叉搜索树的方式插入结点,保证插入结点之后还是二叉搜索树,为了方便树的结构调整,插入结点默认为为红色,当插入结点完成之后,可能会违反红黑树的性质,此时有三种情况

  • 插入结点的父节点是黑色:没有违反红黑树的性质

  • 插入结点的父节点是红色,叔节点存在且为红:违反了红黑树的性质,此时需要对父节点和爷爷结点进行变色

由于父节点是红色的,所以爷爷结点一定存在且为黑,变色完之后,如果 g 结点是根结点,则将 g 结点变为黑色,否则将 g 结点所在的子树当做新插入的结点,继续向上调整

在这里插入图片描述

  • 插入结点的父节点是红色,叔节点不存在或存在且为黑:违反了红黑树的性质,此时需要对爷爷结点所在的子树进行旋转然后再对结点进行变色

由于父节点是红色的,所以爷爷结点一定存在且为黑,变色完之后,子树的根结点是黑色的,不用继续向上调整

在这里插入图片描述

在这里插入图片描述

u 存在且为黑的情况,一定是由 u 存在且为红的情况继续向上调整而来的

// 右旋
void RotateR(Node* parent)
{Node* pparent = parent->_parent;Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR) subLR->_parent = parent;subL->_right = parent;parent->_parent = subL;if (pparent == nullptr) _root = subL;else{if (pparent->_left == parent) pparent->_left = subL;else pparent->_right = subL;}subL->_parent = pparent;
}// 左旋
void RotateL(Node* parent)
{Node* pparent = parent->_parent;Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL) subRL->_parent = parent;subR->_left = parent;parent->_parent = subR;if (pparent == nullptr) _root = subR;else{if (pparent->_left == parent) pparent->_left = subR;else pparent->_right = subR;}subR->_parent = pparent;
}// 插入
bool Insert(const std::pair<K, V>& kv)
{// 按照二叉搜索树的方式插入结点,保证该树插入结点之后还是二叉搜索树if (_root == nullptr){_root = new Node(kv);_root->_color = BLACK;return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else return false;}cur = new Node(kv);if (parent->_kv.first > kv.first) parent->_left = cur;else parent->_right = cur;cur->_parent = parent;// 更新颜色while (parent && parent->_color == RED){Node* grandfather = parent->_parent;if (grandfather->_left == parent){Node* uncle = grandfather->_right;// u 存在且为红// u 不存在或存在且为黑//		p 为 g 的左,cur 为 p 的左 右单旋//		p 为 g 的左,cur 为 p 的右 先左旋再右旋if (uncle && uncle->_color == RED){grandfather->_color = RED;parent->_color = BLACK;uncle->_color = BLACK;// 继续判断是否违反了红黑树的性质cur = grandfather;parent = grandfather->_parent;}else{if (parent->_left == cur){RotateR(grandfather);grandfather->_color = RED;parent->_color = BLACK;}else{RotateL(parent);RotateR(grandfather);grandfather->_color = RED;cur->_color = BLACK;}}}else{Node* uncle = grandfather->_left;// u 存在且为红// u 不存在或存在且为黑//		p 为 g 的右,cur 为 p 的右 左单旋//		p 为 g 的右,cur 为 p 的左 先右旋再左旋if (uncle && uncle->_color == RED){grandfather->_color = RED;parent->_color = BLACK;uncle->_color = BLACK;// 继续判断是否违反了红黑树的性质cur = grandfather;parent = grandfather->_parent;}else{if (parent->_right == cur){RotateL(grandfather);grandfather->_color = RED;parent->_color = BLACK;}else{RotateR(parent);RotateL(grandfather);grandfather->_color = RED;cur->_color = BLACK;}}}}_root->_color = BLACK;return true;
}

相关文章:

红 黑 树

文章目录 一、红黑树的概念二、红黑树的实现1. 红黑树的存储结构2. 红黑树的插入 一、红黑树的概念 在 AVL 树中删除一个结点&#xff0c;旋转可能要持续到根结点&#xff0c;此时效率较低 红黑树也是一种二叉搜索树&#xff0c;通过在每个结点中增加一个位置来存储红色或黑色…...

掷骰子的多线程应用程序1(复现《Qt C++6.0》)

说明&#xff1a;复现的代码来自《Qt C6.0》P496-P500。在复现时完全按照代码&#xff0c;出现了两处报错&#xff1a; &#xff08;1&#xff09;ui指针&#xff08;2&#xff09;按钮的响应函数。下面程序对以上问题进行了修改。除了图片、清空、关闭功能外&#xff0c;其他…...

【vue2第十八章】VueRouter 路由嵌套 与 keep-alive缓存组件(activated,deactivated)

VueRouter 路由嵌套 在使用vue开发中&#xff0c;可能会碰到使用多层级别的路由。比如&#xff1a; 其中就包含了两个主要页面&#xff0c;首页&#xff0c;详情&#xff0c;但是首页的下面又包含了列表&#xff0c;喜欢&#xff0c;收藏&#xff0c;我的四个子路由。 此时就…...

如何确保亚马逊、速卖通等平台测评补单的环境稳定性和安全性?

做亚马逊、速卖通等平台测评补单时&#xff0c;确保环境的安全性和稳定性是非常重要的。稳定的环境是测评的基础&#xff0c;如果无法解决安全性问题&#xff0c;那么测评就不值得进行。为了确保稳定的环境系统&#xff0c;需要考虑物理环境和IP环境两个方面。 首先&#xff0…...

echarts图表 实现高度按照 内容撑起来或者超出部分滚动展示效果

背景&#xff1a;因为数据不固定 高度写死导致数据显示不全&#xff0c;所以图表高度要根据内容计算 实现代码如下&#xff1a; <divv-if"showCharts"id"business-bars"class"chart":style"{ height: chartHeight px }"></d…...

【论文阅读】检索增强发展历程及相关文章总结

文章目录 前言Knn-LMInsightMethodResultsDomain AdaptionTuning Nearest Neighbor Search Analysis REALMInsightsMethodKnowledge RetrieverKnowledge-Augmented Encoder ExpResultAblation StudyCase Study DPRInsightMethodExperimentsResults RAGInsightRAG-Sequence Mode…...

【漏洞复现系列】二、weblogic-cve_2020_2883(RCE/反序列化)

Key words&#xff1a;T3协议&#xff0c;weblogic Server&#xff0c;反序列化 2.1、漏洞原理 ​cve_2020_2883 远程代码执行漏洞存在于 WebLogic Server 核心组件中,允许未经身份验证的攻击者通过 T3 协议网络访问并破坏易受攻击的 WebLogic Server&#xff0c;成功的漏洞利…...

算法通关村-----LRU的设计与实现

LRU 缓存 问题描述 请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类&#xff1a; LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存。int get(int key) 如果关键字 key 存在于缓存中&#xff0c;则返回关键字的值&…...

王江涛十天搞定考研词汇

学习目标&#xff1a; 考研词汇 学习内容&#xff1a; 2023-9-17 第一天考研词汇 学习时间&#xff1a; 开始:2023-9-17 结束:进行中 学习产出&#xff1a; 2023-9-17intellect智力&#xff1b;知识分子intellectual智力的&#xff1b;聪明的intellectualize使...理智化&a…...

算法(二)——数组章节和链表章节

数组章节 &#xff08;1&#xff09;二分查找 给定一个 n 个元素有序的&#xff08;升序&#xff09;整型数组 nums 和一个目标值 target &#xff0c;写一个函数搜索 nums 中的 target&#xff0c;如果目标值存在返回下标&#xff0c;否则返回 -1。 class Solution {public i…...

Android:ListView在Fragment中的使用

一、前言&#xff1a; 因为工作一直在用mvvm框架&#xff0c;因此这篇文章是基于mvvm框架写的。在Fragment复制之前一定要谨记项目可以跑起来。确保能跑起来之后直接复制就行。 二、代码展示&#xff1a; 页面布局 ?xml version"1.0" encoding"utf-8"…...

BIGEMAP在土地规划中的应用

工具 Bigemap gis office地图软件 BIGEMAP GIS Office-全能版 Bigemap APP_卫星地图APP_高清卫星地图APP 1.使用软件一般都用于套坐标&#xff0c;比如我们常见的&#xff08;kml shp CAD等土建规划图纸&#xff09;以及一些项目厂区红线&#xff0c;方便于项目选址和居民建…...

软件测试常见术语和名词解释

1. Unit testing (单元测试)&#xff1a;指一段代码的基本测试&#xff0c;其实际大小是未定的&#xff0c;通常是一个函数或子程序&#xff0c;一般由开发者执行。 2. Integration testing (集成测试)&#xff1a;被测试系统的所有组件都集成在一起&#xff0c;找出被测试系统…...

prometheus+process_exporter进程监控

一、需要监控进程的服务器上配置 1、进入到临时工作目录&#xff0c;传入process_exporter包 [root Nginx1 ~]# cd work/ [root Nginx1 work]# rz 2、解压&#xff0c;并移动至/usr/local/目录下 [root Nginx1 work]# tar xzf process-exporter-0.7.5.linux-amd64.tar.gz [root…...

四川玖璨电子商务有限公司专注抖音电商运营

四川玖璨电商是一个靠谱的抖音培训公司&#xff0c;在电商行业内有着广泛的知名度和良好的口碑。该公司通过多年的发展&#xff0c;形成了独特的运营理念和有效的运营策略&#xff0c;为商家提供了一站式的抖音电商运营服务。 首先&#xff0c;四川玖璨电子商务有限公司注重与…...

python LeetCode 刷题记录 83

题目 给定一个已排序的链表的头 head &#xff0c; 删除所有重复的元素&#xff0c;使每个元素只出现一次 。返回 已排序的链表 。 代码 class Solution:def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:if head:# 判断非空链表current he…...

Grom 如何解决 SQL 注入问题

什么是 SQL 注入 SQL 注入是一种常见的数据库攻击手段&#xff0c; SQL 注入漏洞也是网络世界中最普遍的漏洞之一。 SQL 注入就是恶意用户通过在表单中填写包含 SQL 关键字的数据来使数据库执行非常规代码的过程。 这个问题的来源就是&#xff0c; SQL 数据库的操作是通过 SQ…...

腾讯mini项目-【指标监控服务重构】2023-07-19

今日已办 OpenTelemetry Logs 通过日志记录 API 支持日志收集 集成现有的日志记录库和日志收集工具 Overview 日志记录 API - Logging API&#xff0c;允许您检测应用程序并生成结构化日志旨在与其他 telemerty data&#xff08;例如metric和trace&#xff09;配合使用&am…...

抖音矩阵系统源代码开发部署--SaaS开源技术开发文档

一、概述 抖音SEO矩阵系统源代码是一套针对抖音平台的搜索引擎优化工具&#xff0c;它可以帮助用户提高抖音视频在搜索结果中的排名&#xff0c;增加曝光率和流量。本开发文档旨在提供系统的功能框架、技术要求和开发示例&#xff0c;以便开发者进行二次开发和优化。 二、功能…...

CLIP模型资料学习

clip资料 links https://blog.csdn.net/wzk4869/article/details/129680734?ops_request_misc&request_id&biz_id102&utm_termCLIP&utm_mediumdistribute.pc_search_result.none-task-blog-2allsobaiduweb~default-4-129680734.142v94insert_down1&spm10…...

OpenLayers 可视化之热力图

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 热力图&#xff08;Heatmap&#xff09;又叫热点图&#xff0c;是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15

缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下&#xff1a; struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

在四层代理中还原真实客户端ngx_stream_realip_module

一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡&#xff08;如 HAProxy、AWS NLB、阿里 SLB&#xff09;发起上游连接时&#xff0c;将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后&#xff0c;ngx_stream_realip_module 从中提取原始信息…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

【AI学习】三、AI算法中的向量

在人工智能&#xff08;AI&#xff09;算法中&#xff0c;向量&#xff08;Vector&#xff09;是一种将现实世界中的数据&#xff08;如图像、文本、音频等&#xff09;转化为计算机可处理的数值型特征表示的工具。它是连接人类认知&#xff08;如语义、视觉特征&#xff09;与…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多Java框架中如Spring和Hiberna…...