0

所以我基本上有函数avl？运行在 O(n^2) 中，这是因为每次我递归时，我都在调用高度，它是 O(n) 函数（其中 n 是树中的节点数）。

(define (height t)
  (cond
    [(empty? t) 0]
    [else (+ 1 (max (height (BST-left t)) (height (BST-right t))))]))

(define (avl? t)
  (cond
    [(empty? t) #t]
    [else (and (avl? (BST-left t))
               (avl? (BST-right t))
               (>= 1 (abs (- (height (BST-left t))
                             (height (BST-right t))))))]))

我的问题是我想做avl？在 O(n) 时间内运行。我得到了提示：“无论你应用多大的 BST，你都应该尽量限制在恒定时间内调用你的高度函数。这样，​​你可以获得 O(n) 的运行时间。” ......我不知道如何让我的身高在恒定时间内运行。有什么建议让我做avl吗？在 O(n) 而不是 O(n^2) 中运行？

4

2 回答 2

1

如果不允许将高度存储在树中，则可以通过使用告诉您树的高度以及它是否是 AVL 树的工作函数来避免重新计算它。然后每个节点都被查看一次，你就有了一个 O(n) 算法。然后从忘记工人结果的高度部分的包装器中调用工人。您当然应该走捷径，因此如果确定某个子树违反了平衡条件，请不要再检查任何子树、返回#f和虚假高度。

于 2012-03-08T20:16:18.707 回答
0

另一种选择是将高度存储在每个节点中，其中值表示以该节点为根的子树的高度。显然，使用这种方法返回子树的高度将是一个 O(1) 操作。

这意味着，只要树的结构发生变化，所有修改树的操作（插入、删除等）都必须使高度保持最新。

于 2012-03-08T20:35:12.580 回答