เราจะมาดูวิธีการหาค่าพื้นและเพดานจาก BST ตัวอย่างเช่น หากเราต้องการสร้างระบบจัดการหน่วยความจำ โดยที่โหนดว่างจะถูกจัดเรียงใน 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
