1

インタビューでこんな質問をされました。私は、すべてのサブツリーを見つけて、それらのいずれかが bst であるかどうかを確認するという素朴なアプローチから答えを始めました。その過程で、これまでに見た max bst のサイズを記録します。

これよりも良いアプローチはありますか？

4

5 に答える 5

4

これを行うとどうなりますか：

  1. グラフの重みを逆にする
  2. このように Kruskal アルゴリズムを使用します。

を。エッジのセットから最も重み付けされたエッジを選択します。

b. そのエッジを追加しても bst 制約が壊れない場合にのみ、ツリーを作成します。

c. エッジ セットからそのエッジを削除します。

いくつかのツリーになる可能性があるため (bst 制約が満たされないときにエッジを破棄すると、元のグラフが切断される可能性があるため)、より多くのノードを持つツリーを選択するだけです。

于 2012-08-30T00:40:04.947 に答える
2

私はあなたの解決策を次のように考えています：

for each subtree of the tree:
    if the subtree is a binary search tree:
        compute its size
        if it is the largest one found so far:
            best = subtree
return best

サブツリーごとに O(n) の作業を行い、最大 n 個のサブツリーがあるため、これは非効率的です。

ツリー全体を 1 回だけ歩くことで、より良い結果を得ることができます。

// Walk the subtree at node. Find the largest subtree that is a binary search tree
// and return that tree in *result. Also return that subtree's size and the range
// of values it covers in *size, *min, and *max.
void
walk(Node *node, Node **result, size_t *size, Value *min, Value *max)
{
    Node *result0 = NULL;
    size_t size0 = 0;
    Value min0, max0;
    if (node->left)
        walk(node->left, &result0, &size0, &min0, &max0);

    Node *result1 = NULL;
    size_t size1 = 0;
    Value min1, max1;
    if (node->right)
        walk(node->right, &result1, &size1, &min1, &max1);

    // If both subtrees are search trees and node->value falls between them,
    // then node is a search tree.
    if (result0 == node->left
        && result1 == node->right
        && (node->left == NULL || max0 <= node->value)
        && (node->right == NULL || node->value <= min1))
    {
        *result = node;
        *size = size0 + 1 + size1;
        *min = node->left == NULL ? node->value : min0;
        *max = node->right == NULL ? node->value : max1;
    } else if (size0 >= size1) {
        *result = result0;
        *size = size0;
        *min = min0;
        *max = max0;
    } else {
        *result = result1;
        *size = size1;
        *min = min1;
        *max = max1;
    }
}

Node *
findLargestBinarySearchSubtree(Node *root)
{
    Node *result;
    size_t size;
    Value min, max;
    walk(root, &result, &size, &min, &max);
    return result;
}
于 2012-08-30T00:25:23.067 に答える
1

このWeb サイトは、この問題を以下でカバーしているようです: Binary Search Tree Checking。具体的には、C++ でのソリューションの抜粋を次に示します。

/*   
 Returns true if the given tree is a binary search tree 
 (efficient version). 
*/ 
int isBST2(struct node* node) { 
  return(isBSTUtil(node, INT_MIN, INT_MAX)); 
}
/* 
 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) { 
  if (node==NULL) return(true);

  // false if this node violates the min/max constraint 
  if (node->data<min || node->data>max) return(false);

  // otherwise check the subtrees recursively, 
  // tightening the min or max constraint 
  return 
    isBSTUtil(node->left, min, node->data) && 
    isBSTUtil(node->right, node->data+1, max) 
  ); 
}
于 2012-08-30T00:08:12.343 に答える
1

解決すべき複雑さは O(n) あると思います。

bool is_bst(node * cur)
{
   if (cur == NULL)
     return true;

   // if calculated before cur vertex.
   if (hash_set_bst[cur] != -1)
      return hash_set_bst[cur];

   int left_value = MIN;
   int right_value = MAX;
   if (cur -> left != NULL)
      left_value = cur -> left -> value;
   if (cur -> right != NULL)
      right_value = cur -> right -> value;

   if (cur -> value > left_value && cur -> value < right_value)
   {
      hash_set_bst[cur] = is_bst(cur->left) && is_bst(cur->right);
      return hash_set_bst[cur];
   }
   else
   {
      hash_set_bst[cur] = 0;
      is_bst(cur->left);
      is_bst(cur->right);
      return hash_set_bst[cur];
   }
}

これで、ノードごとに、BST を開始できるかどうかがわかります。ここで、サブツリーのサイズを計算し、すべてのノードを反復処理して、ノードが BST を開始できる場合にフラグを持つ最大サイズを把握する必要があります。

サイズを計算するには、次のようにします。

int dfs(node * cur)
{
   if (cur == NULL) return 0;
   size[cur] = 1 + dfs(cur->left) + dfs(cur->right);
   return size[cur];
}
于 2012-08-30T00:17:39.187 に答える
1

サブツリーのいずれかが BST である場合は、トラバーサルが昇順で生成されるように、バイナリ ツリーの順序どおりにトラバーサルを実行し、ツリーのサイズを記録します。ブレークポイントにヒットすると、ブレークポイントをルートとして使用してそのツリーをトラバーサルするために再帰的に、そのサイズを記録します。一番大きいものを選びます。

于 2012-08-30T00:29:33.643 に答える