5

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

4

1 回答 1

9

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

  • 0 阶斐波那契树是空的。
  • 1 阶斐波那契树是单个节点。
  • n + 2 阶斐波那契树是一个节点,其左孩子是 n 阶斐波那契树,其右孩子是 n + 1 阶斐波那契树。

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

在此处输入图像描述

斐波那契树表示 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."

希望这可以帮助!

于 2012-01-25T05:05:59.657 回答