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

C++基础之红黑树

 二叉搜索树

二叉搜索树(Binary Search Tree,BST)是一种二叉树,具有以下性质:

  1. 左子树节点值小于根节点值:对于树中的每个节点 x,其左子树中所有节点的值都小于 x 的值。
  2. 右子树节点值大于根节点值:对于树中的每个节点 x,其右子树中所有节点的值都大于 x 的值。
  3. 子树也是二叉搜索树:每个子树也是二叉搜索树。

红黑树(Red-Black Tree)是一种自平衡的,它在插入和删除节点时通过特定的规则来保持树的平衡,从而保证了基本的查找、插入和删除操作的时间复杂度都是 O(log⁡n)O(\log n)O(logn)。

特性概述:

  1. 节点颜色:每个节点要么是红色,要么是黑色。
  2. 根节点性质:根节点是黑色的。
  3. 叶子节点性质:叶子节点(NIL节点,空节点)是黑色的。
  4. 红色节点性质:红色节点的子节点必须是黑色的(即不存在两个连续的红色节点)。
  5. 任意节点到其每个叶子的路径包含相同数量的黑色节点:这个特性保证了树的黑色高度是相同的,也就是树的平衡性。

红黑树的操作:

  1. 插入操作

    • 新节点插入时,首先按照二叉搜索树的方式找到插入位置,并将节点标记为红色。
    • 根据红黑树性质,需要进行颜色调整和旋转操作,以确保满足红黑树的所有性质。
  2. 删除操作

    • 删除节点后,为了保持红黑树的性质,可能需要进行颜色调整和旋转操作。

红黑树的应用:

红黑树常被用作基础数据结构,例如在C++的STL中,std::mapstd::set 往往会基于红黑树实现,因为它能够高效支持插入、删除和查找操作,并且提供了有序性。

 

相关文章:

C++基础之红黑树

二叉搜索树 二叉搜索树(Binary Search Tree,BST)是一种二叉树,具有以下性质: 左子树节点值小于根节点值:对于树中的每个节点 x,其左子树中所有节点的值都小于 x 的值。右子树节点值大于根节点值…...

ClickHouse数据库对比、适用场景与入门指南

本文全面对比了ClickHouse与其他数据库(如StarRocks、HBase、MySQL、Hive、Elasticsearch等)的性能、功能、适用场景,并提供了ClickHouse的教学入门指南,旨在帮助读者选择合适的数据库产品并快速掌握ClickHouse的使用。 文章目录 …...

举例说明 如何通过SparkUI和日志定位任务莫名失败?

有一个Task OOM: 通过概览信息,发现Stage 10的Task 36失败了4次导致Job失败。概览信息中显示最后一次失败的退出代码(exit code)是143,意味着发生了内存溢出(OOM,即Out of Memory)。…...

Vue前端通过Axios的post方式传输数据,后端为什么一直接收的值是null?

沃靠!这个细节太细了,搞了我两个多小时才找到这个bug。 一、 首先官方文档给我的post请求的例子是这样的: axios.post(/user, {firstName: Fred,lastName: Flintstone}).then(function (response) {console.log(response);}).catch(function (error) {console.log(error);})…...

外链建设如何进行?

理解dofollow和nofollow链接,所谓dofollow链接,就是可以传递权重到你的网站的链接,这种链接对你的网站排名非常有帮助,这种链接可以推动你的网站在搜索结果中的位置向上爬,但一个网站全是这种有用的链接,反…...

深入理解Java正则表达式及其应用

正则表达式是一种强大的文本匹配和处理工具,可以在字符串中查找、替换、提取符合特定模式的内容。Java作为一种广泛应用的编程语言,提供了丰富的正则表达式支持。本文将深入探讨Java正则表达式的基本概念、语法以及常见应用场景,帮助读者全面…...

Gstreamer学习3----灌数据给管线之appsrc

参考资料 Basic tutorial 8: Short-cutting the pipeline gstreamer向appsrc发送帧画面的代码_gst appsrc可变帧率-CSDN博客 在官网教程Basic tutorial 8: Short-cutting the pipeline 里面,讲了一个例子,push音频数据给管线,视频的例子更…...

【深度学习量化交易1】一个金融小白尝试量化交易的设想、畅享和遐想

关注我的朋友们可能知道,我经常在信号处理的领域出没,时不时会发一些信号处理、深度学习科普向的文章。 不过算法研究久了,总想做一些更有趣的事情。 比如用深度学习算法赚大钱。。毕竟有什么事情能比暴富更有意思呢。 一、神经网络与彩票…...

【0基础学爬虫】爬虫基础之自动化工具 DrissionPage 的使用

概述 前三期文章中已经介绍到了 Selenium 与 Playwright 、Pyppeteer 的使用方法,它们的功能都非常强大。而本期要讲的 DrissionPage 更为独特,强大,而且使用更为方便,目前检测少,强烈推荐!!&a…...

c++_0基础_讲解7 练习

这一讲我为大家准备了几道题目,大家试着独自做一下(可能来自不同网站) 整数大小比较 - 洛谷 题目描述 输入两个整数,比较它们的大小。若 x>yx>y ,输出 > ;若 xyxy ,输出 &#xff…...

docker一些常用命令以及镜像构建完后部署到K8s上

docker一些常用命令以及镜像构建完后部署到K8s上 1.创建文件夹2.删除文件3.复制现有文件内容到新建文件4.打开某个文件5.查看文件列表6.解压文件(tar格式)7.解压镜像8.查看镜像9.删除镜像10.查看容器11.删除容器12.停止运行容器13.构建镜像14.启动容器15…...

在typora中利用正则表达式,批量处理图片

一,png格式 在 Typora 中批量将 HTML 图片标签转换为简化的 Markdown 图片链接,且忽略 alt 和 style 属性,可以按照以下步骤操作: 打开 Typora 并加载你的文档。按下 Ctrl H(在 Windows/Linux 上)或 Cmd…...

构建LangChain应用程序的示例代码:33、如何在LangChain框架中使用HumanInputChatModel来模拟人工输入的聊天模型教程

除了HumanInputLLM,LangChain还提供了一个伪聊天模型类,可以用于测试、调试或教育目的。这允许您模拟对聊天模型的调用,并模拟如果人类接收到这些消息会如何响应。 在这篇笔记中,我们将介绍如何使用这个模型。 我们首先在代理中…...

虚拟机使用桥接模式网络配置

1、获取本机的网络详细信息 windowr 输入cmd 使用ipconfig -all 一样即可 在自己的虚拟机中设置网络 虚拟机中的ip ---------192.168.36.*,不要跟自己的本机ip冲突 网关-----------192.168.36.254 一样即可 dns -----------一样即可,我多写了几个&am…...

韩顺平0基础学java——第24天

p484-508 System类 常见方法 System.arrycopy(src,0,dest,1,2); 表示从scr的第0个位置拷贝2个,放到目标数组索引为1的地方。 BigInteger和BigDecimal类 保存大整数和高精度浮点数 BigInte…...

leecode N皇后

深度优先遍历,然后回溯 思考得到的技巧: 1.先思考怎么用学过的数据结构解题 2.回溯不只需要知道最后一步,还需要知道之前所走的每一步 3. 棋盘的生成,.join([]),可以变列表为字符串 看题解得到的技巧: 1.妙啊&#xf…...

2024050802-重学 Java 设计模式《实战模板模式》

重学 Java 设计模式:实战模版模式「模拟爬虫各类电商商品,生成营销推广海报场景」 一、前言 黎明前的坚守,的住吗? 有人举过这样一个例子,先给你张北大的录取通知书,但要求你每天5点起床,12点…...

UNIAPP-ADB无线调试

ADB下载 SDK 平台工具版本说明 | Android Studio | Android Developers (google.cn) 环境变量配置 ADB版本查看 adb version 手机使用数据线连接到电脑 手机需要授权adb调试(开发人员选项里面) CMD输入命令 adb tcpip 5555 到了这一步你手机已经启动了adb服务了&…...

【stm32-新建工程】

stm32-新建工程 ■ 下载相关STM32Cube官方固件包(F1,F4,F7,H7)■ 1. ST官方搜索STM32Cube■ 2. 搜索 STM32Cube■ 3. 点击获取软件■ 4. 选择对应的版本下载■ 5. 输入账号信息■ 6. 出现下载弹框,等待下载…...

写点什么吧,作为STM32系列的开篇……

自从本科毕业后,就再也没碰过单片机…… 自从研究生毕业后,就再也没碰过硬件…… 自以为以前单片机玩的熟得很,特别是ATMEGA系列的AVR单片机,由于老师的推荐,本科时花了好多精力在这个系列单片机上面…… 本科时STM…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件: 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统,智慧工地全套源码,java版智慧工地源码,支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求,提供“平台网络终端”的整体解决方案,提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

ESP32读取DHT11温湿度数据

芯片:ESP32 环境:Arduino 一、安装DHT11传感器库 红框的库,别安装错了 二、代码 注意,DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架,支持"一次开发,多端部署",可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务,为旅游应用带来&#xf…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角,以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向,距离坐标原点x个像素;第二个是y坐标,表示当前位置为垂直方向,距离坐标原点y个像素。 坐标体系-像素 …...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一,概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本:2014.07; Kernel版本:Linux-3.10; 二,Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01),并让boo…...

tree 树组件大数据卡顿问题优化

问题背景 项目中有用到树组件用来做文件目录,但是由于这个树组件的节点越来越多,导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多,导致的浏览器卡顿,这里很明显就需要用到虚拟列表的技术&…...

大数据学习(132)-HIve数据分析

​​​​🍋🍋大数据学习🍋🍋 🔥系列专栏: 👑哲学语录: 用力所能及,改变世界。 💖如果觉得博主的文章还不错的话,请点赞👍收藏⭐️留言&#x1f4…...

Linux --进程控制

本文从以下五个方面来初步认识进程控制: 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程,创建出来的进程就是子进程,原来的进程为父进程。…...