이진 트리에서 각 자식 노드에는 두 개의 노드(왼쪽 및 오른쪽)만 있습니다. 트리 구조는 단순히 데이터의 표현입니다. 이진 검색 트리(BST)는 이러한 조건을 충족하는 특수한 유형의 이진 트리입니다. −
-
상위 노드에 비해 왼쪽 하위 노드가 더 작습니다.
-
오른쪽 자식의 부모 노드가 자식 노드보다 큽니다.
바이너리 트리가 주어지고 그 안에 있는 가장 큰 BST(바이너리 검색 트리)가 무엇인지 알아내야 한다고 가정해 보겠습니다.
이 작업에서는 이진 트리에서 가장 큰 BST를 찾는 함수를 만듭니다. 이진 트리 자체가 BST인 경우 전체 이진 트리의 크기를 결정할 수 있습니다. 예를 들어 -
입력
10 /\ 5 15 /\ \ 1 8 7
표시된 대로 이 경우 강조 표시된 BST 하위 트리가 가장 큽니다. '3'은 하위 트리의 크기이므로 반환 값은 하위 트리의 크기입니다.
입력
52 / \ 37 67 /\ / \ 12 27 57 77 /\ 72 87
출력
5
길이가 부모 노드의 길이보다 작은 노드가 있는 하위 트리에는 최대 3개의 크기 BST 노드가 있습니다.
주어진 이진 트리에서 가장 큰 BST를 찾는 접근 방식
모든 노드 x에 대해 다음 점이 유효하면 이진 트리는 BST입니다. 데이터가 상위 노드보다 작은 노드만 노드의 왼쪽 하위 트리에 나타납니다. 상위 노드보다 더 많은 데이터가 있는 노드는 하나만 있을 수 있습니다. 왼쪽 및 오른쪽 하위 트리는 모두 이진 검색 트리(BST)로 특성화되어야 합니다.
알고리즘은 -
이진 트리의 루트에서 시작하여 재귀를 사용하여 순회를 수행합니다. 현재 노드 'ROOT'에 대해 다음을 수행합니다.
-
유효한 BST의 루트인 경우 해당 크기를 반환합니다.
-
그렇지 않으면 왼쪽 및 오른쪽 하위 트리에서 가장 큰 BST를 찾습니다.
예
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node *left;
struct Node *right;
};
struct Node *
newNode (int data) {
struct Node *node = new Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
struct Detail {
int size;
int max;
int min;
int ans;
bool isBST;
};
bool isBST (Node * root, int min, int max) {
if (root == NULL) {
return true;
}
if (root->data < min || root->data > max) {
return false;
}
return isBST (root->left, min, root->data - 1) &&
isBST (root->right, root->data + 1, max);
}
int size (Node * root) {
if (root == NULL) {
return 0;
}
return 1 + size (root->left) + size (root->right);
}
int largestBST (Node * root) {
// Current Subtree is BST.
if (isBST (root, INT_MIN, INT_MAX) == true) {
return size (root);
}
// Find largest BST in left and right subtrees.
return max (largestBST (root->left), largestBST (root->right));
}
int main () {
struct Node *root = newNode (67);
root->left = newNode (72);
root->right = newNode (77); root->left->left = newNode (57);
printf ("Size of the largest BST is %d", largestBST (root));
return 0;
} 출력
Size of the largest BST is 2
결론
이 문제에서 우리는 이진 트리와 이진 탐색 트리가 무엇이며 재귀를 사용하여 주어진 이진 트리에서 가장 큰 BST를 찾는 방법을 배웠습니다. 재귀를 사용하여 모든 노드 아래의 하위 트리가 BST인지 여부를 알아내고 그에 따라 값을 반환합니다.