1

二分探索木の有効性をチェックするためのさまざまな手法について考えていました。当然、維持する必要がある不変条件は、左側のサブツリーが現在のノード以下でなければならず、現在のノードは右側のサブツリー以下でなければならないということです。この問題に取り組むにはいくつかの方法があります: 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 に答える