алгоритм — C ++ находит самый большой BST в двоичном дереве
Как вы подходите, чтобы иметь самый большой 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;
}
но это не говорит о самом большом. я изо всех сил пытаюсь сделать сравнение. как это должно происходить?
Спасибо
Решение
Да, ваша функция 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;
}
Другие решения
Вот успешная реализация кода для того же вместе с программой драйвера:
#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 или нет.
Ниже приведены шаги, которые выполняются на каждом из узлов рекурсивным способом:
Примечание: пожалуйста, помните, что это подход снизу вверх, и информация будет перетекать снизу вверх.
1) Определить, существую ли я или нет. Если я не (я ноль), я не должен влиять на алгоритм в любом случае и должен вернуться без каких-либо изменений.
2) На каждом узле сохраняется максимальный размер BST до этой точки. Это определяется с использованием общего размера левого поддерева + общий размер правого поддерева + 1 (для самого узла), если дерево в этом конкретном узле удовлетворяет свойству BST. В противном случае он вычисляется по максимальным значениям, которые были возвращены из левого поддерева и правого поддерева.
3) В случае, если свойство BST удовлетворяется в данном узле, тогда текущий узел возвращается как максимальный размер BST до этой точки, в противном случае он определяется из левого и правого поддеревьев.