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

Question

下面是一个迭代算法，用于按顺序遍历二叉搜索树(首先是 left child，然后是 parent，最后是 right child)，而不使用堆栈:

(思路:整个思路就是找到一棵树最左边的 child ，每次都找到手头节点的后继节点，打印它的值，直到没有节点为止。)

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;
  }
}

据称该算法的时间复杂度为Theta(n)假设有n BST 中的节点，这肯定是正确的。但是我无法说服自己，因为我猜某些节点被遍历的次数超过固定次数，这取决于它们的子树中的节点数量，并且将所有这些访问次数加起来不会导致时间复杂度为 Theta(n)。

关于如何证明它的任何想法或直觉？

Answer 1

用边比节点更容易推理。让我们根据Successor函数的代码进行推理。

案例一(then分支)

对于所有有右 child 的节点，我们将访问一次右子树(“右转”边)，然后总是访问左子树(“左转”边)Min-Tree功能。我们可以证明，这样的遍历将创建一条边唯一的路径——在从任何其他具有右 child 的节点进行的任何遍历中，边都不会重复，因为遍历确保您永远不会访问任何“右转”边树上的其他节点。 (构造证明)。

案例二(else分支)

对于所有没有右 child 的节点(else 分支)，我们将沿着“右转”边访问祖先，直到你必须做出“左转”边或遇到二叉树的根。同样，生成的路径中的边是唯一的——在从没有右 child 的任何其他节点进行的任何其他遍历中永远不会重复。这是因为:

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

(这里的证明很简单，但我认为可以用反证法形式化地证明)。

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

请注意，我只知道每条边最多被访问一次——我不知道是否从证明中访问了所有边，但边的数量受顶点数量的限制，这是正确的。

我们很容易看出它也是Omega(n)(每个节点被访问一次)，因此我们可以得出结论它是Theta(n)。