Cấu trúc dữ liệu để lưu trữ các dải

Question

Tôi tự hỏi nếu có ai biết cấu trúc dữ liệu có thể xử lý hiệu quả tình huống sau:

Cấu trúc dữ liệu sẽ lưu trữ một số, có thể chồng chéo, độ dài biến trên một khoảng thời gian liên tục.

• Ví dụ: bạn có thể thêm phạm vi a:[0,3], b:[4,7], c:[0,9].

• Thời gian chèn không cần phải đặc biệt hiệu quả.

năng tìm lại sẽ mất một loạt như một tham số, và trả lại tất cả các dãy trong tập trùng với phạm vi, ví dụ:

• Get(1,2) sẽ trở lại a và c. Get(6,7) sẽ trả lại b và c. Get(2,6) sẽ trả về cả ba.

• Các thủ thuật cần phải hiệu quả nhất có thể.

Answer 1

Bạn có thể tìm một cây nhị phân, lưu trữ các dải trong một hệ thống phân cấp. Bắt đầu từ nút gốc, đại diện cho một dải bao quanh chia nó ở giữa của nó, bạn kiểm tra xem phạm vi của bạn mà bạn đang cố gắng chèn có nằm trong khoảng con bên trái, đúng hay không, hoặc cả hai, và đệ quy thực hiện trong các phân đoạn phù hợp cho đến khi bạn đạt đến độ sâu nhất định, tại đó bạn lưu phạm vi thực tế.

Để tra cứu, bạn kiểm tra phạm vi nhập của mình dựa vào các nút con bên trái và bên phải của nút trên cùng và đi sâu vào các nút chồng chéo, lặp lại cho đến khi bạn đạt đến phạm vi thực tế mà bạn lưu.

Bằng cách này, quá trình truy xuất có độ phức tạp lôgarit. Bạn vẫn cần phải quản lý các bản sao trong truy xuất của bạn, vì một số phạm vi sẽ thuộc về một số nút.

Answer 2

Một cấu trúc dữ liệu bạn có thể sử dụng là một chiều R-tree. Chúng được thiết kế để xử lý các phạm vi và để cung cấp khả năng truy xuất hiệu quả. Bạn cũng sẽ tìm hiểu về Allen's Operators; có một tá mối quan hệ khác giữa các khoảng thời gian hơn là chỉ 'chồng chéo'.

Có những câu hỏi khác về SO mà đụng chạm đến lĩnh vực này, bao gồm:

• SO 325933
• SO 210729