C++의 BST에서 바닥과 천장

여기에서 BST에서 Floor 및 Ceiling 값을 찾는 방법을 살펴보겠습니다. 예를 들어, BST에 여유 노드가 배열된 메모리 관리 시스템을 만들고 싶다면. 입력 요청에 가장 적합한 것을 찾으십시오. 가장 작은 데이터가 키 값보다 큰 트리 아래로 이동한다고 가정하면 세 가지 경우가 있습니다.

• 루트가 핵심입니다. 그런 다음 루트 값은 상한 값입니다.
• 루트 데이터 <키이면 상한 값이 왼쪽 하위 트리에 있지 않고 오른쪽 하위 트리로 진행하여 문제 영역을 줄입니다.
• 루트 데이터> 키이면 상한 값이 오른쪽 하위 트리에 있을 수 있고 왼쪽 하위 트리에서 키보다 큰 데이터를 가진 노드를 찾을 수 있습니다. 그러한 요소가 없으면 루트가 상한 값입니다.

트리가 다음과 같다고 가정하십시오 -

천정 0, 1, 2는 2, 천정 3, 4는 4 등

여기에서는 천장 함수만 볼 수 있습니다. 이 부분을 약간 수정하면 하한값을 얻을 수 있습니다.

예시

#include <iostream>
using namespace std;
class node {
   public:
   int key;
   node* left;
   node* right;
};
node* getNode(int key) {
   node* newNode = new node();
   newNode->key = key;
   newNode->left = NULL;
   newNode->right = NULL;
   return newNode;
}
int ceiling(node* root, int num) {
   if (root == NULL)
   return -1;
   if (root->key == num)
      return root->key;
   if (root->key < num)
      return ceiling(root->right, num);
   int ceil = ceiling(root->left, num);
   return (ceil >= num) ? ceil : root->key;
}
int main() {
   node* root = getNode(8);
   root->left = getNode(4);
   root->right = getNode(12);
   root->left->left = getNode(2);
   root->left->right = getNode(6);
   root->right->left = getNode(10);
   root->right->right = getNode(14);
   for (int i = 0; i < 16; i++)
   cout << i << "\tCeiling: " << ceiling(root, i) << endl;
}

출력

0 Ceiling: 2
1 Ceiling: 2
2 Ceiling: 2
3 Ceiling: 4
4 Ceiling: 4
5 Ceiling: 6
6 Ceiling: 6
7 Ceiling: 8
8 Ceiling: 8
9 Ceiling: 10
10 Ceiling: 10
11 Ceiling: 12
12 Ceiling: 12
13 Ceiling: 14
14 Ceiling: 14
15 Ceiling: -1