Interval tree [Archive] - Diễn Đàn Tin Học

bete

27-03-2005, 19:52

Thân gửi Rikku: bạn coi thử ở http://www.dgp.utoronto.ca/people/JamesStewart/378notes/22intervals/

=> tui thấy trình bày khá rõ về Interval Tree(nhưng chỉ là 1 chiều - 1 dimension)

Tui xin thử diễn giải lại theo sự hiểu biết nông cạn của mình:

1) Mình có n khoảng gốc A1=[b1,e1], A2=[b2,e2],...An=[bn,en]

2) Mình muốn trả lời câu hỏi: cho số k, liệt kê các khoảng gốc Ai có chứa k ở trong (k thuộc Ai)

=> mình có thể xài Interval Tree:

1) Interval Tree là 1 cây nhị phân tìm kiếm (BST- Binary Search Tree)

2) BST thường có 1 trong 2 dạng:

a) dạng 1: mọi nút là nút dữ liệu => nếu có M mẫu tin dữ liệu thì tổng số nút trong cây sẽ là M. Ở dạng này, khi giải bài toán tìm xem 1 giá trị v có ở trong cây: có thể dừng ở 1 nút trong nút trong (internal node) (nếu nút đó là v) hoặc dừng ở 1 nút lá (tìm thấy hoặc không tìm thấy)

a) dạng 2: chỉ nút lá mới là nút dữ liệu, các nút trong (internal node) chỉ là để hướng dẫn sự tìm kiếm => nếu có M mẫu tin dữ liệu thì tổng số nút lá trong cây sẽ là M (tổng số nút trong cây sẽ là 2M-1 thì phải. Ở dạng này, khi giải bài toán tìm xem 1 giá trị v có ở trong cây: luôn dừng ở 1 nút lá (tìm thấy hay không tìm thấy đều vậy)

3) Interval Tree được trình bày trong tài liêu trên ở dạng 2

4) Mình sắp 2n điểm mút (endpoint) (của các khoảng gốc) trên trục thời gian (các khoảng gốc có thể giao nhau và không có điểm mút chung) => trục thời gian sẽ bị chia thành (2n+1) khúc nhỏ (elementary interval. Ví dụ trong tài liệu: A1=[10,20], A2=[15,25], A3=[18,22]
=> 7 khúc sẽ là:
[âm vô cùng,10]: không thuộc khoảng gốc nào hết
[10,15]: thuộc A1
[15,18]: thuộc A1 và A2
[18,20]: thuộc A1, A2 và A3
[20,22]: thuộc A2 và A3
[22,25]: thuộc A2
[25, dương vô cùng]

5) Mỗi khúc sẽ ứng với 1 nút lá => có (2n+1) nút lá

6) Ở mỗi nút lá mình liệt kê các khoảng gốc chứa khúc tương ứng: ví dụ nút [15,18]: chứa A1 và A2. nút [18,20] chứa A1, A2 và A3

7) Khi đó để trả lời câu hỏi "cho số k (giả sử k không trùng điểm mút nào), liệt kê các khoảng gốc Ai có chứa k ở trong (k thuộc Ai)": mình chỉ cần tìm trên cấu trúc cây này. Khi tìm thấy 1 nút lá [aj,bj] thỏa aj < k < bj thì chỉ cần liệt kê các khoảng gốc được chứa trong nút này

***** Tài liệu trên đi thêm 1 bước để tiết kiệm bộ nhớ: nếu cài đặt như trên thì có thể chiếm tới O(n^2) bộ nhớ:

1) Đi ngược từ các nút lá trở lên (quét theo từng dòng, bắt đầu từ dòng kế chót): ở mỗi nút => có 2 (hoặc 1) nút con. Nếu các nút con bao (span) khoảng con [a,b] và [b,c] thì nút đang xét sẽ bao khoảng con [a,c]. Ví dụ: nút cha của [15,18] và [18,20] sẽ bao khoảng con [15,20], nút cha của [20,22] và [22,25] sẽ bao khoảng con [20,25]; đi lên thêm 1 mức: nút cha của [20,25] và [25, dương vô cùng] sẽ bao khoảng con [20, dương vô cùng].

2) Mình không chỉ liệt kê các khoảng gốc ở các nút lá mà cũng liệt kê các khoảng gốc ở các nút trong. 1 khoảng gốc [a,b] chỉ được liệt kê ở 1 nút x (bao khoảng con [c,d]) nếu và chỉ nếu:

a) khoảng gốc [a,b] chứa khoảng con [c,d]

b) Gọi nút cha của x (nếu có) là y (bao khoảng con [e,f]): khoảng gốc [a,b] KHÔNG chứa khoảng con [e,f]

Nói 1 cách khác: mình bắt đầu liệt kê như cách cũ (các khoảng gốc chỉ được liệt kê ở nút lá). Minh đi ngược từng dòng trở lên (bắt đầu từ dòng chứa các nút lá): ở mỗi nút => có 2 (hoặc 1) nút co. Nếu khoảng gốc G được liệt kê ở cả 2 nút con (hoặc ở nút con duy nhứt) thì dời G lên nút đang xét (xóa G ở các nút con và liệt kê G ở nút đang xét)

** Làm như trên thì tại mỗi dòng (tại mỗi mức): 1 khoảng gốc G bất kỳ được liệt kê nhiều nhứt ở 2 nút => tổng cộng sẽ là O (nlogn) (gần như 2nlogn) về chiếm dụng bộ nhớ

3) Khi đó để trả lời câu hỏi "cho số k (giả sử k không trùng điểm mút nào), liệt kê các khoảng gốc Ai có chứa k ở trong (k thuộc Ai)": mình chỉ cần tìm trên cấu trúc cây này. Khi qua mỗi nút trong hoặc nút lá: chỉ cần liệt kê các khoảng gốc chứa trong nút này

(Rikku có thể cho xin cái link tới tài liệu về cây 2 chiều, hoặc cho biết thuật ngữ tiếng Anh của nó là gì (có phải là k-D tree !?) !?)

(có gì sai sót xin các bạn chỉ giúp, cám ơn rất nhiều)

-thân