Interval Tree คืออะไร
Interval Trees เป็นต้นไม้ที่เชื่อมโยงกับ Intervals (ช่วง) Interval = Range เช่น [a, b] หมายถึงช่วงจาก a ถึง b
Elementary Intervals
Interval [10, 20] สร้าง 3 ช่วง: -∞ ถึง 10, 10 ถึง 20, 20 ถึง ∞
เพิ่ม Interval [15, 25]:
เพิ่ม Interval [18, 22]:
ตาราง Sub-intervals
| Interval Name | Interval Range | Sub-intervals |
|---|---|---|
| Interval 1 | [10, 20] | [10, 15], [15, 18], [18, 20] |
| Interval 2 | [15, 25] | [15, 18], [18, 20], [20, 22], [22, 25] |
| Interval 3 | [18, 22] | [18, 20], [20, 22] |
โครงสร้าง Interval Tree
Leaf Nodes = Elementary Intervals บน Leafs สร้าง Complete Binary Tree ขึ้นมา
