Cây phạm vi được định nghĩa là cấu trúc dữ liệu dạng cây có thứ tự để chứa một danh sách các điểm. Nó cho phép tất cả các điểm trong một phạm vi nhất định được truy xuất một cách hiệu quả và thường được triển khai theo hai chiều hoặc cao hơn. Nó giống với kd-tree ngoại trừ thời gian truy vấn O nhanh hơn (log d n + k) nhưng lưu trữ O kém hơn (n log d-1 n), với d cho biết kích thước của không gian, n chỉ số điểm trong cây và k cho biết số điểm được truy xuất cho một truy vấn nhất định. Cây khoảng có thể được phân biệt với cây khoảng:thay vì lưu trữ các điểm và cho phép các điểm trong một phạm vi nhất định được truy xuất một cách hiệu quả, cây khoảng lưu trữ các khoảng và cho phép các khoảng chứa một điểm nhất định được truy xuất một cách hiệu quả.
Cấu trúc dữ liệu
Ví dụ về cây phạm vi 1 chiều. Mỗi nút khác với lá lưu trữ giá trị cao nhất trong cây con bên trái của nó.
Cây phạm vi trên một tập hợp các điểm 1 chiều được coi như một cây tìm kiếm nhị phân cân bằng trên các điểm đó. Các điểm được lưu trữ trong cây được lưu trữ trong các lá của cây; mỗi nút bên trong lưu trữ giá trị lớn nhất có trong cây con bên trái của nó. Cây phạm vi trên tập hợp các điểm theo chiều d là cây tìm kiếm nhị phân đa cấp được xác định đệ quy. Mỗi cấp của cấu trúc dữ liệu được coi như một cây tìm kiếm nhị phân trên một trong các chiều d. Mức đầu tiên là cây tìm kiếm nhị phân trên tọa độ d đầu tiên. Mỗi đỉnh v của cây này bao gồm một cấu trúc liên kết là cây phạm vi thứ nguyên (d − 1) trên tọa độ cuối cùng (d − 1) của các điểm được lưu trữ trong cây con của v.
Hoạt động
Xây dựng
Cây phạm vi 1 chiều trên tập hợp n điểm là cây tìm kiếm nhị phân, có thể được xây dựng trong thời gian O (n log n). Cây phạm vi ở các kích thước cao hơn được xây dựng đệ quy bằng cách xây dựng cây tìm kiếm nhị phân cân bằng trên tọa độ đầu tiên của các điểm và sau đó, đối với mỗi đỉnh v trong cây này, xây dựng cây phạm vi thứ nguyên (d − 1) trên các điểm chứa trong cây con của v. Xây dựng cây phạm vi theo cách này sẽ yêu cầu O (n log d n) thời gian.