b.Hướng giải quyết:

Để tìm một mẩu tin với khóa k đã cho, trước tiên ta so sánh nó với nút gốc nếu nó nhỏ hơn thì đi đến cây con trái. Nếu bằng thì dừng, nếu nó lớn hơn thì đi đến cây con phải.

Áp dụng đệ quy quá trình trên cho các cây con. Trong mỗi bước, chúng ta chắc chắn rằng không có bộ phận nào của cây ngoài “cây con hiện hành “có thể có thể chứa các mẩu tin với khóa k, và “cây con hiện hành “ ngày càng nhỏ hơn. Thủ tục sẽ dừng khi có một mẩu tin với khóa k được tìm thấy hoặc “cây con hiện hành ” trở nên trống. nghĩa là không có một mẩu tin nào chứa khóa k.

Trong tìm kiếm nhị phân đã xét ở phần trước. chúng ta dùng một cây nhị phân để mô tả dãy của các phép so sánh được tạo bởi một hàm tìm kiếm trong mảng. ở phần tìm kiếm cây nhị phân này, chúng ta xây dựng một cấu trúc dữ liệu gồm các mẩu tin được liên kết với nhau và dùng cấu trúc dữ liệu này cho việc tìm kiếm.

Xét hàm tìm kiếm cây nhị phân sau:

Type lienket = ↑ diem;
diem = record
khoa, thongtin: integer;
l, r : lienket;
end;
var t, z, dau : lienket;
function timkiemcaynhiphan(k : integer; x : lienket): lienket;
begin
z ↑.khoa:= k;
repeat
if (k< x ↑.khoa) then x:= x ↑.l
else x: = x↑.r;
until k = x↑.khoa;
timkiemcaynhiphan:= x;
end;
end;

Trong hàm trên ta quy ước: liên kết bên phải của nút dau trỏ tới nút gốc của cây và khóa của nút dau nhỏ hơn tất cả các nút của các khóa khác (thường thì ta cho luôn khóa của nút dau bằng 0 và giả sử tất cả các khóa khác đều nguyên). Như vậy liên kết trái của dau sẽ không được dùng. Bạn sẽ thấy được sự cần thiết của nút dau khi ta dùng nó để thao tác trong hàm chèn sau này.

Như vậy theo thuật toán trên thì để tìm kiếm một mẩu tin có khóa k, chúng ta cho x:= timkiemcaynhiphan (x, dau). Nếu một nút không có cây con trái (hay phải) thì liên kết trái (hay phải ) của nó được trỏ tới nút đuôi z.

Ta đã xét trong trường hợp tìm kiếm tuần tự, chúng ta đã đặt giá trị dạng muốn tìm ở trong z để dừng một quá trình tìm kiếm không thành công. Do đó “cây con hiện hành” trỏ tới x không bao giờ trở thành rỗng và mọi quá trình tìm kiếm đều “thành công”. Trong chương trình gọi hàm tìm kiếm có thể kiểm tra kiểm tra liên kết được trả về có trỏ đến nút z hay không để xác định quá trình tìm kiếm có thành công hay không.

Không mất tính tổng quát, ta quy ước:

- Các liên kết trỏ tới z như trỏ tới các nút ngoài.

- Tất cả các quá trình tìm kiếm không thành công đều kết thúc ở nút ngoài

- Các nút thông thường có chứa các khóa gọi là các nút trong

Chú ý: khi ta đưa thêm khái niệm nút ngoài thì lẽ ra mỗi nút trong đều trỏ đến hai nút khác của cây. Song về mặt cài đặt chúng ta cho tất cả các nút biểu diễn chỉ bởi một nút z duy nhất.

Trường hợp cây rỗng sẽ được biểu diễn bởi một liên kết phải của nút dau trỏ tới z được tạo lập bởi đoạn chương trình sau:

procedure khoitaocay;
begin
new (z);
z ↑.l := z ↑.r;
z ↑.r := z
new(dau);
dau ↑. khoa := 0;
dau ↑.r := z;
end;


Khởi tạo này trỏ các liên kết của z đến chính nó. Chúng ta sẽ sử dụng thủ tục khởi tạo để đảm bảo an toàn trong các chương trình nâng cao mang sau này.

Xét vị dụ áp dụng hàm tìm kiếm khóa I trong cây nhị phân sau:

Trước tiên I được so sánh với A ở gốc. Vì I lớn hơn nên nó tiếp tục được so sánh với S. Cứ tiếp tục như thế nó sẽ được so sánh với E, R, và cuối cùng là H. Các liên kết trong nút chứa H trỏ tới z và quá trình tìm kiếm kết thúc: I được so sánh với chính nó ở trong z và kết quả tìm kiếm kết thúc không thành công.

Ta quy ước rằng các liên kết trỏ tới z như là trỏ tới các nút ngoài, tất cả các quá trình tìm kiếm không thành công đều kết thúc ở các nút ngoài. Các nút không thành công có chứa các khoá được gọi là nút trong; khi đưa thêm khái niệm nút ngoài thì lẽ ra mỗi nút trong đều phải trỏ đến hai nút khác của cây nhưng về mặt cài đặt chúng ta cho tất cả các nút ngoài được biểu diễn chỉ bởi nút z duy nhất. Chúng ta sẽ cùng xét ví dụ sau để thấy các liên kết này và các nút giả một cách rõ nhất:

(cây tìm kiếm nhị phân với các nút giả)

Chúng ta cùng xét một ví dụ cụ thể sau:

Tìm khoá I trên cây trong hình trên bằng cách dùng thủ tục timkiemcaynhiphan. Trước tiên I được so sánh với khoá A ở gốc. Vì I lớn hơn nên nó tiếp tục được so sánh với S, cứ tiếp tục như thế I sẽ được so sánh với E, R, và cuối cùn là H. Các liên kết trong nút chứa H trỏ tới z và quá trình tìm kiếm kết thúc: I được so sánh với chính nó ở trong z và tìm kiếm kết thúc không thành công

School@net (Theo www.thnt.com.vn)