algorithm - 证明/说明算法的时间复杂度为O(h+k)

Question

证明/解释给定算法的时间复杂度为O(h+k)。其中 h 是树的高度，k 是 x 和 y(含)范围内的节点数。

我知道，如果 k=0(范围内没有任何项目)，那么算法会简单地遍历树的高度，因此 O(h)。我也知道一个节点是否在它对它的两个 child 而不是其中一个 child 重复出现的范围内。但这似乎有双重效果，所以我对如何证明/解释这一点感到困惑。

INRANGE-TREE-WALK (v, x, y)
  if v != NIL
    if v.key < x
      INRANGE-TREE-WALK(v.right, x, y)
    else if v.key 〈= y
      print v.key
      INRANGE-TREE-WALK (v.left, x, y)
      INRANGE-TREE-WALK (v.right, x, y)
    else
      INRANGE-TREE-WALK(v.left, x, y)

Answer 1

我假设这棵树是一棵二叉搜索树。

您可以查看调用该函数的当前节点的深度，然后注意对于任何给定的深度，访问的深度不会超过一个节点 v v.key < x .

虽然这可能会在不同的深度发生多次，但声称在树中的相同深度，这种情况永远不会发生超过一次。

暂时假设这个声明是错误的，并且在树中的一个特定深度 d 算法访问两个节点 a 和 b，它发现 a.key < x 和 b.key < x 。我们还选择 a 和 b 使得 a.key <= b.key ，即 a 在 b 的左边。

首先，请注意访问 a 和 b 的唯一方法是首先访问这些节点的共同祖先 p，因为我们有 x <= p.key <= y 。否则没有办法沿着树下的两个不同的 Twig 走。

但由于这是一棵二叉搜索树，p 右子树中的所有节点 v 的值都为 v.key >= P.key，因此为 v.key >= x。对于节点 b 也是如此。但这与 b.key < x 的前提相矛盾。

所以，我们有证据表明该函数不会被同一级别的两个节点调用，并且它们都有 v.key < x。因此，在整个算法的执行过程中，该条件只能找到 h 次。

对于 v.key > y 的情况也可以得出相同的结论。

x <= p.key <= y 有多少次为真？由于该算法永远不会访问同一个节点两次(因为它只访问任何已访问节点的子节点)，因此此条件为真的次数等于 k。

保持 v == NIL 的次数。这永远不会超过访问节点数加一。

将所有这些加在一起，我们得到了不超过 2(2h + k)+1 的单个函数调用的数量，并且假设执行一个函数调用 -排除递归调用 -- 是常数，我们得到 O(h+k) 的时间复杂度。