众所周知,从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树是多少?
发布于 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)中的根旋转。显然,这个序列还在继续。
如果计算树中的节点数,则匹配我的原始语句并完成证明。
(在下面的树中,移除高亮显示的节点将导致新的最大旋转次数。)
发布于 2012-12-12 21:49:25
我不擅长证明,我相信下面的文章充满了漏洞,但也许它会引发一些积极的东西。
要在删除节点后对最小化的AVL树进行k次旋转,必须满足以下条件:
最小化树的高度和节点数是用以下公式计算的。
H(k) = 2k + 1,k>0
N(0) =0 N(1) =1 N(h) = N(h-1) + N(h-2) + 1,h>1
F(k) = N(H(k))
(例如:)
k = 1, H(k) = 4, N(4) = 7
k = 2, H(k) = 6, N(6) = 20
证据(如它是)
最小高度
删除操作只能导致包含4个或更多节点的树进行轮换。
删除时发生1次旋转的最小子树是4个节点,其高度为3。删除短边中的节点将导致旋转。同样,删除根节点,使用短边的节点作为替换,将导致旋转。树是如何配置的并不重要:
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的平衡树。
.
/ \
. .
要实现第二次旋转,目标树必须具有高度为4的同级树,以便根的平衡因子为+/-1 (因此高度为5)。受影响的树是在父树的右侧还是左侧并不重要,兄弟树的布局也不重要(即H4的H3子级可以在左侧或右侧,并且可以是上述4个方向中的任何一个,而H2子级可以是2个可能的方向中的任何一个-这需要证明)。
_._ _._
/ \ / \
(H4) . . (H4)
/ \ / \
. . . .
\ \
. .
很明显,第三次旋转要求受影响树的祖父母同样不平衡+/-1,第四次旋转要求曾祖父母不平衡+/-1,以此类推。
根据定义,子树的高度是每个分支的最大高度加上根的最大高度。一个同级必须比另一个同级高1,才能实现根中的+/-1不平衡。
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.
最小节点数
N(0) =0 N(1) =1 //两个子树的节点数加上根N(h) = N(h-1) + N(h-2) + 1
推论
从下面的树中删除A,并观察到高度在旋转后没有变化。因此,父级中的平衡系数不会改变,也不会发生额外的旋转。
B B D
/ \ \ / \
A D => D => B E
/ \ / \ \
C E C E C
然而,在k=2的情况下,如果H(4)在这里最小化并不重要-第二次旋转仍然会发生。
_._ _._
/ \ / \
(H4) . . (H4)
/ \ / \
. . . .
\ \
. .
问题
https://stackoverflow.com/questions/13367981
复制相似问题