6

任意の 2 つのノードが交換される二分探索木が与えられます。そのため、これら 2 つのノードを見つけて元に戻す必要があります (データではなくノードを交換する必要があります)。

ツリーを順番にトラバーサルし、各ノードへのポインターを保存する追加の配列を作成することで、これを実行しようとしました。次に、配列をトラバースして、ソートされていない 2 つのノードを見つけます。これらの 2 つのノードがツリー内で検索され、スワップされます。

だから私の質問は、O(1) 空間でこの問題を解決する方法ですか?

4

3 に答える 3

7

BST を 順番にトラバーサルすると、順序付けされた要素をトラバーサルできます。
インオーダー トラバーサルを使用して、2 つの場違いな要素を見つけ (それらを 2 つのポインターに格納)、元に戻すことができます。

このメソッドは、実際には作成せずに、その場で説明した配列を実際に作成しています。

ただし、スペース消費量は ではなくO(1)、はスタック トレースによるツリーの高さであるO(h)ことに注意してください。hツリーのバランスが取れている場合、次のようになります。O(logn)

于 2012-08-06T08:40:44.193 に答える
0

以下のように isBST() メソッドを変更して、ランダムに交換された 2 つのノードを交換し、修正することができます。

/* Returns true if the given tree is a binary search tree
 (efficient version). */
int isBST(struct node* node)
{
  struct node *x = NULL;
  return(isBSTUtil(node, INT_MIN, INT_MAX,&x));
}

/* Returns true if the given tree is a BST and its
   values are >= min and <= max. */
int isBSTUtil(struct node* node, int min, int max, struct node **x)
{

  /* an empty tree is BST */
  if (node==NULL)
     return 1;

  /* false if this node violates the min/max constraint */
  if (node->data < min || node->data > max) {
     if (*x == NULL) {
        *x = node;//same the first incident where BST property is not followed.
     }
     else {
        //here we second node, so swap it with *x.
        int tmp = node->data;
        node->data = (*x)->data;
        (*x)->data = tmp;

     }
     //return 0;
     return 1;//have to return 1; as we are not checking here if tree is BST, as we know it is not BST, and we are correcting it.
  }
  /* otherwise check the subtrees recursively,
   tightening the min or max constraint */
  return
    isBSTUtil(node->left, min, node->data-1, x) &&  // Allow only distinct values
    isBSTUtil(node->right, node->data+1, max, x);  // Allow only distinct values
}
于 2016-01-02T21:22:31.923 に答える
0

BST によっては、これは O(1) で実行できます。

たとえば、ツリーのノードに親へのポインタがある場合、ウィキペディアの Tree_traversal ページの nonRecrusiveInOrderTraversal セクションで説明されている実装を使用できます。

別の可能性として、BST がノード間のポインターではなく 1 次元配列として格納されている場合は、配列を単純にたどることができます (そして、各ノードの親と子を決定するために計算を行います)。

トラバーサル/ウォークを実行中に、現在の要素が正しい場所にあるかどうかを確認します。

そうでない場合は、ツリー内のどこにあるべきかを確認し、その場所の要素と交換できます。(ルートが間違った場所にある場合は注意してください)。

于 2012-08-07T01:13:06.463 に答える