หา Floor และ Ceil จาก BST ใน C++

ในบทความนี้เราจะมาดูวิธีหา Floor และ Ceiling Value จาก BST ตัวอย่างระบบจัดการ Memory ที่ Free Nodes จัดเรียงใน BST หา Best Fit สำหรับ Request ถ้าเดินลง Tree ด้วยค่าที่มากกว่า Key น้อยที่สุด จะมี 3 กรณี:

• Root คือ Key แล้ว Root Value คือ Ceiling
• ถ้า Root Data < Key Ceiling ไม่อยู่ Left Subtree ไป Right Subtree
• ถ้า Root Data > Key Ceiling อาจอยู่ Left Subtree หาไม่เจอ Root คือ Ceiling

ตัวอย่าง Tree:

Ceiling ของ 0,1,2 คือ 2 Ceiling ของ 3,4 คือ 4 และต่อไป

ที่นี่แสดง Ceiling Function ถ้าปรับเล็กน้อยจะได้ Floor Values

ตัวอย่างโค้ด C++

#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