ต้นไม้ช่วง (Interval Tree) เป็นโครงสร้างข้อมูลต้นไม้ที่จัดเรียงแล้ว ใช้สำหรับเก็บช่วง (intervals) โดยเฉพาะอย่างยิ่ง ช่วยให้สามารถค้นหาช่วงทั้งหมดที่ทับซ้อนกับช่วงหรือจุดที่กำหนดได้อย่างมีประสิทธิภาพ นี่คือโปรแกรม C++ สำหรับการนำต้นไม้ช่วงมาใช้งาน
อัลกอริทึม
Begin ฟังก์ชัน insert() ใช้สำหรับแทรกโหนดใหม่เข้าไปในต้นไม้: ถ้าต้นไม้ว่าง โหนดใหม่จะกลายเป็นรูท รับค่า low ของช่วงที่รูท ถ้าค่า low ของรูทน้อยกว่า ช่วงใหม่จะไปอยู่ที่ต้นไม้ย่อยทางซ้าย ถ้าไม่ โหนดใหม่จะไปอยู่ที่ต้นไม้ย่อยทางขวา ถ้าจำเป็น ให้อัปเดตค่า max ของพาเรนต์นี้ End Begin ฟังก์ชัน intervalFind() ค้นหาช่วงที่กำหนด i ในต้นไม้ช่วงที่กำหนด: ถ้าต้นไม้ว่าง ให้คืนค่า null ถ้าช่วงที่กำหนดทับซ้อนกับรูท คืนค่า root->i ถ้าลูกทางซ้ายของรูทมีอยู่ และ max ของลูกทางซ้ายมากกว่าหรือเท่ากับช่วงที่กำหนด แล้ว i อาจทับซ้อนกับช่วงในต้นไม้ย่อยทางซ้าย ถ้าไม่ ช่วงจะทับซ้อนกับต้นไม้ย่อยทางขวาเท่านั้น End
ตัวอย่างโค้ด
#include <iostream> using namespace std; struct Interval//interval variables declaration { int l, h; }; struct ITNod//node declaration { Interval *i; int max; ITNod *l, *r; }; ITNod * newNode(Interval i)//to create new node { ITNod *t = new ITNod; t->i = new Interval(i); t->max = i.h; t->l = t->r = NULL; }; ITNod *insert(ITNod *r, Interval i) { if (r== NULL) return newNode(i); int l = r->i->l; if (i.l< l) r->l = insert(r->l, i); else r->r = insert(r->r, i); if (r->max < i.h) r->max = i.h; return r; } bool Overlap(Interval i1, Interval i2)// check if two intervals overlap or not. { if (i1.l <= i2.h && i2.l<= i1.h) return true; return false; } Interval *intervalFind(ITNod *root, Interval i) { if (root == NULL) return NULL; if (Overlap(*(root->i), i)) return root->i; if (root->l!= NULL && root->l->max >= i.l) return intervalFind(root->l, i); return intervalFind(root->r, i); } void inorder(ITNod *root)//perform inorder traversal { if (root == NULL) return; inorder(root->l); cout << "[" << root->i->l<< ", " << root->i->h << "]" << " max = "<< root->max << endl; inorder(root->r); } int main(int argc, char **argv) { Interval ints[] = { { 5, 20 }, { 6, 7 }, { 3, 4 }, { 67, 26 }, { 3, 4 } }; int n = sizeof(ints) / sizeof(ints[0]); ITNod *root = NULL; for (int i = 0; i < n; i++) root = insert(root, ints[i]); cout << "In-order traversal of the constructed Interval Tree is\n"; inorder(root); Interval x = { 7, 6 }; cout << "\nSearching for interval [" << x.l << "," << x.h << "]"; Interval *res = intervalFind(root, x); if (res == NULL) cout << "\nNo Overlapping Interval"; else cout << "\nOverlaps with [" << res->l << ", " << res->h << "]"; }
ผลลัพธ์
In-order traversal of the constructed Interval Tree is [3, 4] max = 4 [3, 4] max = 4 [5, 20] max = 26 [6, 7] max = 26 [67, 26] max = 26 Searching for interval [7,6] Overlaps with [5, 20]
