0

二分木で最大の BST を持つためのアプローチは何ですか? 最大で、つまり最高です。

ツリーが BST であるかどうかを確認するための非常に優れた実装があるこの投稿を参照します。

bool isBinarySearchTree(BinaryTree * n,
int min=std::numeric_limits<int>::min(),
int max=std::numeric_limits<int>::max()) 
{
     return !n || (min < n->value && n->value < max
     && isBinarySearchTree(n->l, min, n->value)
     && isBinarySearchTree(n->r, n->value, max));
}

ツリーに二分探索木が含まれているかどうかを調べるソリューションを実装するのは非常に簡単です。私は次の方法がそれを作ると思います：

bool includeSomeBST(BinaryTree* n)
{ 
      return includeSomeBST(n->left)  ||  includeSomeBST(n->right) ;

      if(n == NULL)
           return false ; 

      return true ;
}

しかし、最大の BST が必要な場合はどうすればよいでしょうか? これは私の最初のアイデアであり、

BinaryTree largestBST(BinaryTree* n)
{ 
      if(isBinarySearchTree(n))
           return n;

      if(!isBinarySearchTree(n->left))
      {
           if(!isBinarySearchTree(n->right))
               if(includeSomeBST(n->right))
                    return largestBST(n->right);

               else if(includeSomeBST(n->left))
                    return largestBST(n->left);

               else
                   return NULL;

           else
               return n->right;
      }
      else 
          return n->left;
}

しかし、実際には最大のものではありません。私は比較をするのに苦労しています。それはどのように行われるべきですか？

ありがとう

4

2 に答える 2

1

はい、関数 includeSomeBST が間違っています。ノード n,n->left および n->right をチェックするだけですが、ノードを再帰的にチェックする必要があります。

bool includeSomeBST(BinaryTree* n) {

  if(!isBinarySearchTree(n))
  {

       return includeSomeBST(n->left) || includeSomeBST(n->right);
  }

  if(n==NULL) return false; 
  return true;

}

于 2012-10-07T10:30:08.257 に答える
0

ドライバープログラムと一緒に同じものの成功したコード実装は次のとおりです。

#include <iostream>
using namespace std;

class BinaryTree {
    public:
        BinaryTree *right;
        BinaryTree *left;
        int value;
        BinaryTree(int value) {
            this->value = value;
        }
};


int max_value(int a, int b) {
    if (a > b) {
        return a;
    } else {
        return b;
    }
}

int min_value(int a, int b) {
    if (a < b) {
        return a;
    } else {
        return b;
    }
}

BinaryTree* findLargestBST(BinaryTree *n, int* maxSize, int *max, int *min, bool *is_bst) {
    if (n == NULL) {
        *maxSize = 0;
        *is_bst = true;
        return n;
    }
    int *lc_max_size = new int;
    int *rc_max_size = new int;
    int *lc_max = new int;
    int *lc_min = new int;
    int *rc_max = new int;
    int *rc_min = new int;
    *lc_max = std::numeric_limits<int>::min();
    *rc_max = *lc_max;
    *lc_min = std::numeric_limits<int>::max();
    *rc_min = *lc_min;
    BinaryTree* returnPointer;

    bool is_curr_bst = true;
    BinaryTree* lc = findLargestBST(n->left, lc_max_size, lc_max, lc_min, is_bst);
    if (!*is_bst) {
        is_curr_bst = false;
    }

    BinaryTree* rc = findLargestBST(n->right, rc_max_size, rc_max, rc_min, is_bst);
    if (!*is_bst) {
        is_curr_bst = false; 
    }

    if (is_curr_bst && *lc_max <= n->value && n->value <= *rc_min) {
        *is_bst = true;
        *maxSize = 1 + *lc_max_size + *rc_max_size;
        returnPointer = n;
        *max = max_value (n->value, *rc_max);
        *min = min_value (n->value, *lc_min);
    } else {
        *is_bst = false;
        *maxSize = max_value(*lc_max_size, *rc_max_size);
        if (*maxSize == *lc_max_size) {
            returnPointer = lc;
        } else {
            returnPointer = rc;
        }
        *max = *min = n->value;
    }

    delete lc_max_size;
    delete rc_max_size;
    delete lc_max;
    delete lc_min;
    delete rc_max;
    delete rc_min;
    return returnPointer;
}

int main() {

    /* Let us construct the following Tree
          50
       /      \
     10        60
    /  \       /  \
   5   20    55    70
            /     /  \
          45     65    80
  */

  BinaryTree *root = new BinaryTree(50);
  root->left        = new BinaryTree(10);
  root->right       = new BinaryTree(60);
  root->left->left  = new BinaryTree(5);
  root->left->right = new BinaryTree(20);
  root->right->left  = new BinaryTree(55);
  root->right->left->left  = new BinaryTree(45);
  root->right->right = new BinaryTree(70);
  root->right->right->left = new BinaryTree(65);
  root->right->right->right = new BinaryTree(80);

  /* The complete tree is not BST as 45 is in right subtree of 50.
     The following subtree is the largest BST
        60
      /  \
    55    70
   /     /  \
  5     65    80
  */

  int *maxSize = new int;
  int *min_value = new int;
  int *max_value = new int;
  *min_value = std::numeric_limits<int>::max();
  *max_value = std::numeric_limits<int>::min();
  bool *is_bst = new bool;
  BinaryTree *largestBSTNode = findLargestBST(root, maxSize, max_value, min_value, is_bst);
  printf(" Size of the largest BST is %d", *maxSize);
  printf("Max size node is %d", largestBSTNode->value);
  delete maxSize;
  delete min_value;
  delete max_value;
  delete is_bst;
  getchar();

  return 0;
}

使用されるアプローチはかなり単純で、次のように理解できます。

これは、ツリーがBSTであるかどうかを判断するときに使用する上から下へのアプローチではなく、下から上へのアプローチです。これは、ツリーをBSTとして決定するときに使用されるのと同じmax-minアプローチを使用します。

以下は、各ノードで再帰的に実行されるステップです。 注：これはボトムアップのアプローチであり、情報は下から上に流れることに注意してください。

1）私が存在するかどうかを判断します。私がそうでない場合（私はnullです）、アルゴリズムに影響を与えてはならず、変更を加えずに戻る必要があります。

2）すべてのノードで、この時点までのBSTの最大サイズが格納されます。これは、この特定のノードのツリーがBSTプロパティを満たしている場合、左側のサブツリーの合計サイズ+右側のサブツリーの合計サイズ+ 1（ノード自体の場合）を使用して決定されます。それ以外の場合は、左側のサブツリーと右側のサブツリーから返された最大値から計算されます。

3）指定されたノードでBSTプロパティが満たされている場合、現在のノードはこの時点までの最大サイズBSTとして返されます。それ以外の場合は、左右のサブツリーから決定されます。

于 2012-10-08T18:37:58.977 に答える