BST中寻找k后继子的时间复杂度

Question

给定一个高度为h的二叉查找树（BST），它需要O（k h）时间来连续应用BST Inorder后续算法k次，从任何节点开始，在先前调用返回的节点上应用每个下一个调用。

伪代码：

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

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

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

Answer 1

下面是一个非常简单的算法。

创建一个空堆栈S和一个变量curr=NULL。

• 找到树中的起始节点。此外，将它的所有祖先（以及节点本身）推送到堆栈S
• 现在从堆栈S中弹出一个节点top并检查curr是否是它的正确子节点。如果它没有对它的正确子树进行无序遍历
  • 如果我们在遍历时找到k个或更多节点，我们就完成了

  总体时间完整性为O（h k）。第1步需要O（h）时间。第2步需要O（h k）时间（第2步的所有迭代合并需要O（h k）时间。）！

Answer 2

采取以下有关后续遍历的事实：

>

可以遍历分支不超过两次：向下和向上。

每次重复访问一个分支对应于找到至少一个后续分支：当您通过分支向上回溯时，您将访问至少一个后续分支，比您第一次通过该分支时，在向下的方向上访问了至少一个后续分支。

只遍历一次的分支数量不能超过2h。最坏的情况发生在您从树左下角的一片叶子开始，必须一直向上到根（继任者），然后再次向下到底部叶子以找到根的继任者。但是如果之后您需要更多的继任者，您将不得不再次访问其中的一些分支（回溯），然后才能第一次遍历其他分支。因此，您只遍历一次的分支总数不能超过2h。

因此，要找到k个后续分支，您最多将遍历k个分支两次（向下和向上，参见第2点）和2h个分支一次（第3点），这可以归结为最坏情况下的分支遍历计数2k 2h，即O（h k）。

Answer 3

我将为这个问题编写完整的实现，以便于证明我关于所花时间的论点。

.

假设BST的每个节点都具有以下结构：

typedef struct node{
    int vale;
    struct node* left;
    struct node* right;
}node;

该算法将有两个步骤：

a、 从树的根节点开始，找到起始节点和该节点的所有祖先。将所有这些存储在传递的堆栈中：

//root -> root node of the tree.
//val  -> value of the node to find.
// s   -> stack to store all ancestor.
node* find_node(node* root, int val,std::stack<node*> &s)
{
    if(root != NULL)  s.push(root);
    if(root == NULL || root->value == val) return root;
    if(root->value > val) return find_node(root->left);
    else return find_node(root->right);


}

并且对该方法的调用如下所示：

//Assuming that the root is the root node of the tree.
std::stack<node*> s;
node* ptr = find_node(root,s); // we have all ancestors of ptr along with ptr in stack s now.

湾。现在我们必须打印树的下k个直接大（比ptr）的元素。我们将从节点（即ptr）开始：

// s  -> stack of all ancestor of the node.
// k  -> k-successor to find.
void print_k_bigger(stack<node*> s, int k)
{
    //since the top element of stack is the starting node. So we won't print it.
    // We will just pop the first node and perform inorder traversal on its right child.
    prev = s.top();
    s.pop();
    inorder(prev->right,k);

    // Now all the nodes present in the stack are ancestor of the node. 
    while(!s.empty() && k>0)
    {
        //pop the node at the top of stack.
        ptr = s.top();
        s.pop();

        //if the node popped previously (prev) was the right child of the current 
        //node, i.e. prev was bigger than the current node. So we will have to go 
        //one more level up to search for successors. 
        if(prev == ptr->right) continue;

        //else the current node is immidiate bigger than prev node. Print it.
        printf("%d",ptr->value);

        //reduce the count.
        k--;

        //inorder the right subtree of the current node.
        inorder(ptr->right);

        //Note this.
        prev = ptr;

    }

}

以下是我们的顺序：

void inorder(node* ptr, int& k)
{
    if(ptr != NULL)
    {
        inorder(ptr->left,k);
        printf("%d",ptr->value);
        k--;
        inorder(ptr->right,k);
    }
}

时间分析：

1. 查找节点的方法是O（h），因为它可以达到最大根到叶路径的长度
2. 方法print\u k\u bigger是O（hk），因为在循环的每次迭代中，堆栈的大小都在减小，或者k的值在减小。请注意，当从while循环内部调用inorder（）时，不会增加额外的开销，因为对inorder（）的所有调用都将以最大值O（k）进行