Xem Interval Tree. Là cây liên quan đến khoảng (interval). Trước hãy xem elementary intervals.
Interval là khoảng [a, b] từ a đến b.
Cho interval [10, 20]. Có 3 khoảng: -∞ đến 10, 10-20, 20-∞.
Thêm interval [15, 25]:
Thêm [18, 22]:
Các interval và sub-intervals:
| Interval Name | 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] |
Xây Interval Tree từ thông tin này. Sub-intervals đặt trong cây con. Mỗi nút lá = elementary interval. Trên các lá xây cây nhị phân hoàn chỉnh.
