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

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

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室(Algorithms, Machines, and People Lab)开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目,8个月后成为Apache顶级项目,速度之快足见过人之处&…...

MFC内存泄露

1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...

React Native在HarmonyOS 5.0阅读类应用开发中的实践

一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强,React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 (1)使用React Native…...

CMake控制VS2022项目文件分组

我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...

蓝桥杯3498 01串的熵

问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798&#xff0c; 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...

九天毕昇深度学习平台 | 如何安装库?

pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子&#xff1a; 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...

华为OD机考-机房布局

import java.util.*;public class DemoTest5 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseSystem.out.println(solve(in.nextLine()));}}priv…...

go 里面的指针

指针 在 Go 中&#xff0c;指针&#xff08;pointer&#xff09;是一个变量的内存地址&#xff0c;就像 C 语言那样&#xff1a; a : 10 p : &a // p 是一个指向 a 的指针 fmt.Println(*p) // 输出 10&#xff0c;通过指针解引用• &a 表示获取变量 a 的地址 p 表示…...

【安全篇】金刚不坏之身:整合 Spring Security + JWT 实现无状态认证与授权

摘要 本文是《Spring Boot 实战派》系列的第四篇。我们将直面所有 Web 应用都无法回避的核心问题&#xff1a;安全。文章将详细阐述认证&#xff08;Authentication) 与授权&#xff08;Authorization的核心概念&#xff0c;对比传统 Session-Cookie 与现代 JWT&#xff08;JS…...