Tìm Floor và Ceil từ BST trong C++

Tìm giá trị Floor (lớn nhất ≤ key) và Ceil (nhỏ nhất ≥ key) trong BST. Ví dụ ứng dụng: quản lý bộ nhớ, tìm block phù hợp nhất.

Thuật toán tìm Ceil:

• Nếu root == key → root là ceil.
• Nếu root < key → ceil không ở cây con trái, đệ quy sang phải.
• Nếu root > key → ceil có thể ở cây con trái, đệ quy sang trái. Nếu không tìm thấy thì root là ceil.

Ví dụ cây BST:

Ceil của 0,1,2 là 2; 3,4 là 4; 5,6 là 6; 7,8 là 8; 9,10 là 10; 11,12 là 12; 13,14 là 14; 15 là -1 (không có).

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;
}

Kết quả

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