顺序遍历算法中二叉搜索树的时间分析

Question

下面是一个迭代算法，可以在不使用堆栈的情况下按顺序遍历二进制搜索树（首先是左子，然后是父，最后是右子）：

（想法：整个想法是找到树最左边的子节点，每次都找到手边节点的后续节点，并打印其值，直到不再剩下节点。）

void In-Order-Traverse(Node root){
     Min-Tree(root); //finding left-most child
     Node current = root;
  while (current != null){
     print-on-screen(current.key);
     current = Successor(current);
  }
  return;
}

Node Min-Tree(Node root){ // find the leftmost child
   Node current = root;
   while (current.leftChild != null)
      current = current.leftChild;
   return current;
}

Node Successor(Node root){
  if (root.rightChild != null) // if root has a right child ,find the leftmost child of the right sub-tree
    return Min-Tree(root.rightChild);
  else{
    current = root;
    while (current.parent != null && current.parent.leftChild != current)
        current = current.parent;
    return current.parrent;
  }
}

有人声称，假设BST中有n个节点，该算法的时间复杂度为θ（n），这肯定是正确的。然而，我无法说服自己，因为我猜一些节点的遍历次数超过了常数，这取决于它们的子树中的节点数量，并且总结所有这些访问次数不会导致时间复杂度达到θ（n）

关于如何证明这一点，有什么想法或直觉吗？

Answer 1

我们关注的是边而不是节点。（要有更好的直觉，请查看此图片：http://i.stack.imgur.com/WlK5O.png)

我们声称，在该算法中，每条边最多访问两次（实际上它正好访问了两次）；

第一次是向下，第二次是向上。要访问一个边缘两次以上，我们必须再次向下遍历该边缘：向下，向上，向下，......

我们证明了不可能有第二次边缘向下访问。

假设我们第二次向下遍历边（u， v），这意味着u的祖先之一有一个继承者，它是u的后代。

这是不可能的：

我们知道，当我们向上遍历一条边时，我们正在寻找一条左转边来找到一条后继边，所以当u位于后继边的左侧时，这个后继边的后继边位于它的右侧，通过移动到后继边的右侧（以找到其后继边），再次到达u，所以不可能再次到达边（u，v）。（为了找到继任者，我们要么向右移动，要么向上移动，但不要向左移动）

Answer 2

给定的程序在θ（N）时间内运行。θ（N）并不意味着每个节点都被访问过一次。请记住，有一个常数因子。所以θ（N）实际上可能被限制为5 N或10 N，甚至1000 N。因此，它并没有给你一个节点被访问的确切次数。

二叉搜索树的顺序迭代遍历的时间复杂度可以分析如下：，

考虑一个有N个节点的树，

让执行时间用复杂度函数T（N）表示。

让左子树和右子树分别包含X和N-X-1节点，

那么时间复杂度T（N）=T（X）T（N-X-1）c，

现在考虑BST的两个极端情况，

情况1：完全平衡的BST，即两个子树的节点数相等。例如，考虑如下所示的BST，

                        10
                       /  \
                      5   14
                     / \  / \
                    1  6 11 16 

对于这样的树，复杂性函数是，

T(N) = 2 T(⌊N/2⌋) + c

在这种情况下，主定理给出了Θ（N）的复杂性。

情况2：完全不平衡的BST，即左子树或右子树为空。对于X=0，存在。例如，考虑如下所示的BST，

               10
              /
             9
            /
           8
          /
         7    

现在，T（N）=T（0）T（N-1）c，

T(N) = T(N-1) + c
T(N) = T(N-2) + c + c
T(N) = T(N-3) + c + c + c
 .
 .
 .
T(N) = T(0) + N c

由于T（N）=K，其中K是常数，

T（N）=K N c

T（N）=Θ（N）。

因此，对于所有情况，复杂度为θ（N）。

Answer 3

用边而不是节点更容易推理。让我们根据继承者函数的代码进行推理。

案例1（然后分支）

对于具有右子节点的所有节点，我们将访问右子树一次（“右转”边缘），然后始终使用Min-Tree函数访问左子树（“左转”边缘）。我们可以证明这样的遍历将创建一条边缘唯一的路径-边缘不会在任何其他具有右子节点的遍历中重复，因为遍历确保您永远不会访问树上其他节点的任何“右转”边缘。（构造证明）。

案例2（elsebranch）

对于没有右子节点（else分支）的所有节点，我们将通过跟随“右转”边访问祖先，直到您必须做出“左转”边或遇到二叉树的根。同样，生成的路径中的边是唯一的-在没有正确子节点的任何其他节点进行的任何其他遍历中都不会重复。这是因为：

• 除了起始节点和跟随“左转”边到达的节点外，中间的所有其他节点都有一个右子节点（这意味着这些节点被排除在分支之外）。当然，起始节点没有正确的子节点
• 每个节点都有一个唯一的父节点（只有根节点没有父节点），父节点的路径是“左转”或“右转”（节点是左子节点或右子节点）。给定任何节点（忽略右子条件），只有一条路径可以创建模式：多个“右转”，然后是一个“左转”
• 由于中间的节点有一个正确的子节点，因此在从不同节点开始的2次遍历中不可能出现边。（因为我们目前正在考虑没有合适子节点的节点）

（这里的证据相当牵手，但我认为它可以通过矛盾得到正式证明）。

由于边是唯一的，因此仅在情况1（或仅在情况2）中遍历的总边数将为O（n）（因为树中的边数等于顶点数-1）。因此，将2种情况相加后，顺序遍历将为O（n）。

请注意，我只知道每个边最多访问一次——我不知道是否从证明中访问了所有边，但边的数量以顶点的数量为界，这是恰到好处的。

我们可以很容易地看到它也是ω（n）（每个节点访问一次），所以我们可以得出结论，它是θ（n）。