4. Khi chốn Tuzla, trước hết phải so sỏnh XVAL của Tuzla và Banja Luka. Giỏ trị XVAL của Tuzla là 54, cũn của Banja Luka là 19, vậy phải rẽ phải. Sau đú so sỏnh YVAL của Tuzla (40) và Derventa (50), vậy phải rẽ trỏi. Tiếp tục so sỏnh XVAL của Tuzla (54) và Teslic (38), vậy phải rẽ phải (hỡnh 2.3d).
5. Cuối cựng, khi chốn thành phố Sinj, ta phải so sỏnh XVAL của Sinj và
Banja Luka. Ta rẽ trỏi vỡ tọa độ x của Sinjnhor hơn của Banja Luka. Kết quả được mụ tả trờn hỡnh 2.3d và 2.3e.
Trong trường hợp tồi nhất thỡ độ cao của cõy 2-d với k nỳt là (k-1), việc tỡm kiếm nỳt cho trước sẽ mất O(k) lần.
Teslic
a)
b) c) d)
2.2.3. Huỷ bỏ trong cõy 2-d
Cụng việc phức tạp nhất với cõy 2-d là huỷ bỏ điểm khỏi cõy. Giả sử T là cõy 2 chiều, điểm sẽ huỷ bỏ cú tọa độ (x, y). Bước thứ nhất của việc huỷ bỏ là tỡm ra nỳt N trong T sao cho N.XVAL=x và N.YVAL=y. Nếu N là nỳt lỏ thỡ huỷ N là dễ dàng, chỉ việc đặt NIL cho LLINK, RLINK trong nỳt cha N, giải phúng vựng nhớ N. Nếu N là nỳt trong cõy thỡ tỡnh hỡnh phức tạp hơn. Trong trường hợp này, cõy con cú gốc tại N.LLINK (đặt tờn là Tl) hay tại N.RLINK (đặt tờn là Tr) là khụng rỗng. Cỏi ta muốn bõy giờ là tỡm nỳt R từ Tl hay Tr cú thể thay thế nỳt N và cú thể lần lượt được huỷ bỏ khỏi cõy con. Như vậy cỏc bước của thuật toỏn huỷ bỏ nỳt N bờn trong cõy sẽ là:
Bước 1: Tỡm nỳt ứng viờn thay thế R trong Ti với i{l, r}.
Bước 2: Thay thế mọi trường khụng cú liờn kết của N bởi cỏc trường của R. Bước 3: Huỷ bỏ đệ qui R khỏi Ti.
Đệ qui trờn đõy cú điểm dừng vỡ Ti với i{l, r} cú độ cao nhỏ hơn cõy T. Bước phức tạp nhất trong thuật toỏn trờn là tỡm ra nỳt ứng viờn thay thế. Nỳt R muốn thay thế phải cú quan hệ khụng gian với mọi nỳt P trong Tl và Tr sao cho N dẫn tới P. Cú nghĩa rằng, nếu P ở phớa tõy nam N thỡ P phải ở tõy nam R, nếu P ở tõy bắc N thỡ P phải ở tõy bắc R, ... Như vậy, nỳt mong muốn thay thế R phải thoả cỏc tớnh chất sau:
1. Mọi nỳt M trong Tl thoả M.XVAL<R.XVAL nếu level(N) là chẵn và M.YVAL<R.YVAL nếu level(N) là lẻ.
2. Mọi nỳt M trong Tr thoả M.XVALR.XVAL nếu level(N) là chẵn và M.YVALR.YVAL nếu level(N) là lẻ.
Nếu Tr khụng rỗng và level(N) là chẵn, thỡ bất kỳ nỳt nào trong Tr mà cú trường XVAL nhỏ nhất thỡ là nỳt ứng viờn thay thế. Thớ dụ, trong hỡnh 2.3e, nếu ta lấy N là nỳt chứa Banja Luka, thỡ nỳt ứng viờn thay thế từ cõy con bờn phải là nỳt liờn kết với Testic vỡ nú cú tọa độ x nhỏ nhất trong cỏc nỳt của cõy con phớa phải Banja Luka.
Mặt khỏc, nếu Tr khụng rỗng và level(N) là lẻ thỡ bất kỳ nỳt nào trong Tr mà cú trường YVAL nhỏ nhất thỡ là nỳt ứng viờn thay thế.
Tổng quỏt thỡ việc tỡm kiếm nỳt thay thế từ cõy con bờn trỏi chỉ cú thể thắng lợi dưới một số điều kiện nhất định. Nếu level(N) là chẵn thỡ nỳt thay thế phự hợp trong Tl là nỳt bất kỳ nếu thoả món trường XVAL của nú cú giỏ trị lớn
nhất. Tương tự nếu level(N) là lẻ thỡ ta cú thể sử dụng nỳt bất kỳ trong Tl mà cú trường YVAL lớn nhất để làm nỳt thay thế.
Vấn đề xảy ra là cú thể cú nhiều nỳt trong Tl cựng cú XVAL (hay YVAL) lớn nhất, trong trường hợp này điều kiện thứ hai trong định nghĩa cõy 2-d cú thể bị vi phạm bởi bước 3 vừa mụ tả trờn. Tổng quỏt thỡ, nếu N là nỳt trong và ta muốn huỷ bỏ N khỏi T thỡ tỡm thay thế từ cõy con phải vỡ việc tỡm ứng viờn thay thế trong cõy trỏi là khụng thể.
Cỏi gỡ xảy ra nếu N cú cõy phải rỗng (N.RLINK=NIL)? Trong trường hợp này ta cú thể chọn nỳt thay thế R từ Tl cú giỏ trị x nhỏ nhất trong Tl (nếu level(N) là chẵn) hay cú giỏ trị y nhỏ nhất trong Tl (nếu level(N) là lẻ). Sau đú ta sửa đổi bước 2 trong thuật toỏn trờn đõy như sau:
Bước 2 (sửa đổi): Thay thế toàn bộ cỏc trường khụng cú liờn kết của nỳt N bằng nỳt R. Đặt N.RLINK=N.LLINK và N.LLINK=NIL.
2.2.4 Truy vấn khoảng trong cõy 2-d
Truy vấn khoảng trờn cõy 2-d cú tờn T là truy vấn theo chỉ định điểm (xc, yc) và khoảng r. Kết quả cho lại là tập điểm (x, y) trong cõy T sao cho (x, y) nằm trong khoảng r của (xc, yc). Núi cỏch khỏc khoảng truy vấn xỏc định vũng trũn bỏn kớnh r cú tõm (xc, yc) và tỡm mọi điểm trong cõy 2-d nằm trong vũng trũn.
Khi xử lý truy vấn khoảng, ta nhớ lại rằng mỗi nỳt N trong cõy 2-d biểu diễn vựng RN, nếu vũng trũn và vựng RN khụng giao nhau thỡ khụng tỡm thấy điểm nào trong cõy con cú gốc là nỳt N. Hóy quan sỏt cỏc vựng trong hỡnh 2.4d.
1. Nỳt cú nhón Banja Luka biểu diễn vựng chứa cỏc điểm (x, y) của cỏc số thực. 2. Nỳt cú nhón Derventa biểu diễn vựng chứa mọi điểm (x, y) với x19; nú cú thể được thu nhận bởi biểu thức {(x, y) | x19}.
3. Nỳt cú nhón Teslic biểu diễn vựng chứa mọi điểm (x, y) với x19 và y<50; nú cú thể được thu nhận bởi biểu thức {(x, y) | x19&y<50}.
4. Nỳt cú nhón Tuzla biểu diễn vựng chứa mọi điểm (x, y) với x38 và y<50; nú cú thể được thu nhận bởi biểu thức {(x, y) | x38&y<50}.
5. Cuối cựng, nỳt nhón Sinj biểu diễn vựng chứa mọi điểm (x, y) với x<19. Tổng quỏt thỡ mỗi nỳt N cú nhiều nhất 4 ràng buộc kết hợp biểu diễn kết nối cỏc vựng:
1. XLB: Ràng buộc này biểu diễn cận dưới (Lower Bound) của x và cú khuụn dạng xc1.
2. XUB: Ràng buộc này biểu diễn cận trờn (Upper Bound) của x và cú khuụn dạng x<c2.
3. YLB: Ràng buộc này biểu diễn cận dưới của y và cú khuụn dạng yc3. 4. YUB: Ràng buộc này biểu diễn cận trờn của y và cú khuụn dạng y<c4. Cú thể mở rộng định nghĩa kiểu dữ liệu nodetype thành newnodetype bằng cỏch gộp cỏc trường vừa mụ tả trờn như sau:
newnodetype = record INFO: infotype;
XVAL, YVAL: real;
XLB, XUB, YLB, YUB: real {+, -}; LLINK, RLINK: newnodetype;
end
Khi xen nỳt ta chỉ phải làm như sau đõy:
1. Với gốc cõy: đặt - vào XLB và YLB, đặt + vào XUB và YUB. 2. 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.YUB
3. 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
Thớ dụ sau đõy xem xột truy vấn khoảng trờn bản đồ Bosnia (hỡnh 2.5). Cho trước vũ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à Derventa sẽ 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ậy ta 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<19. Vỡ vựng này khụng cắt vũng trũn nờn ta sẽ khụng xem xột cành này. Mặt khỏc cành phớa phải của Banja Luka biểu diễn mọi điểm (x, y) thoả x19, chắc chắn nú cắt vũng trũn. Kiểm tra xem cành bờn phải (Derventa) cú trong vũng trũn? Cõu trả lời là cú, vậy ta cho lại mó của nú. Sau đú hóy khảo sỏt cành của Derventa. Vựng biểu diễn bởi tập điểm (x, y) thoả x19 và y<50. Vựng này cắt vũng trũn, vậy phải kiểm tra cành cú trong vũng trũn? Cõu trả lời là cú, vậy ta trả lại cành của nú (Testic). Hóy xem xột con của
Testic (Tuzla). Vựng này được biểu diễn bởi tập điểm (x, y) thoả x38 và y<50, và vựng này cắt đường trũn. Vậy cần kiểm tra xem Tuzla trong vũng trũn? Cõu trả lời là khụng, do vậy cú thể dừng tại đõy.
2.2.5. Cõy k-d với k2
Cõy 2-d để biểu diễn điểm trong khụng gian 2-d. Cõy k-d với k2 biểu diễn điểm trong khụng gian k-d. Thớ dụ, cõy 3-d biểu diễn cỏc điểm (x, y, z) và cõy 4-d biểu diễn điểm dưới dạng (x, y, x, t)... Tổng quỏt, điểm trong khụng gian k-d cú dạng (x1, ..., xk), trong đú xi là số thực.
Để biểu diễn nỳt cõy k-d, ta giả sử rằng cỏc trường XVAL, YVAL sử dụng trong cõy 2-d bị loại bỏ, thay vỡ nodetype hay newnodetype sẽ cú trường VAL mới. Nú là mảng độ dài k của cỏc số thực.
Cõy T cú cấu trỳc nỳt như vậy được gọi là cõy k-d nếu với mỗi nỳt N trong cõy T ta cú:
1. Giả sử level(N) mod k=i.
2. Với mỗi nỳt M trong cành trỏi của N ta cú M.VAL[i]<N.VAL[i]. 3. Với mỗi nỳt P trong cành phải N ta cú P.VAL[i]N.VAL[i].
Mọi thuật toỏn của cõy 2-d tổng quỏt húa cho cõy k-d với k2. Nếu k=1 ta cú cõy tỡm kiếm nhị phõn chuẩn.
2.3. Cõy tứ phõn điểm (Point Quadtrees)
Một cõy tứ phõn điểm giống như cõy 2-d nú được sử dụng để biểu diễn cỏc điểm dữ liệu trong khụng gian hai chiều. Cú điều khụng giống như cõy 2-d là cõy tứ phõn điểm luụn phõn một vựng thành 4 phần. Trong cõy 2-d, nỳt N phõn một vựng thành hai phần do vẽ một đường thẳng đi qua điểm (N.XVAL, N.YVAL). Đường kẻ này cú thể là đường nằm ngang nếu cấp của N là lẻ hoặc là đường thẳng đứng trong trường hợp cấp của N là chẵn. Đối với cõy tứ phõn điểm thỡ nỳt N phõn một vựng mà nú biểu diễn do vẽ cả đường thẳng đứng và đường nằm ngang qua điểm (N.XVAL, N.YVAL). Bốn phần được tạo ra được gọi là cỏc gúc NW (Tõy Bắc), SW (Tõy Nam), NE (Đụng Bắc) và SE (Đụng Nam) xỏc định bởi nỳt N và mỗi gúc tương ứng với một con của nỳt N. Do đú cỏc nỳt trong cõy bốn nhỏnh cú thể xỏc định 4 cành. Trước khi thực hiện cỏc thao tỏc đối với cõy bốn cành chỳng ta đưa ra định nghĩa đơn giản của cấu trỳc nỳt cho một nỳt của cõy tứ phõn như sau:
qtnodetype = record INFO : infotype; XVAL: real; YVAL: real; NW, SW, NE, SE : qtnodetype; end
2.3.1. Chốn và tỡm kiếm trong cõy tứ phõn điểm
Bõ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ột cõy tứ phõn. Hỡnh 2.6 cho thấy quỏ trỡnh xõy dựng cõy tứ phõn. 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 4 phầ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