Bài toán tìm kiếm và phương pháp tìm kiếm cơ bản
a. Bài toán: Tìm kiếm trên cây nhị phân là một thuật toán đơn giản, một phương pháp tìm kiếm động hiệu quả.
Phương pháp này là một trong các thuật toán nền móng của khoa học máy tính. Sở dĩ thuật tóan này được bàn ở
đây và được coi là cơ bản bởi lẽ nó đơn giản; nhưng lại là phương pháp tìm kiếm được chọn lựa trong nhiều
trường hợp ứng dụng.
Như chúng ta đã biết trong một cây: mỗi nút chỉ được trỏ tới bởi duy nhất một nút khác gọi là
cha của nó. Một cây nhị phân thì mỗi nút có 2 liền kề trái và phải. Với việc tìm kiếm, mỗi nút
của cây có một mẩu tin chứa giá trị khóa. Không mất tính tổng quát, ta giả thiết rằng: trong cây
– tìm – kiếm – nhị - phân tất cả các mẩu tin với các khóa nhỏ hơn thì ở trong cây – con – trái vàtất cả các mẩu
tin trong cây con phải có giá trị khóa lớn hơn hay bằng nhau. Chúng tathấy rằng sẽ hoàn toàn đơn giản để đảm
bảo cho cây tìm kiếm nhị phân thỏa mãn định nghĩa của nó khi chèn thêmvào một cây nút mới.
Thủ tục tìm kiếm giống như thủ tục tìmkiếmnhiphân ta đã xét ở phần trước. Tất nhiên, chúng ta sẽ luôn bám sát
với định nghĩa của cây nhị phân
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ể 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;

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 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:
Chúng ta cùng xét một ví dụ cụ thể sau:
Tìm khoá I trên cây trong hìnhtrê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ù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à tìm kiếm kết thúc không thành công.
Chèn nút trong cây nhị phân
Để chèn thêm một nút mới vào cây (giả sử chúng ta đã tìm kiếm nó không thành công, kế đến gặp nó trong nơi
chứa z), chúng ta cần một thủ tục duy trì cha p của x trong khi duyệt cây từ gốc đến ngọn. Khi tiếp xúc với ngọn
của cây (xảy ra khi x=z) p trỏ tới nút mà liên kết của nó phải được thay đổi để trỏ tới nút mới được chèn vào.
function chentrongcay(k: integer; x: lienket): lienket;
var p: lienket;
begin

xếp tương tự như phương pháp Quicksort, trong đó nút gốc của cây đóng vai trò là phần tử phân hoạch của
Quicksort.