当前位置: 首页 > 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…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

Zustand 状态管理库:极简而强大的解决方案

Zustand 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多&#xff0c;如何一步解决&#xff0c;采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集&#xff08;每个目录代表一个类别&#xff0c;目录下是该类别的所有图片&#xff09;&#xff0c;你需要进行以下配置步骤&#x…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术&#xff0c;它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton)&#xff1a;由层级结构的骨头组成&#xff0c;类似于人体骨骼蒙皮 (Mesh Skinning)&#xff1a;将模型网格顶点绑定到骨骼上&#xff0c;使骨骼移动…...

Spring AI与Spring Modulith核心技术解析

Spring AI核心架构解析 Spring AI&#xff08;https://spring.io/projects/spring-ai&#xff09;作为Spring生态中的AI集成框架&#xff0c;其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似&#xff0c;但特别为多语…...

Netty从入门到进阶(二)

二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架&#xff0c;用于…...

DingDing机器人群消息推送

文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人&#xff0c;点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置&#xff0c;详见说明文档 成功后&#xff0c;记录Webhook 2 API文档说明 点击设置说明 查看自…...

Spring Security 认证流程——补充

一、认证流程概述 Spring Security 的认证流程基于 过滤器链&#xff08;Filter Chain&#xff09;&#xff0c;核心组件包括 UsernamePasswordAuthenticationFilter、AuthenticationManager、UserDetailsService 等。整个流程可分为以下步骤&#xff1a; 用户提交登录请求拦…...