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

【数据结构】平衡树引入

数据结构-平衡树


前置知识
  • 二叉树
  • 二叉树的中序遍历

问题

维护一个数据结构,支持插入元素、删除元素、查询元素的排名、查询排名对应的元素、查询元素的前驱、查询元素的后继等。

BST(二叉搜索树)

作为一个基本无效(很容易卡掉)的数据结构,将其放在这里讲可能更为合适。。。
BST 的思想,来自于二叉树的 DFS 序。
设想一下,若一个二叉树的中序遍历正好递增,也就是说,始终有 左儿子 ≤ 根 ≤ 右儿子 左儿子\le根\le右儿子 左儿子右儿子,那么不就可以达到 O ( 树高 ) O(\text{树高}) O(树高) 的复杂度了吗?
可能不是这样。设想一组数据,令插入的第 i i i 个节点为 i i i,BST 便会退化为 O ( n 2 ) O(n^2) O(n2),长这样:

思路

为了弥补 BST 的各种劣势,聪明的 OIers 发明了平衡树。
对于上面卡掉 BST 的样例,平衡树的一种画法长这样:

可以看出来,平衡树是非常平衡的。
平衡树的重要处理就是维护其平衡性。
接下来介绍一下用来维护平衡树的平衡性质的两种操作——左旋( Zag \text{Zag} Zag)和右旋( Zig \text{Zig} Zig

  • Zag \text{Zag} Zag
    如果有一个失衡子树长这样:

    需要将节点 q \text q q 旋转至节点 p \text p p,我们可以这样:

    注意到,其中序遍历是不变的。
  • Zig \text{Zig} Zig
    如果有一个失衡子树长这样:

    需要将节点 q \text q q 旋转至节点 p \text p p,我们可以这样:

    注意到,其中序遍历是不变的。

由于不同的平衡树对失衡子树的处理方式是不同的,所以这里不再赘述,可以去下方的文章学习。


数据结构参数
  • 单次修改时间复杂度: Θ ( log ⁡ n ) \Theta(\log n) Θ(logn)
  • 单次查询时间复杂度: Θ ( log ⁡ n ) \Theta(\log n) Θ(logn)
  • 空间复杂度: Θ ( n ) \Theta(n) Θ(n)

接下来是三种基本的平衡树:

  • AVL
  • Treap
  • Splay

相关文章:

【数据结构】平衡树引入

数据结构-平衡树 前置知识 二叉树二叉树的中序遍历 问题 维护一个数据结构,支持插入元素、删除元素、查询元素的排名、查询排名对应的元素、查询元素的前驱、查询元素的后继等。 BST(二叉搜索树) 作为一个基本无效(很容易卡掉…...

机器视觉相机镜头光源选型

镜头选型工具 - HiTools - 海康威视 Hikvisionhttps://www.hikvision.com/cn/support/tools/hitools/cl8a9de13648c56d7f/ 海康机器人-机器视觉产品页杭州海康机器人股份有限公司海康机器人HIKROBOT是面向全球的机器视觉和移动机器人产品及解决方案提供商,业务聚焦于…...

Appium:iOS测试比Android测试更难?

iOS测试与Android测试: Appium 是一个开源的自动化测试框架,用于iOS、Android和Web应用程序。它允许开发者使用自己的语言来编写测试脚本,并且可以运行在多种平台上。 就Appium本身而言,它为iOS和Android提供了相似的测试能力和…...

使用c#罗列、监视、控制进程

个人简介:本人多年从事研发和测试领域工作,有一定的经验; 口号:懒人推动科技进步,学习编程啊脚本啊目的就是要将人从做相同的工作脱离出来,手懒可以但是脑子不能懒,让重复的事情自动完成,能动一下就完成任务就不能动两下,懒到极致才是目标! 方向:本人不怎么将理论的…...

Vue:绘制图例

本文记录使用Vue框架绘制图例的代码片段。 可以嵌入到cesium视图中,也可以直接绘制到自己的原生系统中。 一、绘制图例Vue组件 <div v-for="(color, index) in colors" :key="index" class="legend-item"><div class="color-…...

Web(8)SQL注入

Web网站&#xff08;对外门户&#xff09; 原理&#xff1a;not>and>or(优先级) 一.低级注入 order by的作用是对字段进行排序&#xff0c;如order by 5&#xff0c;根据第五个字段 进行排序&#xff0c;如果一共有4个字段&#xff0c;输入order by 5系统就会报错不 …...

kafka入门(三):kafka多线程消费

kafka消费积压 如果生产者发送消息的速度过快&#xff0c;或者是消费者处理消息的速度太慢&#xff0c;那么就会有越来越多的消息无法及时消费&#xff0c;也就是消费积压。 消费积压时&#xff0c; (1) 可以增加Topic的分区数&#xff0c;并且增加消费组的消费者数量&#…...

android通过广播打印RAM信息

通过广播打印ram相关log 参数说明&#xff1a; 广播&#xff1a;com.android.settings.action.RAM_INFO int型参数index&#xff1a;0 - 3h, 1 - 6h, 2 - 12h, 3 - 24h 代表过去时间app使用ram情况&#xff08;平均/最大占用&#xff09; Index: frameworks/base/services/cor…...

C++新经典模板与泛型编程:策略类模板

策略类模板 在前面的博文中&#xff0c;策略类SumPolicy和MinPolicy都是普通的类&#xff0c;其中包含的是一个静态成员函数模板algorithm()&#xff0c;该函数模板包含两个类型模板参数。其实&#xff0c;也可以把SumPolicy和MinPolicy类写成类模板—直接把algorithm()中的两…...

微信小程序引入Vant Weapp修改样式不起作用,使用外部样式类进行覆盖

一、引入Vant Weapp后样式问题 在项目中使用第三方组件修改css样式时,总是出现各种各样问题,修改的css样式不起作用,没有效果,效果不符合预期等。 栗子(引入一个搜索框组件)实现效果: 左侧有一个搜索文字背景为蓝色,接着跟一个搜索框 wxml <view class"container&q…...

python核酸检测 青少年电子学会等级考试 中小学生python编程等级考试二级真题答案解析2022年6月

目录 python核酸检测 一、题目要求 1、编程实现 2、输入输出...

搭建React项目,基于Vite+React+TS+ESLint+Prettier+Husky+Commitlint

基于ViteReactTSESLintPrettierHuskyCommitlint搭建React项目 node: 20.10.0 一、创建项目 安装包管理器pnpm npm i pnpm -g基于Vite创建项目 pnpm create vitelatest web-gis-react --template react-ts进入项目目录安装依赖 $ cd web-gis-react $ pnpm i启动项目 $ pnpm…...

ChatGPT在国内的使用限制,国内的ChatGPT替代工具

人工智能技术的发展不仅改变了我们的生活方式&#xff0c;也在各行各业发挥着越来越重要的作用。ChatGPT&#xff08;Generative Pre-trained Transformer&#xff09;作为一种先进的自然语言处理模型&#xff0c;由OpenAI推出&#xff0c;其在生成人类般流畅对话方面表现出色。…...

服务器如何保证数据安全_Maizyun

服务器如何保证数据安全 在当今的数字化时代&#xff0c;数据安全已经成为企业和社会组织必须面对的重要问题。服务器作为存储和处理大量数据的核心组件&#xff0c;必须采取有效的措施来确保数据的安全。本文将探讨服务器如何保证数据安全。 一、访问控制和身份认证 访问控…...

sql2005日志文件过大如何清理

由于安装的时候没有计划好空间&#xff0c;默认装在系统盘&#xff0c;而且又没有做自动备份、截断事务日志等&#xff0c;很快LDF文件就达到十几G&#xff0c;或者几十G &#xff0c;此时就不得不处理了。 备份和计划就不说了&#xff0c;现在就说下怎么把它先删除吧&#xf…...

Linux--学习记录(2)

解压命令&#xff1a; gzip命令&#xff1a; 参数&#xff1a; -k&#xff1a;待压缩的文件会保留下来&#xff0c;生成一个新的压缩文件-d&#xff1a;解压压缩文件语法&#xff1a; gzip -k pathname(待压缩的文件夹名)gzip -kd name.gz&#xff08;待解压的压缩包名&#x…...

字符串函数`strlen`、`strcpy`、`strcmp`、`strstr`、`strcat`的使用以及模拟实现

文章目录 &#x1f680;前言&#x1f680;库函数strlen✈️strlen的模拟实现 &#x1f680;库函数strcpy✈️strcpy的模拟实现 &#x1f680;strcmp✈️strcmp的模拟实现 &#x1f680;strstr✈️strstr的模拟实现 &#x1f680;strcat✈️strcat的模拟实现 &#x1f680;前言 …...

插入排序与希尔排序(C语言实现)

1.插入排序 由上面的动图可以知道插入排序的逻辑就是从第一个元素开始往后遍历&#xff0c;如果找到比前一个元素小的&#xff08;或者大的&#xff09;就往前排&#xff0c;所以插入排序的每一次遍历都会保证前面的数据是有序的&#xff0c;接下类用代码进行讲解。 我们这里传…...

【微软技术栈】与其他.NET语言的互操作性 (C++/CLI)

本文内容 使用 C# 索引器实现 C# 的 is 和 as 关键字实现 C# 的 lock 关键字 本节中的主题介绍如何在 Visual C 中创建程序集&#xff0c;这些程序集使用或提供以 C# 或 Visual Basic 编写的程序集的功能。 1、使用 C# 索引器 Visual C 不包含索引器&#xff1b;它具有索引…...

TCPUDP使用场景讨论

将链路从TCP改为UDP会对通信链路产生以下影响和注意事项&#xff1a; 可靠性&#xff1a;UDP是无连接的协议&#xff0c;与TCP相比&#xff0c;它不提供可靠性保证和重传机制。因此&#xff0c;当将链路从TCP改为UDP时&#xff0c;通信的可靠性会降低。如果在通信过程中丢失了U…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?

编辑&#xff1a;陈萍萍的公主一点人工一点智能 未来机器人的大脑&#xff1a;如何用神经网络模拟器实现更智能的决策&#xff1f;RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战&#xff0c;在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

<6>-MySQL表的增删查改

目录 一&#xff0c;create&#xff08;创建表&#xff09; 二&#xff0c;retrieve&#xff08;查询表&#xff09; 1&#xff0c;select列 2&#xff0c;where条件 三&#xff0c;update&#xff08;更新表&#xff09; 四&#xff0c;delete&#xff08;删除表&#xf…...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)

目录 1.TCP的连接管理机制&#xff08;1&#xff09;三次握手①握手过程②对握手过程的理解 &#xff08;2&#xff09;四次挥手&#xff08;3&#xff09;握手和挥手的触发&#xff08;4&#xff09;状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)

更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...

Java 加密常用的各种算法及其选择

在数字化时代&#xff0c;数据安全至关重要&#xff0c;Java 作为广泛应用的编程语言&#xff0c;提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景&#xff0c;有助于开发者在不同的业务需求中做出正确的选择。​ 一、对称加密算法…...

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...

Java入门学习详细版(一)

大家好&#xff0c;Java 学习是一个系统学习的过程&#xff0c;核心原则就是“理论 实践 坚持”&#xff0c;并且需循序渐进&#xff0c;不可过于着急&#xff0c;本篇文章推出的这份详细入门学习资料将带大家从零基础开始&#xff0c;逐步掌握 Java 的核心概念和编程技能。 …...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用

1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...

代理篇12|深入理解 Vite中的Proxy接口代理配置

在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...

安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)

船舶制造装配管理现状&#xff1a;装配工作依赖人工经验&#xff0c;装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书&#xff0c;但在实际执行中&#xff0c;工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...