4

下面是一个迭代算法，可以在不使用 Stack的情况下按顺序（首先left child，然后是parent，最后）遍历二叉搜索树：right 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)假设 BST 中有n节点，这肯定是正确的。但是我无法说服自己，因为我猜一些节点的遍历次数超过了常数，这取决于它们的子树中的节点数量，并且总结所有这些访问次数不会导致时间复杂度Theta(n)

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

4

3 回答 3

4

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

案例一（then分公司）

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

案例2（else分公司）

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

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

（这里的证明是相当随意的，但我认为它可以通过矛盾来正式证明）。

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

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

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

于 2013-04-19T02:45:39.673 回答
3

给定的程序在 Θ(N) 时间内运行。Θ(N) 并不意味着每个节点只被访问一次。请记住，有一个常数因素。所以 Θ(N) 实际上可能受到5 N或10 N甚至1000 N的限制。因此，它不能准确计算节点被访问的次数。

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

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

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

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

那么时间复杂度T(N) = T(X) + T(N-X-1) + c，

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

案例1： ABST是完全平衡的，即两棵子树的节点数相等。例如考虑下图所示的 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)适用于所有情况。

于 2013-04-19T01:53:30.357 回答
0

我们专注于边缘而不是节点。（为了更好地了解这张图片：http: //i.stack.imgur.com/WlK5O.png）

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

第一次向下遍历，第二次向上遍历。要访问一条边超过两次，我们必须再次向下遍历该边：向下，向上，向下，...。

我们证明不可能对边进行第二次向下访问。

假设我们edge (u , v)第二次向下遍历 ，这意味着 的祖先之一u有一个后继者u。

这是不可能的 ：

我们知道，当我们向上遍历一条边时，我们正在寻找一个左转边来寻找一个后继者，所以 whileu是在后继者的左边，这个后继者的后继者在它的右边，由移动到后继者的右侧（以找到其后继者）u再次到达并因此edge (u,v)再次是不可能的。（要找到继任者，我们要么向右移动，要么向上移动，但不向左移动）

于 2013-04-19T16:02:38.040 回答