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

Tham khảo tài liệu multibooks - tổng hợp it - pc part 10, 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 102. Nếu nút N có nút P là cha và mức level(P) là chẵn thì N.XLB=P.XLB nếu N=P.LLINK N.XLB=P.XVAL nếu N=P.RLINK N.XUB=P.XVAL nếu N=P.LLINK N.XUB=P.XUB nếu N=P.RLINK N.YLB=P.YLB N.YUB=P.YUB3. Nếu nút N có nút P là cha và mức level(P) là lẻ thì N.YLB=P.YLB nếu N=P.LLINK N.YLB=P.YVAL nếu N=P.RLINK N.YUB=P.YVAL nếu N=P.LLINK N.YUB=P.YUB nếu N=P.RLINK N.XLB=P.XLB N.XUB=P.XUBThí dụ sau đây xem xét truy vấn khoảng trên bản đồ Bosnia (hình 2.6). Cho trướcvòng tròn tâm (35, 46) và bán kính 9.5. Câu trả lời là hai điểm Testic và Derventasẽ thoả mãn.Tiến trình truy vấn như sau. Vùng biểu diễn gốc cây 2-d không cắt vòng tròn, vậyta kiểm tra xem Banja Luka có trong vòng tròn? Câu trả lời là nó không nằm trong.Tiếp tục xem xét hai cành của Banja Luka, bên trái biểu diễn mọi điểm (x, y) thoảxđiểm (x, y) thoả x³38 và y qtnodetype = record INFO : infotype; XVAL: real; YVAL: real; NW, SW, NE, SE : qtnodetype; end2.3.1 Chèn và tìm kiếm trong cây tứ phân điểmBây giờ chúng ta hãy khảo sát tập 5 điểm (Banja Luka, Derventa, Teslic, Tuzla vàSinj) đã được thể hiện với cây 2-d, nó sẽ được thể hiện như thế nào thông qua mộtcây tứ phân. Hình 2.7 thể hiện việc chèn từng điểm vào cây, còn hình 2.8 cho thấycây tứ phân được xây dựng như thế nào.Tiến trình này được mô tả như sau:1. Khởi đầu cây tứ phân là rỗng, việc chèn Banja Luka tạo ra nút gốc của câyđược gán nhãn với cặp (19, 45).2. Việc chèn Derventa tạo ra vùng miêu tả bởi Banja Luka được phân thành 4phần thông qua việc vẽ một đường nằm ngang và một đường thẳng đứng qua (19,45). Derventa, ở vị trí (40, 50), nằm trong góc phần tư NE, do vậy Banja Error!Luka có con NE là Derventa.3. Việc chèn Teslic được tiến hành như sau: Teslic nằm theo hướng Đông Namcủa Banja Luka. Do vùng này hiện tại chưa có điểm nào nên chúng ta đặt Tesliclàm con SE của Banja Luka.4. Việc chèn Tuzla phức tạp hơn. Chúng ta thấy rằng Tuzla nằm ở SE của BanjaLuka. Do vậy chúng ta chuyển đến nhánh SE của Banja Luka. Kết quả là góc phầntư SE được chia bởi vẽ đường nằm ngang và đường thẳng đứng qua điểm Teslic.Với kết quả bốn phần được tạo ra, Tuzla ở góc SE và như vậy Tuzla trở thành nútcon SE của Teslic.5. Cuối cùng, việc chèn Sinj là không quá phức tạp bởi vì nó nằm ở SW củaBanja Luka. Do hiện tại con trỏ này là rỗng nên ta đặt nút này chứa thông tin liênquan đến Sinj.Nhìn chung chiều cao của một cây tứ phân chứa n nút có thể có giá trị lớn nhất làn-1, điều đó có nghĩa là thời gian để tìm kiếm hay chèn là nhỏ hơn số lượngnút.2.3.2 Thao tác xoá trên cây tứ phân điểm Error!Khi xoá nút N từ cây tứ phân có gốc T cũng có những nét giống như chúng ta đãthực hiện với cây 2-d để tìm một nút thay thế thích hợp cho các nút không phải làlá. Đối với trường hợp các nút lá thì việc xoá không có vấn đề gì: Chúng ta đặttrường liên kết tương ứng của nút cha của N trỏ tới NIL và giải phóng không gianlưu trữ.Việc xoá trong cây tứ phân là rất phức tạp. Hình 2.9 chỉ ra tại sao lại phứctạp. Đầu tiên mỗi nút trong cây tứ phân thể hiện một vùng và vùng này được địnhnghĩa hơi khác hơn so với cây 2-d. Đối với cây 2-d nó đủ để kết hợp 4 ràng buộcdưới dạng x³c1, x endKhi chèn nút N vào cây T chúng ta cần đảm bảo những điểm dưới đây:1. Nếu N là gốc của cây T, thì N.XLB=-¥, N.YLB=-¥, N.XUB=+¥, vàN.YUB=+¥.2. Nếu P là cha của N thì khi đó bảng dưới đây mô tả những giá trị của cáctrường XLB, YLB, XUB, YUB của N tuỳ thuộc vào việc N là con NW, SW, NEhay SE của P. Chúng ta sử dụng ký hiệu w=(P.XUB–P.XLB) và h=(P.YUB –P.YLB).Trường N.XLB N.XUB N.YLB N.YUB hợpN= P.XLB P.XLB+w´0.5 P.YLB+h´0.5 P.YUB Để vậnP.NW dụngN= P.XLB P.XLB+w´0.5 P.YLB P.YLB+h´0.5 thànhP.SW công kỹN= P.XLB+w´0.5 P.XUB P.YLB+h´0.5 P.YUB thuậtP.NE xoáN= P.XLB+w´0.5 P.XUB P.YLB P.YLB+h´0.5 trong với cây tứP.SE phânđiểm thì khi xoá một nút trong N ta phải tìm một nút thay thế R từ một trong cáccây con của N (từ một trong N.NW, N.SW, N.NE, N.SE) sao cho mỗi nút R1 trongN.NW là ở phía tây bắc của R, mỗi nút R2 trong N.SW ở phía tây nam R, mỗi nútR3 trong N.NE ở phía đông bắc của R và mỗi nút R4 trong N.SE ở phía đông namcủa R.Hãy xem xét cây tứ phân trên hình 2.8 và hình 2.9. Giả sử chúng ta muốn xoáBanja Luka từ cây tứ phân này. Trong trườ ...