Bài viết này sẽ giới thiệu và trình bày kiến thức về cây nhị phân tìm kiếm. (Bài viết tham khảo từ nguồn: Đỗ Xuân Lôi – Cấu trúc dữ liệu và giải thuật- NXB Đại Học Quốc Gia Hà Nội).
Định nghĩa
Cây nhị phân tìm kiếm ứng với n khoá k1,…,kn là một cây nhị phân mà mỗi nút của nó đều được gán một giá trị khoá nào đó trong các giá trị khoá đã cho và đối với mọi nút trên cây tính chất sau đây luôn được thoả mãn:
- Mọi khoá thuộc cây con trái nút đó đều nhỏ hơn khoá ứng với nút đó.
- Mọi khoá thuộc cây con phải nút đó đều lớn hơn khoá ứng với nút đó.
Ở đây thứ tự chon, ta quy ước là thứ tự tăng dần đối với số và thứ tự từ điển đối với chữ.
Sau đây là ví dụ về cây nhị phân tìm kiếm đối với khoá là số và chữ:
Giải thuật tìm kiếm
Đối với một cây nhị phân tìm kiếm để tìm xem một khoá X nào đó có trên cây đó không, ta có thể thực hiện như sau:
So sánh X với khoá ở gốc, và một trong bốn tình huống sau đây sẽ xuất hiện:
- Không có gốc (cây rỗng): X không có trên cây, phép tìm kiếm không thoả.
- X trùng với khoá gốc: Phép tìm kiếm được thoả.
- X nhỏ hơn khoá ở gốc: tìm kiếm tiếp tục thực hiện bằng cách xét cây con trái của gốc với cách làm tương tự.
- X lớn hơn khoá ở gốc: tìm kiếm tiếp tục thực hiện bằng cách xét cây con phải của gốc với cách làm tương tự.
Như với cây ở hình trên, nếu X=68 ta sẽ thực hiện:
- So sánh X với 34: X>34, ta chuyển sang cây con phải.
- So sánh X với 66: X>66, ta chuyển sang cây con phải.
- So sánh X với 71: X<71, ta chuyển sang cây con trái.
- So sánh X với 68: X=68, vậy tìm kiếm đã được thoả.
Nhưng nếu X=30 thì phải:
- So sánh X với 34: X<34, ta chuyển sang cây con trái.
- So sánh X với 17: X>17, ta chuyển sang cây con phải.
- So sánh X với 25: X>25, ta chuyển sang cây con phải, nhưng cây con phải rỗng, vậy phép tìm kiếm không thoả.
Nếu sau phép tìm kiếm không thoả, ta bổ sung luôn X vào cây nhị phân tìm kiếm (như ví dụ vừa xét ta bổ sung khoá 30 vào thành con phải của nút 25) ta thấy phép bổ sung này thực hiện rất đơn giản và không làm ảnh hưởng gì tới vị trí của các khoá hiện có trên cây cả, tính chất của cây nhị phân tìm kiếm vẫn được đảm bảo.
Nếu giả sử quy cách mỗi nút của cây nhị phân tìm kiếm có dạng:
Ở đây trường LPTR và RPTR chứa các con trỏ trỏ tới gốc cây con trái và cây con phải của nút.
Trường KEY ghi nhận giá trị khoá tương ứng của nút, trường INFOR ghi nhận các thông tin khác, không có vai trò trong tìm kiếm.
Giải thuật tìm kiếm có bổ sung trên cây nhị phân tìm kiếm sẽ như sau:
Procedure BST(T,X,q);{ Thủ tục này thực hiện tìm kiếm trên cây nhị phân tìm kiếm, có gốc được trỏ bởi T, nút có khoá bằng X. Nếu tìm kiếm được thoả thì đưa ra con trỏ q trỏ tới nút đó, nếu tìm kiếm không thoả thì bổ sung nút mới có khoá là X vào T và đưa ra con trỏ q trỏ tới nút mới đó kèm theo thông báo}.
1.{Khởi tạo control}
P:=null; q:=T;2.{Tìm kiếm}
While q ≠ null do
Case
X < KEY (q): p :=q; q:= LPTR(q);
X = KEY (q) : return;
X > KEY (q) :p :=q; q:= RPTR(q);
End case; 3.{Bổ sung}
Call new (q);
KEY(q) :=X;
LPTR(q) :=RPTR(q) :=null;
Case
T = null: T:=q; {cây rỗng, đã bổ sung}
X < KEY(p) : LPTR(p) :=q;
Else : RPTR(p) :=q
End case;
Write(“không thấy, đã bổ sung”);
Return;Với giải thuật trên có thể suy ra: ta có thể dựng được cây nhị phân tìm kiếm ứng với một dãy khoá đưa vào bằng cách liên tục bổ sung các nút ứng với từng khoá, bắt đầu từ một cây rỗng. Tất nhiên thoạt đầu phải dựng lên nút gốc cây ứng với khoá đầu tiên (trường hợp tìm kiếm trên cây rỗng). Sau đó, đối với các khoá tiếp theo, tìm trên cây không thấy thì bổ sung vào.
Author: Nguyễn Khánh Tùng
