在BST中找到k个继任者的时间复杂性 [英] Time complexity of finding k successors in BST

问题描述

给出一个高度为 h 的二进制搜索树（BST），它将花费 O（k + h） BST InOrder后继算法 k 次

伪代码：

  get_kth_successor（node）：
次= 1到k：
 node =后继者（node）
返回节点
  

如何证明这种时间复杂性？

特别是，我试图在 k 与访问的节点数之间建立关系，但在这里找不到任何模式。

解决方案

采用关于继承人遍历的以下事实：

1. 您最多可以遍历分支两次：向下和向上。 / p>




2. 分支的每次两次访问都对应于找到至少一个后继者：当您向上通过分支回溯时，您将访问至少一个后继者




3. 您第一次遍历同一分支的次数仅一次 不能超过 2h 。当您从树的左下角的叶子开始，并且必须一直向上到达根（后继），然后再次下降到下叶以找到根的后继时，会发生这种最坏的情况。但是，如果之后需要更多继任者，则必须再次访问其中一些分支（回溯），然后才能第一次遍历其他分支。因此，您遍历一次的分支总数不能超过 2h 。

因此，要找到 k 后继者，您将最多遍历 k 分支两次（向下和向上，请参见第2点），而 2h 分支一次（第3点），这归结为最差的分支遍历- 2k + 2h 的计数，即 O（h + k）。

Given a binary search tree (BST) of height h, it would take O(k+h) time to apply the BST InOrder Successor algorithm k times in succession, starting in any node, applying each next call on the node that was returned by the previous call.

Pseudo code:

get_kth_successor(node):
    for times = 1 to k:
        node = successor(node)
    return node

How can I prove this time complexity?

In particular, I am trying to establish a relation between k and the number of nodes visited, but can't find any pattern here.

解决方案

Take the following truths concerning a successor(s) traversal:

1. You can traverse a branch not more than two times: downward and upward.

2. Every double visit of a branch corresponds to finding at least one more successor: when you backtrack via a branch upwards, you will have visited at least one successor more than at the time you passed that same branch the first time, in the downward direction.

3. The number of branches you will traverse only once cannot be more than 2h. This worst case happens when you start at a leaf in the bottom-left side of the tree and must go all the way up to the root (a successor) and then down again to a bottom-leaf to find the successor of the root. But if you need more successors after that, you will have to visit some of these branches again (in backtracking) before you can traverse other branches for the first time. So the total number of branches you traverse only once cannot increase above 2h.

So, to find k successors you will at the most traverse k branches twice (downward and upward, cf. point 2) and 2h branches once (point 3), which comes down to a worst case branch-traversal-count of 2k+2h which is O(h+k).

这篇关于在BST中找到k个继任者的时间复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！