Chúng ta vẫn dùng thuận giải để chèn các điểm vào cây 2D như trong cây tìm kiếm nhị phân thông thường; nhưng ở nút gốc, ta dùng tung độ y (nếu điểm được chèn có tung độ y nhỏ hơn điểm ở nút gốc, thì sang trái; nếu không sẽ sang phải), sau đó ở mức tiếp theo ta dùng hoành độ x, rồi ở mức tiếp theo nữa thì dùng tung độ y,… cứ luân phiên như vậy cho đến khi gặp nút ngoài cùng. Ta hãy cùng xét hình ảnh cây 2D dưới tương ứng với tập điểm trong ví dụ
Điều đáng chú ý của kỹ thuật này là việc chia mặt phẳng một cách đơn giản: tất cả những điểm dưới gốc thuộc cây con bên trái, tất cả các điểm ở trên thuộc cây con bên phải; sau đó tất cả những điểm ở trên nút gốc và ở bên trái điểm thuộc cây con bên phải thì thuộc cây con bên trái của cây con bên phải của nút gốc 
Hình trên là minh họa cho bước khởi đầu của việc chia nhỏ mặt phẳng một cây 2D. Trước tiên, một điểm ngang được vẽ qua điểm A (là nút đầu tiên được đưa vào). Sau đó, vì B ở dưới A, ta chuyển sang cây con bên trái A, và nửa mặt phẳng dưới A được chia bởi đường thẳng dọc ở hoành độ x của B. Kế tiếp, vì C ở dưới A, ta qua nút gốc, và vì C ở bên trái B, ta qua trái B và chia phần mặt phẳng ở dưới A và bên trái B bằng đường thẳng ngang tại tung độ y của C. Việc chèn D là tương tự, kế tiếp là E được chèn bên phải A vì E ở trên A… Mỗi nút ngoài của cây tương ứng một chình chữ nhật nào đó trong mặt phẳng. Mỗi vùng tương ứng một nút ngoài của cây; mỗi điểm nằm trên một đoạn thẳng dọc hoặc ngang xác định phép chia tại điểm đó. Trình xây dựng cây 2D là một thay đổi đơn giản của trình tìm kiếm trên cây nhị phân chuẩn để thay đổi việc tìm theo x và y tại mỗi mức. Chúng ta sẽ thấy rõ hơn trong thuật toán xây dựng cây 2D dưới đây 
Như đã mô phỏng trên hình vẽ, ta dùng một nút đầu head vơi điểm giả (0,0). Nút head “nhỏ hơn” mọi nút khác để cây lùi qua liên kết phải của nút head, và nút giả z được dùng để biểu diễn mọi nút ngoài. Lời gọi timtrencay(p, head) chèn một nút mới chứa điểm p vào cây. Biến logic d dùng để thực hiện việc kiểm tra luân phiên các toạ độ x và y khi đi xuống trên cây. ** Như vậy việc xây dựng cây 2D từ N điểm ngẫu nhiên đòi hỏi trung bình 2NlnN phép so sánh Thực vậy, với cac điểm phân bố ngẫu nhiên, cây 2D có cùng cách biểu diễn đặc trưng như cây nhị phân. Cả hai toạ độ giữ nhiệm vụ như các khoá ngẫu nhiên. Để tìm kiếm vùng bằng cây 2D, trước tiên ta xây dựng cây 2D từ các điểm trong giai đoạn tiền xử lý:
Tiếp theo, để tìm kiếm vùng, ta kiểm tra điểm ở mỗi nút với vùng tùm với chiều được dùng để chia mặt phẳng của nút đó. Trong ví dụ, ta bắt đầu bằng cách qua phải ở nút gốc và qua phải ở nút E, vì hình chữ nhật tìm kiếm hoàn toàn ở trên A và ở bên phải nút E. Kế đó, ở nút F, ta phải lần xuống theo cả hai cay con vì F rơi trong vùng (theo chiều x) xác định bởi hình chữ nhật (cẩn thận rằng điều này không đồng nghĩa với F rơi trong hình chữ nhật). Tiếp theo là các cây con bên trái của P và K được kiểm tra, tương ứng với việc kiểm tra các vùng phủ lên hình chữ nhật tìm kiếm.
Việc cài đặt tiến trình này là dễ dàng với sự mở rộng đơn giản từ thủ tục khoảng 1D sau:
Cài đặt chương trình sau khi đã mở rộng thuật toán trên:
Thủ tục này lần xuống hai cây con chỉ khi đường phân cách cắt ngang hình chữ nhật, điều này thường không xảy ra với những hình chữ nhật tương đối nhỏ *** Tìm kiếm vùng bằng cây 2D dùng khoảng R+logN bước để tìm R điểm trong các khoảng tìm trong miền chứa N điểm Phương pháp nàyvẫn còn đang được phân tích. Đương nhiên, sự thực hiện luôn phụ thuộc vào kiểu của vùng được dùng. Nhưng phương pháp này rất đáng kể so với phương pháp lưới đã trình bày ở kỳ trước, và nó phần nào ít phụ thuộc vào “tính ngẫu nhiên” của tập điểm. Tìm kiếm trên vùng nhiều chiều Phương pháp lưới và cây 2D tổng quát trực tiếp được cho nhiều chiều hơn: sự mở rộng đơn giản của các thuật toán trên tức khắc cho các phương pháp tìm kiếm làm việc trên vùng có số chiều lớn hơn 2. Tuy nhiên, bản chất của không gian nhiều chiều đòi hỏi phải thận trọng và tính năng của thuật toán này có lẽ khó mà nói trước được cho một ứng dụng cụ thể nào đó Để cài đặt phương pháp lưới cho việc tìm kiếm trên vùng k chiều, ta tạo một lưới là mảng k chiều và dùng một chỉ mục cho mỗi chiều. Vấn đề chính là tìm một giá trị hợp lý cho biến size. Vấn đề này hoàn toàn rõ ràng khi k lớn: kiểu lưới gì được dùng khi tìm kiếm trên vùng 10 chiều? ngay như ta chỉ dùng 3 lần chia cho mỗi chiều, ta cũng cần đến 3 luỹ thừa 10 ô lưới, hầu hết các ô này rỗng với những giá trịn N bình thường. Việc tổng quát từ cây 2D thành cây kD cũng đơn giản: xoay vòng lần lượt qua các chiều (như ta đã làm trong trường hợp 2 chiều bằng cách thay đổi luân phiên giữa x và y) khi lần xuống cây. Như trên, trong trường hợp ngẫu nhiên, cây kết quả có cùng các đặc trưngnhư cây tìm kiếm nhị phân. Cũng như trên, có sự tương ứng tự nhiên giữa các cây và các xử lý hình học. Trong trường hợp 3 chiều, sự phân cành ở mỗi nút tương ứng với việc dùng một mặt phẳng cắt miềm tìm kiếm 3 chiều; một cách tổng quát, ta cắt miền k chiều bằng một siêu phẳng (k-1) chiều nếu k rất lớn, cần chú ý nhiều về sự không cân bằng của cây kD, vì các tập điểm cụ thể có thể không đủ lớn để biểu lộ được sự ngẫu nhiên trên một số lớn các chiều. Đặc biệt, tất cả các điểm trên một cây con có thể sẽ có cùng một giá trị trên nhiều chiều, dẫn đến 1 số các cành một hướng trong cây. Một cách làm giảm vấn đề này, là thay vì xoay vòng các chiều, ta luôn chia cac điểm theo chiều tốt nhất. Kỹ thuật này tất nhiên cũng áp dụng được cho cây 2D. Nó đòi hỏi có thông tim mở rộng (để chọn chiều) được lưu trong mỗi nút, nhưng nó làm giảm sự không cân bằng của cây, đặc biệt là trong các cây có số chiều cao Tóm lại, mặc dù dễ có được sự tổng quát các chương trình này trong bài toán tìm kiếm trên vùng nhiều chiều, nhưng biện pháp như vậy khó áp dụng hữu hiệu cho một ứng dụng lớn. Những cơ sở dữ liệu lớn, với nhiều thuộc tính trong một mẩu tin, có thể là những đối tượng rất phức tạp; và một sự hiểu biết rõ ràng về các đặc trưng của cơ sở dữ liệu là điều cần thiết để phát triển một phương pháp tìm kiếm vùng có hiệu quả cho một ứng dụng cụ thể. Đây là bài toán rất quan trọng còn đang được nghiên cứu.
School@net (Theo THNT)
|
Tìm kiếm
Khách: 13
Thành viên: 0
Tổng cộng: 13
Như đã biết, cây hai chiều là một cấu trúc dữ liệu động, rất giống cây nhị phân ngoại trừ điều là nó chia không gian hình học theo một cách thuận tiện cho việc tìm kiếm vùng. Phương pháp cây hai chiều mang ý tưởng là xây dựng cây tìm kiếm nhị phân với các điểm được chứa trong các nút, dùng các toạ độ x và y của các điểm như là các khoá theo một trình tự thay đổi nghiêm ngặt
