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

复制
相关文章
npm与nvm的冲突处理
node本身包含一个npm,后来本人通过它安装nvm来管理npm版本,长期以来一直相安无事,再后来在终端使用中莫名其妙出现一个奇怪问题——无论在独立终端,还是vscode的集成终端,输入以下命令都能打印一样结果:
IT晴天
2019/05/14
1.3K0
处理 WebView 与 ViewPager 滑动冲突
问题场景 在项目的App中,有一个ViewPager,它内部包含了WebView,而内部的webview加载了一个可以滑动的网页。
技术小黑屋
2020/02/10
2.1K0
ElasticSearch 冲突问题处理
当我们使用 index API 更新文档 ,可以一次性读取原始文档,做我们的修改,然后重新检索整个文档。最近的检索请求将获胜:无论最后哪一个文档被检索,都将被唯一存储在 Elasticsearch 中。如果其他人同时更改这个文档,他们的更改将丢失。
用户9615083
2022/12/25
6370
ElasticSearch 冲突问题处理
冲突和谈判的处理原则
----------------------------------------------------------------------------
PM吃瓜
2023/03/02
1940
冲突和谈判的处理原则
逻辑删除与联合索引冲突处理
然后今天跟朋友探讨了下,决定使用datetime作为逻辑删除字段的类型,如果未删除,则字段为魔法值的固定时间,已删除,则设为删除时的时间
阿超
2022/08/17
6490
逻辑删除与联合索引冲突处理
Git 处理文件与 Revison 冲突问题
有一次,尝试使用git log 来查看某个分支(build.gradle)的历史提交时,遇到了这样的问题
技术小黑屋
2021/04/26
6790
多主复制下处理写冲突(1)-同步与异步冲突检测及避免冲突
如两个用户同时编辑wiki,如图-7。用户1将页面标题从A-》B,且用户2同时将标题从A-》C。每个用户的更改都成功提交到本地主节点。但当异步复制到对方时,发现存在冲突。正常的主从复制则不会出现此问题。
JavaEdge
2022/08/01
1K0
多主复制下处理写冲突(1)-同步与异步冲突检测及避免冲突
git 通过 SublimeMerge 处理冲突
在使用 Git 的时候,如果是多个小伙伴开发,那么如果同时修改一个文件将出现冲突。也就是在自动合并的时候不知道使用哪个代码才对,此时就需要合并工具的协助。我找了很久发现 SublimeMerge 是界面最好看的,同时快捷键和 SublimeText 一样多也好用的工具
林德熙
2019/06/15
1.2K0
Golang Dep 依赖冲突处理
对于 Golang 应用内存堆栈的监控,基本都是读取 runtime.MemStats,然后发往一些 TSDB 进行可视化展示。代码一般都是这样的:
poslua
2019/08/19
1.3K0
git 通过 SublimeMerge 处理冲突
在使用 Git 的时候,如果是多个小伙伴开发,那么如果同时修改一个文件将出现冲突。也就是在自动合并的时候不知道使用哪个代码才对,此时就需要合并工具的协助。我找了很久发现 SublimeMerge 是界面最好看的,同时快捷键和 SublimeText 一样多也好用的工具
林德熙
2022/08/04
4690
逻辑删除与联合索引冲突处理(二)
一星陨落,黯淡不了星空灿烂;一花凋零,荒芜不了整个春天。——巴尔扎克 之前写过一篇,用时间实现,今天提供另一种思路 我们的逻辑删除字段,如果和联合唯一索引同时使用,还可以使用下面这一种方式: 如果未删除,使用魔法值 如果已删除,使用NULL 因为mybatisPlus官方文档也提到了: 字段类型支持说明: 支持所有数据类型(推荐使用 Integer,Boolean,LocalDateTime) 如果数据库字段使用datetime,逻辑未删除值和已删除值支持配置为字符串null,另一个值支持配置
阿超
2022/08/17
4840
逻辑删除与联合索引冲突处理(二)
浅谈NPM怎样处理处理依赖和冲突
其实我们都知道早期版本的的 npm (v2) 管理模块依赖的方式并不复杂。它读取每个模块的依赖列表,并下载匹配版本的依赖模块到该模块目录内的 node_modules 文件夹下;如果该依赖又依赖了其他的模块,会继续下载该依赖的依赖到该模块目录的 node_modules 文件夹下——如此递归执行下去,最终形成一颗庞大的依赖树。
前端老道
2022/03/28
3.9K0
对Bitmap的内存优化
在Android应用里,最耗费内存的就是图片资源。而且在Android系统中,读取位图Bitmap时,分给虚拟机中的图片的堆栈大小只有8M,如果超出了,就会出现OutOfMemory异常。所以,对于图片的内存优化,是Android应用开发中比较重要的内容。 1) 要及时回收Bitmap的内存 Bitmap类有一个方法recycle(),从方法名可以看出意思是回收。这里就有疑问了,Android系统有自己的垃圾回收机制,可以不定期的回收掉不使用的内存空间,当然也包括Bitmap的空间。那为什么还需要这个
xiangzhihong
2018/01/30
1.4K0
结构体的大小与内存对其
最近在群里看到了有人问起结构体的大小问题,好多人的都不太明白。因此写篇文章总结一下。顺便再提一下结构体本身。
zy010101
2019/05/25
7810
处理视觉冲突 | 手势导航 (二)
我们将在近期为大家带来一个关于 "手势导航" 的系列连载,本文是连载的第二篇,如果您希望了解其他手势导航的话题,请持续关注我们。
Android 开发者
2019/11/29
2.8K0
Redis字典的实现方式和冲突处理
Redis的哈希表是一个数组,数组的每个元素都是一个指向哈希表节点的指针。每个哈希表节点包含一个键和值的对,同时还有指向下一个节点的指针,从而形成一个链表。
一凡sir
2023/09/16
3330
Redis字典的实现方式和冲突处理
insert into...on duplicate key冲突处理
这两天工作和生活上的事情都比较多,工作上要赶好几个OKR任务,搞得节奏有点乱,生活上这几天搬了新家,每天回家都自己做饭吃,再加上打扫房间的卫生,稍微搞一搞就九点十点了,时间变的很紧。今天写文章的时间又比较晚了,就写点简单的内容吧。
AsiaYe
2020/06/11
1.6K0
View的滑动冲突的分析和处理实践
文中有用到 Scroller 来实现弹性滑动,不了解的可以先看下 View的滑动实现方式。
103style
2022/12/19
5170
View的滑动冲突的分析和处理实践
如何处理工作与生活之间的冲突?
移动互联网让我们随时随地”在线“,工作时间与生活时间越来越模糊。尤其是程序员这类随时可能都需要解决线上问题的工作。
石云升
2022/08/25
3320
【精简版】git分支融合与冲突处理
其他可能用上的命令: 撤销merge状态: git merge --abort
devi
2021/08/19
1.3K0

相似问题

内存库向量处理器中内存访问冲突的条件

13

内存访问冲突

33

处理任务中的libvlcsharp对象的内存访问冲突

16

未处理的异常错误,内存冲突

21

SIGSEGV内存访问冲突

26
添加站长 进交流群

领取专属 10元无门槛券

AI混元助手 在线答疑

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

洞察 腾讯核心技术

剖析业界实践案例

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