Cây phạm vi (range tree) được định nghĩa là cấu trúc dữ liệu cây có thứ tự để lưu danh sách điểm. Nó cho phép truy xuất hiệu quả tất cả điểm trong một phạm vi cho trước, thường dùng cho hai chiều trở lên. Nó tương tự kd-tree nhưng với thời gian truy vấn nhanh hơn O(logd n + k) tuy nhiên lưu trữ kém hơn O(n logd-1 n), với d là chiều không gian, n là số điểm trong cây, k là số điểm truy xuất cho một truy vấn. Cây phạm vi khác với cây khoảng (interval trees): thay vì lưu điểm và truy xuất điểm trong phạm vi, cây khoảng lưu khoảng và truy xuất khoảng chứa điểm cho trước.
Cấu trúc dữ liệu
Ví dụ cây phạm vi 1 chiều. Mỗi nút không phải lá lưu giá trị lớn nhất trong cây con trái.
Cây phạm vi trên tập điểm 1 chiều là cây tìm kiếm nhị phân cân bằng trên các điểm đó. Các điểm lưu trong cây được lưu ở các lá; mỗi nút nội bộ lưu giá trị lớn nhất chứa trong cây con trái của nó. Cây phạm vi trên tập điểm d chiều là cây tìm kiếm nhị phân đa cấp (multi-level) được định nghĩa đệ quy. Mỗi cấp của cấu trúc dữ liệu là một cây tìm kiếm nhị phân trên một trong d chiều. Cấp đầu là cây tìm kiếm nhị phân trên tọa độ đầu tiên của d tọa độ. Mỗi đỉnh v của cây này có một cấu trúc liên kết là cây phạm vi (d-1) chiều trên (d-1) tọa độ cuối của các điểm lưu trong cây con của v.
Các thao tác
Xây dựng (Construction)
Cây phạm vi 1 chiều trên n điểm là cây tìm kiếm nhị phân, có thể xây dựng trong O(n log n) thời gian. Cây phạm vi chiều cao hơn được xây dựng đệ quy bằng cách xây 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, sau đó, cho mỗi đỉnh v trong cây này, xây cây phạm vi (d-1) chiều trên các điểm chứa trong cây con của v. Xây dựng cây phạm vi cách này mất O(n logd n) thời gian.