AVL树不是重量平衡吗？

Question

在上一个 问题 重量平衡的树木有一个定义，以及关于红黑树的问题。

这个问题是要提出相同的问题，但是 AVL树.

问题是，给定$ mu $ $ $平衡的树的定义，就像另一个问题一样

是否有一些$ mu gt 0 $，以便所有足够大的AVL树均为$ mu $ - 平衡？

我认为只有一个对AVL树的定义，没有歧义。

Answer 1

宣称: ：不，没有这样的$ mu $。

证明: ：我们给出了不断增长的AVL树的无限序列，其重量平衡价值往往$ 0 $，这与索赔相矛盾。

令$ c_h $ $ h $的完整树;它具有$ 2^{h+1} -1 $节点。

令$ s_h $ 斐波那契树 高度$ h $;它具有$ f_ {h+2} -1 $节点。 [[1,2,taocp 3]

现在，让$（t_h）_ {i geq 1} $ with $ t_h = n（s_h，c_h）$我们声称是反示例的树的序列。

考虑$ t_h $的重量平衡值，对于某些$ h in mathbb {n} _+$：

美元frac {2^{h+1}}} {f_ {h+2}}} - frac {1} {f_ {h+2}}}}}}}}}}}} sim sim frac {f_ {f_ {h+2}}} {2^{h+1}}} ＆= frac { frac {1} { sqrt {5}}}（ phi^{h+2} - hat { phi} { phi}^{h+2} ）} {2^{h+1}} sim sim frac { phi^{h+2}}} { sqrt {5} cdot 2^{h+1}}}} infty} { to} 0 end {align*} $

这是证明的结论。

符号:

• $ f_n $是$ n $ th 斐波那契号
• $ phi 大约1.6 $是 黄金比率, ，$ hat { phi} 大约-0.62 $它的共轭。
• $ f sim g $表示$ f $和$ g $在渐近上相等，即$ lim_ {n to infty} frac {f（n）} {g（n）} = 1 $。

Nota Bene: ：斐波那契树正是那些具有给定高度最小节点的AVL树（或等效地，给定数量的节点的最大高度）。

附录: ：如果我们没有听到教授提到它们，我们该如何提出斐波那契树？好吧，高度$ h $的AVL树将是什么样的节点？当然，您需要一个根。其中一个子树需要具有高度$ H-1 $，我们必须尽可能少的节点选择它。另一个可以具有高度$ h-2 $而不会违反高度平衡条件，我们也可以选择尽可能少的节点。从本质上讲，我们递归地建造了想要的树木！这是前四个：

^[资源]

我们在$ h $：$ h $的构造树中的节点$ f（h）$进行了复发：

$ qquad displaystyle begin {align*} f（1）＆= 1 f（2）＆= 2 f（h） qquad n geq 3 end {align*} $

求解它会导致$ f（h）= f_ {h+2} -1 $，我们上面使用了。

---

在 二进制搜索树有限平衡 Nievergelt and Reingold（1972）。