Loading [MathJax]/jax/output/CommonHTML/config.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
社区首页 >问答首页 >当删除操作导致2次旋转时,最小的AVL树大小是多少?

当删除操作导致2次旋转时,最小的AVL树大小是多少?
EN

Stack Overflow用户
提问于 2012-11-13 20:10:40
回答 2查看 6.8K关注 0票数 6

众所周知,从AVL树中删除可能导致几个节点最终不平衡。我的问题是,需要2次旋转的最小AVL树大小是多少(我假设左-右或右-左旋转是1次旋转)?我目前有一个包含12个节点的AVL树,其中删除会导致2次旋转。我的AVL树按如下顺序插入:

8,5,9,3,6,11,2,4,7,10,12,1。

如果删除10,9将变得不平衡并发生旋转。在这样做的过程中,8变得不平衡,并发生另一次旋转。有没有更小的树,在删除后需要2次旋转?

在阅读了jpalecek的评论后,我真正的问题是:给定一些常数k,在1次删除后有k次旋转的最小大小的AVL树是多少?

EN

回答 2

Stack Overflow用户

发布于 2012-12-26 01:08:15

在最坏的情况下,一棵有四个节点的树需要一次旋转。最坏情况下删除的数量随着列表中的每一项而增加: 4,12,33,88,232,609,1596,4180,10945,28656,...

这是Sloane's A027941,是一个斐波那契类型的序列,可以用N(i)=1+N(i-1)+N(i-2)i>=2, N(1)=2, N(0)=1生成。

要了解为什么会这样,首先要注意的是,旋转不平衡的AVL树会将其高度降低1,因为它的短腿是以牺牲它的长腿为代价的。

当从AVL树中删除节点时,AVL算法将检查已删除节点的所有祖先,以进行潜在的重新平衡。因此,为了回答您的问题,我们需要识别具有给定高度的最小节点数的树。

在这样的树中,每个节点要么是叶子,要么具有+1或-1的平衡因子:如果节点的平衡因子为零,这将意味着可以在不触发重新平衡的情况下删除节点。我们知道再平衡会使树变短。

下面,我展示了一组最坏情况树。您可以看到,在序列中的前两棵树之后,每棵树都是通过连接前两棵树来构建的。您还可以看到,每个树中的每个节点要么是叶子,要么具有非零的平衡因子。因此,每棵树都有其节点数的最大高度。

对于每棵树,在最坏的情况下,删除左子树将导致旋转,最终将该子树的高度减少1。这将整个树作为一个整体进行平衡。另一方面,从右子树中删除节点可能最终导致树的不平衡,从而导致根的旋转。因此,正确的子树是最重要的。

在最坏的情况下,您可以验证Tree (c)和Tree (d)在删除时是否有一次旋转。

树(c)在树(e)中显示为右子树,树(d)在树(f)中显示为右子树。当在树(c)或(d)中触发旋转时,这会缩短树,从而导致树(d)和(f)中的根旋转。显然,这个序列还在继续。

如果计算树中的节点数,则匹配我的原始语句并完成证明。

(在下面的树中,移除高亮显示的节点将导致新的最大旋转次数。)

票数 5
EN

Stack Overflow用户

发布于 2012-12-12 21:49:25

我不擅长证明,我相信下面的文章充满了漏洞,但也许它会引发一些积极的东西。

要在删除节点后对最小化的AVL树进行k次旋转,必须满足以下条件:

  • 目标节点必须存在于包含4个节点的子树中。
  • 目标节点必须位于短分支上,或者必须是子树的根并替换为短分支的叶。
  • 目标子树根的祖先中的每个节点必须稍微失衡(平衡系数为+/-1)。也就是说,当遇到平衡因子0时,旋转链将停止。

最小化树的高度和节点数是用以下公式计算的。

  • 设H(k) =受k次旋转影响的树的最小高度。

H(k) = 2k + 1,k>0

  • 设N( h ) =高度为h的(最小节点) AVL树中的节点数。

N(0) =0 N(1) =1 N(h) = N(h-1) + N(h-2) + 1,h>1

  • 设F(k) =树中受k次旋转影响的最小节点数。

F(k) = N(H(k))

(例如:)

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
k = 1, H(k) = 4, N(4) = 7
k = 2, H(k) = 6, N(6) = 20

证据(如它是)

最小高度

删除操作只能导致包含4个或更多节点的树进行轮换。

  • 包含1个节点的树必须具有平衡因子0。
  • 包含2个节点的树必须具有平衡因子+/-1,删除操作将生成包含1个节点的平衡树。
  • 包含3个节点的树必须具有平衡因子0。删除节点会导致平衡因子为+/-1,并且没有旋转从少于4个节点的树中删除occurs.
  • Therefore,不会导致旋转。

删除时发生1次旋转的最小子树是4个节点,其高度为3。删除短边中的节点将导致旋转。同样,删除根节点,使用短边的节点作为替换,将导致旋转。树是如何配置的并不重要:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
  B        B     Removal of A or replacement of B with A               
 / \      / \    results in rotation. No rotation occurs
A   C    A   D   on removal of C or D, or on replacement 
     \      /    of B with C.
      D    C     

    C      C     Removal of D or replacement of C with D
   / \    / \    results in rotation. No rotation occurs
  B   D  A   D   on removal of A or B, or on replacement
 /        \      of C with B. 
A          B     

从4节点树中删除会得到高度为2的平衡树。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
  .
 / \
.   .

要实现第二次旋转,目标树必须具有高度为4的同级树,以便根的平衡因子为+/-1 (因此高度为5)。受影响的树是在父树的右侧还是左侧并不重要,兄弟树的布局也不重要(即H4的H3子级可以在左侧或右侧,并且可以是上述4个方向中的任何一个,而H2子级可以是2个可能的方向中的任何一个-这需要证明)。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
   _._              _._
  /   \            /   \
(H4)   .          .   (H4)
      / \        / \
     .   .      .   .
          \          \
           .          .

很明显,第三次旋转要求受影响树的祖父母同样不平衡+/-1,第四次旋转要求曾祖父母不平衡+/-1,以此类推。

根据定义,子树的高度是每个分支的最大高度加上根的最大高度。一个同级必须比另一个同级高1,才能实现根中的+/-1不平衡。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
H(1) = 3 (as observed above)
H(k) = 1 + max(H(k - 1), H(k - 1) + 1)) = 1 + H(k - 1) + 1 = H(k - 1) + 2
... Inductive proof leading to H(k) = 2k + 1 eludes me.

最小节点数

  • 根据定义,子树中的节点数是左分支中的节点数加上右分支中的节点数加上根的节点数。
  • 也是这样定义的,高度为0的树必须有0个节点,高度为1的树必须没有分支,因此有1个节点。
  • 如上所示,一个分支必须比另一个短。
  • 设N(h) =创建高度为h的树所需的最小节点数:

N(0) =0 N(1) =1 //两个子树的节点数加上根N(h) = N(h-1) + N(h-2) + 1

推论

  • 最小节点数不一定是大型树中的最大节点数。简而言之:

从下面的树中删除A,并观察到高度在旋转后没有变化。因此,父级中的平衡系数不会改变,也不会发生额外的旋转。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
  B          B           D
 / \          \         / \
A   D    =>    D   =>  B   E  
   / \        / \       \    
  C   E      C   E       C

然而,在k=2的情况下,如果H(4)在这里最小化并不重要-第二次旋转仍然会发生。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
   _._              _._
  /   \            /   \
(H4)   .          .   (H4)
      / \        / \
     .   .      .   .
          \          \
           .          .

问题

  • 目标子树的位置是什么?显然,对于k= 1,它是根,而对于k= 2,如果根的平衡因子为-1,则它是左边,否则是右边。有没有一个公式来确定k >= 3的位置?
  • 一棵树可以包含多少个最大节点来影响k个旋转?在祖先中是否可以有一个不旋转的中间节点,尽管它的父节点是?
票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/13367981

复制
相关文章
如何使用JavaScript从字符串中删除HTML标签?
我们可以使用以下示例从带有 JavaScript 的字符串中删除 HTML 标签 -
很酷的站长
2022/12/04
12.9K0
如何使用JavaScript从字符串中删除HTML标签?
如何删除 JavaScript 数组中的虚值[每日前端夜话0x55]
翻译:疯狂的技术宅 原文:https://medium.freecodecamp.org/how-to-remove-falsy-values-from-an-array-in-javascript-e623dbbd0ef2
疯狂的技术宅
2019/05/06
9.5K0
如何删除 JavaScript 数组中的虚值[每日前端夜话0x55]
Google JavaScript API 的使用
您可以使用JavaScript客户端库与Web应用程序中的Google API(例如,人物,日历和云端硬盘)进行交互。请按照此页面上的说明进行操作。
拿我格子衫来
2022/01/24
3K0
ABAP 字段隐藏的方法
正文部分 ​ *数据库表spfli相关 TABLES: spfli, sflight. START-OF-SELECTION. SKIP. *输出 ULINE AT /(91). WRITE: / sy-vline,(15) '航线承运人', sy-vline , (15) '航班连接', sy-vline, (15) '国家代码', sy-vline,(15) '起飞城市', sy-vline, (15) '起飞机场',sy-vline. ULINE A
matinal
2020/11/27
1K0
HTML中的javascript交互
在Android开发中,越来越多的商业项目使用了Android原生控件与WebView进行混合开发,当然不仅仅就是显示一个WebView那么简单,有时候还需要本地Java代码与HTML中的javascript进行交互,Android也对交互做了很好的封装,所以很容易实现例如:点击网页中的按钮Android调用原生对话框,点击网页中的电话号码调用Android拨号APP。这篇给大家介绍下如何实现Android与HTML+JS的交互。 有的人可能不理解什么是javascript,可以简单理解为它在HTML中
xiangzhihong
2018/02/01
4K0
HTML中的javascript交互
如何使用 Python 隐藏图像中的数据
秘密数据可以是任何格式的数据,如文本甚至文件。简而言之,隐写术的主要目的是隐藏任何文件(通常是图像、音频或视频)中的预期信息,而不实际改变文件的外观,即文件外观看起来和以前一样。
小白学视觉
2022/02/14
4K0
如何使用 Python 隐藏图像中的数据
JavaScript值延迟脚本和异步脚本
Html 4.0为<script>标签定义了defer属性,这个属性的用途是表名脚本在执行时,不会影响页面的构造。也就是说,脚本会延迟到整个页面解析完毕之后在运行,因此,在<script>元素中设置defer属性,相当于告诉浏览器立即下载,但延迟执行。但是有一种特殊情况,看如下代码: <html xmlns="http://www.w3.org/1999/xhtml"> <head> <meta http-equiv="Content-Type" content="text/html; charse
郑小超.
2018/01/24
8320
如何在 JavaScript 中处理 HTML 事件?
在Web开发中,JavaScript是一种常用的脚本语言,用于增强网页的交互性和动态性。HTML事件是用户与网页交互时发生的动作,如点击、鼠标移动、键盘输入等。本文将介绍如何在JavaScript中处理HTML事件,以实现更丰富的用户体验和交互功能。
海拥
2023/06/27
2820
如何在 JavaScript 中处理 HTML 事件?
隐藏在网站 CSS 中的窃密脚本
在过去的两年里,网络犯罪分子使用了各种各样的方法来在网上商城的各个地方隐藏针对Credit Card的信息窃取代码,以防止被安全检测方案所发现,而这些信息窃取代码也被称之为Web Skimmer或Magecart脚本。
FB客服
2021/01/25
8280
隐藏在网站 CSS 中的窃密脚本
shell脚本 从自定义的值中随机抽取+不重复
日期:2018/6/12 介绍:从数组里随机抽一个,但不会重复,相比之下python比较好做出效果
陈不成i
2021/06/24
3.3K0
Python脚本之根据excel统计表中字段值的缺失率实用案例
有时候,我们需要去连接数据库,然后统计下目标库表字段的值有多少个空值,并且计算出它的缺失率:
数据仓库践行者
2021/12/06
2.7K0
Python脚本之根据excel统计表中字段值的缺失率实用案例
从javascript脚本混淆说起
脚本病毒是一个一直以来就存在,且长期活跃着的一种与PE病毒完全不同的一类病毒类型,其制作的门槛低、混淆加密方式的千变万化,容易传播、容易躲避检测,不为广大网民熟知等诸多特性,都深深吸引着各色各样的恶意软件制作者 … 小到一个不起眼的lnk快捷方式,大到一个word文档,都是脚本的载体。本文主要以 js脚本为例(特指JScript,下同 ),具体结合实际样本,讲述混淆方式及其混淆类型检测相关知识,文章受限于样本个数及其种类,存在一定的局限性,但大致情况应当不会相差太大。本系列首先会对jscript及其脚本进行
FB客服
2018/02/28
1.5K0
从javascript脚本混淆说起
如何处理数据库表字段值中的特殊字符?
现网业务运行过程中,可能会遇到数据库表字段值包含特殊字符的场景,此场景虽然不常见,但只要一出现,其影响却往往是致命的,且排查难度较高,非常有必要了解一下。
披头
2020/11/20
4.8K0
问与答98:如何根据单元格中的值动态隐藏指定的行?
Q:我有一个工作表,在单元格B1中输入有数值,我想根据这个数值动态隐藏行2至行100。具体地说,就是在工作表中放置一个命令按钮,如果单元格B1中的数值是10时,当我单击这个命令按钮时,会显示前10行,即第2行至第11行;再次单击该按钮后,隐藏全部的行,即第2行至第100行;再单击该按钮,则又会显示第2行至第11行,又单击该按钮,隐藏第2行至第100行……也就是说,通过单击该按钮,重复显示第2行至第11行与隐藏第2行至第100行的操作。如图1所示。
fanjy
2021/03/12
6.4K0
EasyGBS平台如何更改token值的时效性?
EasyGBS国标视频云服务可支持通过国标GB28181协议将设备接入,实现视频的实时监控直播、录像、语音对讲、云存储、告警等功能,同时也支持将接入的视频流进行全终端、全平台分发,分发的视频流包括RTSP、RTMP、FLV、HLS、WebRTC等格式。平台部署简单,无需插件就能实现web浏览器播放,也支持手机浏览器、微信、PC等各种终端的无插件播放。
TSINGSEE青犀视频
2022/05/12
2.6K0
JAVASCRIPT 如何创建SEARCH字段
matinal
2023/10/14
1820
javascript html转换成markdown,如何使用Turndown使用JavaScript将HTML转换为Markdown[通俗易懂]
许多项目不是从定义的结构开始, 而是随着时间的流逝而变化。例如, 一个基本博客可能从一开始就使用HTML格式将其内容存储在数据库中, 但是由于其简单性, 总有一天某人可能希望开始使用Markdown而不是HTML, 在这种情况下, 你需要从一种格式转换为另一种格式。如果你将服务器端逻辑与JavaScript(Node.js)一起使用, 甚至直接在浏览器中将HTML转换为编辑器中的Markdown, 则可以使用Turndown库轻松地完成此类任务, HTML到用JavaScript编写的Markdown转换器。
全栈程序员站长
2022/10/04
4K0
点击加载更多

相似问题

在linux机器上运行jar时UnauthorizedAccessException

20

GSON:运行jar文件时的MalformedJsonException (在Eclipse中工作正常)

20

在不同的机器/PC上运行jar文件

13

无法运行以前工作正常的.jar文件

11

Java JAR文件在本地机器上运行,而在其他机器上缺少文件

13
添加站长 进交流群

领取专属 10元无门槛券

AI混元助手 在线答疑

扫码加入开发者社群
关注 腾讯云开发者公众号

洞察 腾讯核心技术

剖析业界实践案例

扫码关注腾讯云开发者公众号
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
查看详情【社区公告】 技术创作特训营有奖征文