Range Trees ในโครงสร้างข้อมูล

Range Tree คืออะไร?

Range Tree = Ordered Tree Data Structure จัดเก็บ List ของ Points รองรับการ Retrieve Points ทั้งหมดใน Range ที่กำหนดได้อย่างมีประสิทธิภาพ ใช้ใน 2D ขึ้นไป

คล้าย kd-tree แต่: Query เร็วกว่า O(log^d n + k) แต่ Storage มากกว่า O(n log^d-1 n)
d = Dimension, n = จำนวน Points, k = จำนวน Points ที่ Retrieve

ต่างจาก Interval Tree: Range Tree เก็บ Points + Range Query, Interval Tree เก็บ Intervals + Point Containment Query

Data Structure

1D Range Tree = Balanced BST บน Points Points เก็บที่ Leaves, Internal Node เก็บ Max Value ใน Left Subtree

d-Dimensional Range Tree = Recursively Defined Multi-level BST
Level 1: BST บน Coordinate แรก
Vertex v แต่ละตัวมี Associated Structure = (d-1)-D Range Tree บน (d-1) Coordinates สุดท้ายของ Points ใน Subtree ของ v

Operations

Construction

1D Range Tree: O(n log n) (Build Balanced BST)
Higher Dimensions: Build BST บน Coordinate แรก → สำหรับแต่ละ Vertex v สร้าง (d-1)-D Range Tree บน Points ใน Subtree ของ v
Total: O(n log^d n) Time

Query (Range Search)

1D: Standard BST Range Query O(log n + k)
d-D: Descend Level 1 Tree หา Nodes ที่ Overlap Query Range → สำหรับแต่ละ Node Query Associated (d-1)-D Tree

สรุป Complexity