Ở đây chúng ta sẽ thấy, cách tìm giá trị Tầng và Trần từ BST. Ví dụ, nếu chúng ta muốn tạo một hệ thống quản lý bộ nhớ, nơi các nút tự do được sắp xếp trong BST. Tìm phù hợp nhất cho yêu cầu đầu vào. Giả sử chúng ta đang di chuyển xuống cây với dữ liệu nhỏ nhất lớn hơn giá trị khóa, thì có ba trường hợp có thể xảy ra.
- Gốc là chìa khóa. Khi đó giá trị gốc là giá trị trần
- Nếu dữ liệu gốc
- Nếu dữ liệu gốc> khóa, thì giá trị trần có thể nằm ở cây con bên phải, chúng tôi có thể tìm thấy nút có dữ liệu lớn hơn khóa trong cây con bên trái, nếu không có phần tử như vậy thì giá trị trần là giá trị trần.
Giả sử cái cây như thế này -
Trần 0, 1, 2 là 2, trần 3, 4 là 4, v.v.
Ở đây chúng ta sẽ chỉ thấy chức năng trần, nếu chúng ta sửa đổi một chút, chúng ta có thể nhận được giá trị sàn.
Ví dụ
#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;
} Đầu ra
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