1

我正在考虑检查二叉搜索树有效性的不同技术。自然，需要维护的不变量是左子树必须小于或等于当前节点，而当前节点又应小于或等于右子树。有几种不同的方法可以解决这个问题：第一种是检查每个子树上值的约束，可以像这样概述（在 Java 中，对于整数节点）：

public static boolean isBST(TreeNode node, int lower, int higher){

   if(node == null) return true;
   else if(node.data < lower || node.data > higher) return false;
   return isBST(node.left, lower, node.data) && isBST(node.right, node.data, higher);
}

还有另一种方法可以使用 inOrder 遍历来完成此操作，您可以在其中跟踪前一个元素并确保进程严格不递减。这两种方法都先探索左子树，如果我们在根的右子树中间出现不一致，推荐的路径是什么？我知道可以使用 BFS 变体，但是否可以同时使用多种技术，是否推荐？例如，我们可以对一个 BFS、一个 inorder 和一个 reverseInorder 并在检测到故障的那一刻返回。这可能只适用于非常大的树，以便以更多空间和访问相同数据结构的多个线程为代价来减少平均运行时间。当然，如果我们'

4

2 回答 2

0

那么迭代加深深度优先搜索呢？

它通常（渐近地）与广度优先搜索一样快（并且还发现任何早期失败），但使用的内存与深度优先搜索一样少。

它通常看起来像这样：

boolean isBST(TreeNode node, int lower, int higher, int depth)
{
  if (depth == 0)
    return true;
  ...
  isBST(..., depth-1)
  ...
}

呼叫者：

boolean failed = false;
int treeHeight = height(root);
for (int depth = 2; depth <= treeHeight && !failed; depth++)
  failed = !isBST(root, -INFINITY, INFINITY, depth);
于 2013-10-27T21:15:35.360 回答
0

我希望这取决于您的具体情况。特别是，您的树无法成为二元树的概率是多少，以及发生故障的预期深度。

例如，如果树很可能是正确的二叉树，那么使用 3 多种技术将是浪费的，因为有效树的整体运行时间将大致增加三倍。

于 2013-10-27T19:22:19.287 回答