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

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

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

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

cf2117E

原题链接&#xff1a;https://codeforces.com/contest/2117/problem/E 题目背景&#xff1a; 给定两个数组a,b&#xff0c;可以执行多次以下操作&#xff1a;选择 i (1 < i < n - 1)&#xff0c;并设置 或&#xff0c;也可以在执行上述操作前执行一次删除任意 和 。求…...

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

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

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍

文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结&#xff1a; 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析&#xff1a; 实际业务去理解体会统一注…...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

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

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

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

浅谈不同二分算法的查找情况

二分算法原理比较简单&#xff0c;但是实际的算法模板却有很多&#xff0c;这一切都源于二分查找问题中的复杂情况和二分算法的边界处理&#xff0c;以下是博主对一些二分算法查找的情况分析。 需要说明的是&#xff0c;以下二分算法都是基于有序序列为升序有序的情况&#xf…...