如何生成尽可能不平衡的AVL树？

Question

我在一些论文中看到了这一点,并且有人认为当我们删除AVL树的节点时,最多可以有log(n)次旋转.我相信我们可以通过生成尽可能不平衡的AVL树来实现这一目标.问题是如何做到这一点.这对于研究去除旋转物有很大帮助.非常感谢!

Answer 1

如果你想制作一个最大的不平衡的AVL树,你正在寻找一个Fibonacci树,它被归纳定义如下:

• 0阶的Fibonacci树是空的.
• 1阶的Fibonacci树是单个节点.
• n + 2阶的Fibonacci树是一个节点,其左子节点是n阶的Fibonacci树,右子节点是n + 1阶的Fibonacci树.

例如,这是一个5阶斐波那契树:

Fibonacci树表示AVL树可以具有的最大偏斜量,因为如果平衡因子更加不平衡,则每个节点的平衡因子将超过AVL树所放置的限制.

您可以使用此定义非常容易地生成最大的不平衡AVL树:

function FibonacciTree(int order) {
    if order = 0, return the empty tree.
    if order = 1, create a single node and return it.
    otherwise:
        let left  = FibonacciTree(order - 2)
        let right = FibonacciTree(order - 1)
        return a tree whose left child is "left" and whose right child is "right."

希望这可以帮助!