MultiBooks - Tổng hợp IT - PC part 11

Tham khảo tài liệu multibooks - tổng hợp it - pc part 11, công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
MultiBooks - Tổng hợp IT - PC part 11 1. If region(T) Ç C = Æ then Halt 2. else (a) If (T.XVAL, T.YVAL)Î C then print (T.XVAL, T.YVAL); (b) RangeQueryPointQuadtree(T.NW, C); (c) RangeQueryPointQuadtree(T.SW, C); (d) RangeQueryPointQuadtree(T.NE, C); (e) RangeQueryPointQuadtree(T.SE, C); End proc2.4 Cây tứ phân matrix MX (MX-Quadtrees)Trong cả hai trường hợp cây 2-d và cây tứ phân điểm, hình thù của cây phụ thuộcvào thứ tự các đối tượng được chèn vào cây. Đặc biệt, thứ tự ảnh hưởng đến chiềucao của cây, do đó ảnh hưởng đến độ phức tạp của các thao tác tìm kiếm và chèn.Mỗi nút N của cây 2-d và cây tứ phân điểm biểu diễn vùng và phân chia vùngthành 2 (trường hợp cây 2-d) hoặc 4 (trường hợp cây tứ phân) vùng con. Việc phânchia có thể không đều vì nó phụ thuộc vào vị trí điểm (N.XVAL, N.YVAL) trongvùng biểu diễn bởi N.Ngược lại, mục tiêu của cây MX-quadtree là để đảm bảo hình dạng (và chiều cao)của cây độc lập với số lượng các nút của cây, cũng như thứ tự chèn các nút này.Thêm nữa, MX-quadtree tập trung vào việc đem lại các giải thuật xoá và tìm kiếmcó hiệu quả.Một cách ngắn gọn, cây MX-quadtree làm việc như sau: Đầu tiên chúng ta giả địnhrằng bản đồ đang được phân thành một lưới kích thước (2k x 2k). Người phát triểnứng dụng tự do lựa chọn k và một khi nó được chọn thì nó phải cố định.MX-quadtree có cấu trúc nút tương tự như cây tứ phân điểm, đó là chúng có kiểunewqtnodetype. Có một sự khác biệt là gốc của MX-quadtree miêu tả vùng xácđịnh bởi XLB = 0, XUB = 2k, YLB = 0, YUB = 2k. Hơn nữa, khi một vùng đượcphân chia, nó được chia ở giữa. Do vậy, nếu N là một nút, khi đó các vùng thể hiệnbởi bốn cành của N được mô tả theo bảng dưới đây. Trong bảng này, w ký hiệuchiều rộng của vùng được biểu diễn bởi N và được cho bởi w= N.XUB – N.XLB.Do tất cả các vùng được biểu diễn bởi các nút trong MX-quadtree là các vùngvuông, nên w = N.YUB – N.YLB. Con XLB XUB YLB YUB NW N.XLB N.XLB +w/2 N.YLB +w/2 N.YLB +w SW N.XLB N.XLB +w/2 N.YLB N.YLB +w/2 NE N.XLB +w/2 N.XLB +w N.YLB +w/2 N.YLB +w SE N.XLB +w/2 N.XLB +w N.YLB N.YLB +w/22.4.1 Chèn và tìm kiếm trong MX-Quadtree Error!Chúng ta hãy xem xét cách chèn điểm vào cây MX-Quadtree. Mỗi điểm (x, y)trong cây MX-Quadtree biểu diễn vùng 1x1 mà góc dưới bên trái là (x, y). Điểmchèn vào nút biểu diễn vùng 1x1 tương ứng với điểm này. Giả sử bây giờ chúng tamuốn chèn các điểm A, B, C và D như trên hình 2.12, hãy tiến hành các bước nhưdưới đây: Error!1. Việc chèn điểm A với toạ độ (1, 3) như sau: Là nút gốc biểu diễn toàn bộvùng và A nằm trong NW. Do vậy, cành NW của gốc tương ứng vùng 2x2 mà gócdưới bên trái của nó là điểm (0, 2). Điểm A nằm trong góc NE của vùng này. Hình2.12a chỉ ra kết quả cây tứ phân MX sau khi chèn điểm A. Hình 2.13a chỉ ra việcphân chia vùng. Chú ý rằng điểm A được chèn vào mức 2 của cây và mức nàybằng giá trị k. Tổng quát là điểm luôn được chèn vào mức k trong cây tứ phân MX.2. Việc chèn điểm B với toạ độ (3, 3) sẽ xác định được B thuộc nhánh NE củagốc. Do vậy cành NE của nút gốc tương ứng vùng 2x2 với góc dưới bên trái là (2,2). Điểm B lại nằm trong góc NE của vùng này. Kết quả được thể hiện trên hình2.12b và 2.13b.3. Error!Việc chèn điểm C với tọa độ (3, 1) được tiến hành như sau: C nằm trong góc SEcủa toàn vùng. Điều này đòi hỏi tạo nút mới là nút con SE của gốc. C nằm trongvùng con NE của nút này. Hình 2.12c và 2.13c chỉ ra kết quả.4. Cuối cùng, hình 2.12d và 2.13d biểu diễn kết quả sau khi chèn D.2.4.2 Thao tác xoá trong MX-QuadtreesThao tác xoá trong một MX-Quadtrees là một thao tác tương đối đơn giản bởi vìtoàn bộ các điểm đều nằm ở cấp cuối (đều là các nút lá). Lưu ý rằng nếu N là mộtnút không phải lá trong cây MX-Quadtrees với gốc là T thì khi đó vùng biểudiễn bởi nút N có ít nhất một điểm thuộc cây. Nếu chúng ta muốn xoá một điểm(x, y) từ cây T, việc đầu tiên là thiết lập liên kết tương ứng của cha nút N tới NIL.Nói cách khác nếu M là cha của N và M.DIR trỏ tới N thì thiết lập M.DIR=NIL vàcho lại N để giải phóng vùng nhớ. Bây giờ tiến hành kiểm tra xem bốn trường liênkết của M đều là NIL? nếu đúng ta khảo sát cha của M (ta gọi nó là P). Vì M là concủa P, ta tìm trường liên kết DIR1 sao cho P.DIR1=M. Sau đó thiết lậpP.DIR1=NIL và tiếp tục kiểm tra xem toàn bộ các trường liên kết của P có là NIL?Nếu đúng, tiếp tục tiến trình. Toàn bộ tiến trình đòi hỏi phải duyệt qua cây một lầntừ đỉnh xuống đáy (để tìm nút sẽ xóa) và một lần đi ngược cây. Như vậy toàn bộtiến trình sẽ là O(k) lần.Hãy xem xét tiến trình làm việc ra sao với cây MX trên hình 2.12d. Giả sử ta muốnxoá D. Việc xóa nút D không khó khăn vì ta tìm ra nó và đặt NIL vào trường liênkết SE của cha nó (cái trỏ đến D). Để xác định xem cha của D c ...