Thuật toán cây khoảng thời gian hỗ trợ kết hợp các khoảng thời gian không có chồng chéo

Question

Tôi đang tìm một thuật toán cây khoảng cách tương tự như cây khoảng trắng đen trong CLR nhưng hỗ trợ hợp nhất các khoảng theo mặc định để không bao giờ có khoảng thời gian trùng lặp.

Nói cách khác nếu bạn có cây có hai khoảng [2,3] và [5,6] và bạn đã thêm khoảng [4,4], kết quả sẽ là một cây chỉ chứa một khoảng [2], 6].

Cảm ơn

Cập nhật: trường hợp sử dụng tôi đang xem xét đang tính đóng cửa chuyển tiếp. Tập hợp khoảng thời gian được sử dụng để lưu trữ các bộ kế thừa vì chúng đã là found to be quite compact. Nhưng nếu bạn đại diện cho khoảng thời gian đặt chỉ là một danh sách liên kết tôi đã tìm thấy rằng trong một số trường hợp họ có thể trở nên khá lớn và do đó cũng như thời gian cần thiết để tìm điểm chèn. Do đó quan tâm của tôi trong cây khoảng cách. Ngoài ra có thể có khá nhiều sáp nhập một cây với một cây khác (tức là một hoạt động OR được đặt) - nếu cả hai cây lớn thì tốt hơn nên tạo một cây mới bằng cách sử dụng các trình tự sắp xếp của cả hai cây thay vì chèn lặp lại của mỗi khoảng thời gian.

Answer 1

Vấn đề tôi thấy là việc chèn một khoảng thời gian lớn có thể quét sạch một đoạn lớn của cây, làm cho việc khôi phục các bất biến màu đỏ-đen trở nên khó khăn.

Tôi nghĩ sẽ dễ dàng hơn khi sử dụng cây phát, như sau. Để đơn giản, mỗi cây chứa hai sentinels, một khoảng thời gian A ở bên trái của tất cả các khoảng thời gian khác và một khoảng thời gian Z ở bên phải. Khi chèn một khoảng thời gian I, hãy phát trước I của người tiền nhiệm là H vào thư mục gốc của cây. Cây trông giống như

H 
/\ 
... X 
    /\ 
    ... ... 

Bây giờ tách X và SPLAY I 's kế-to-be J vào thư mục gốc.

H  J 
/ /\ 
...  ... ... 

Tại thời điểm này tất cả các khoảng thời gian đó chồng chéo I là trong cây con trái J 's. Tách cây con đó ra và đặt tất cả các nút của nó vào danh sách miễn phí, mở rộng I nếu cần. Hãy I phụ huynh của H và J

 I 
    /\ 
    H J 
/ \ 
...  ... 

và tiếp tục trên con đường vui vẻ của chúng tôi. Hoạt động này là O (log n) phân bổ, trong đó n là số lượng các nút cây (điều này có thể được chứng minh bằng cách kiểm tra hàm splay tree tiềm năng và thực hiện rất nhiều đại số).

---

tôi nên thêm rằng có một đệ quy cây-to-cây merge tự nhiên bằng cách chèn vào thư mục gốc của một cây và sau đó sáp nhập trái và subtrees đúng. Tôi không biết phân tích nó ra sao.