CÂY TÌM KIẾM NHỊ PHÂN
Một trong các ứng dụng quan trọng nhất của cây nhị phân là sử dụng cây nhị phân để tổ chức dữ liệu. Trong các chương trình, thông thường chúng ta cần phải lưu một tập các dữ liệu, rồi thường xuyên phải thực hiện cá phép toán: tìm kiếm dữ liệu, cập nhật dữ liệu… Trong các chương 4 và 5, chúng ta đã nghiên cứu sự cài đặt KDLTT tập động (một tập dữ liệu với các phép toán tìm kiếm, xen, loại…) bởi danh sách. Nếu tập dữ liệu được lưu trong DSLK thì các phép toán tìm kiếm, xen, loại, … đòi hỏi thời gian O(n),
trong đó n là số dữ liệu. Nếu tập dữ liệu được sắp xếp thành một danh sách theo thứ tự tăng (giảm) theo khóa tìm kiếm, và danh sách này được lưu trong mảng, thì phép toán tìm kiếm chỉ đòi hỏi thời gian O(logn) nếu sử dụng kỹ thuật tìm kiếm nhị phân (mục 4.4), nhưng các phép toán xen, loại vẫn cần thời gian O(n). Trong mục này, chúng ta sẽ nghiên cứu cách tổ chức một tập dữ liệu dưới dạng cây nhị phân, các dữ liệu được chứa trong các đỉnh của cây nhị phân theo một trật tự xác định, cấu trúc dữ liệu này cho phép ta cài đặt các phép toán tìm kiếm, xen, loại,… chỉ trong thời gian O(h), trong đó h là độ cao của cây nhị phân.
I) Cây tìm kiếm nhị phân
Giả sử chúng ta có một tập dữ liệu, các dữ liệu có kiểu Item nào đó chứa một thành phần được lấy làm khóa tìm kiếm. Chúng ta giả thiết rằng các giá trị khóa có thể sắp thứ tự tuyến tính, thông thường các giá trị khóa là các số nguyên, các số thực, các ký tự hoặc xâu ký tự. Chúng ta sẽ lưu tập dữ liệu đó trong một cây nhị phân (khóa của dữ liệu được nói tới như là khóa của một đỉnh) theo trật tự như sau: giá trị khóa của một đỉnh bất kỳ lớn hơn các giá trị khóa của tất cả các đỉnh ở cây con trái của đỉnh đó và nhỏ hơn các giá trị khóa của tất cả các đỉnh ở cây con phải của đỉnh đó. Do đó, chúng ta có định nghĩa sau:
Cây tìm kiếm nhị phân (binary search tree) là cây nhị phân thỏa mãn tính chất sau: đối với mỗi đỉnh x trong cây, nếu y là đỉnh bất kỳ ở cây con trái của x thì khóa của x lớn hơn khóa của y, còn nếu y là đỉnh bất kỳ ở cây con phải của x thì khóa của x nhỏ hơn khóa của y.
Ví dụ. Chúng ta xét các cây nhị phân với các giá trị khoá của các đỉnh là các số nguyên. Các cây nhị phân trong hình 8.11 là các cây tìm kiếm nhị phân. Chúng ta có nhận xét rằng, các cây tìm kiếm nhị phân trong hình 8.11 biểu diễn cùng một tập hợp dữ liệu, nhưng cây trong hình 8.11a có độ cao là 3, cây trong hình 8.11b có độ cao là 4, còn cây trong hình 8.11c có tất cả các cây con trái của các đỉnh đều rỗng và nó có độ cao là 6. Một nhận xét quan trọng khác là, nếu chúng ta duyệt cây tìm kiếm nhị phân theo thứ tự trong, chúng ta sẽ nhận được một dãy dữ liệu được sắp xếp theo thứ tự khóa tăng dần. Chẳng hạn, với các cây tìm kiếm nhị phân trong hình 8.11, ta có dãy các giá trị khóa là 1, 3, 4, 5,7, 9.
Hình 11. Các cây tìm kiếm nhị phân
Chúng ta cũng có thể định nghĩa cây tìm kiếm nhị phân bởi đệ quy như sau:
• Cây nhị phân rỗng là cây tìm kiếm nhị phân
• Cây nhị phân không rỗng T là cây tìm kiếm nhị phân nếu:
1. Khóa của gốc lớn hơn khóa của tất cả các đỉnh ở cây con trái TLvà nhỏ hơn khóa của tất cả các đỉnh ở cây con phải TR.
2. Cây con trái TL và cây con phải TR là các cây tìm kiếm nhị phân.
Sử dụng định nghĩa đệ quy này, chúng ta dễ dàng đưa ra các thuật toán đệ quy thực hiện các phép toán trên cây tìm kiếm nhị phân, như chúng ta sẽ thấy trong mục sau đây.
II) Các phép toán tập động trên cây tìm kiếm nhị phân
Bây giờ chúng ta xét xem các phép toán tập động (tìm kiếm, xen, loại, …) sẽ được thực hiện như thế nào khi mà tập dữ liệu được cài đặt bởi cây tìm kiếm nhị phân. Chúng ta sẽ chỉ ra rằng, các phép toán tập động trên cây tìm kiếm nhị phân chỉ đòi hỏi thời gian O(h), trong đó h là độ cao của cây. Như độc giả đã thấy trong hình 8.12, một tập dữ liệu có thể lưu trong các cây tìm kiếm nhị phân có độ cao của cây có thể là n, trong đó n là số dữ liệu. Như vậy, trong trường hợp xấu nhất thời gian thực hiện các phép toán tập động trên cây tìm kiếm nhị phân là O(n). Tuy nhiên, trong mục 8.5 chúng ta sẽ chứng tỏ rằng, nếu cây tìm kiếm nhị phân được tạo thành bằng cách xen vào các dữ liệu được lấy ra từ tập dữ liệu một cách ngẫu nhiên, thì thời gian trung bình của các phép toán tập động là O(logn). Hơn nữa, bằng cách áp dụng các kỹ thuật hạn chế độ cao của cây, chúng ta có thể đảm bảo thời gian logarit cho các phép toán tập động trên cây tìm kiếm nhị phân (xem chương 11)
Dưới đây chúng ta sẽ đưa ra các thuật toán thực hiện các phép toán tập động trên cây tìm kiếm nhị phân. Chúng ta sẽ mô tả các thuật toán bởi các hàm dưới dạng giả mã . Trong các thuật toán, chúng ta sẽ sử dụng các ký hiệu sau đây: T là cây tìm kiếm nhị phân có gốc là root, dữ liệu chứa ở gốc được ký hiệu là rootData, cây con trái của gốc là T L , cây con phải của gốc là T R ; v là một đỉnh, dữ liệu chứa trong đỉnh v được ký hiệu là data(v), đỉnh con trái của v là leftChild(v), đỉnh con phải là rightChild(v); dữ liệu trong các đỉnh có kiểu Item, khóa của dữ liệu d được ký hiệu là d.key.
Phép toán tìm kiếm. Cho cây tìm kiếm nhị phân T, để tìm xem cây T có chứa dữ liệu với khóa k cho trước hay không, chúng ta kiểm tra xem gốc có chứa dữ liệu với khóa k hay không. Nếu không, giả sử k < rootData.key, khi đó do tính chất của cây tìm kiếm nhị phân, dữ liệu với khóa k chỉ có thể chứa trong cây con trái của gốc, và do đó, ta chỉ cần tiếp tục tìm kiếm trong cây con trái của gốc. Tương tự, nếu k > rootData.key, sự tìm kiếm được hạn chế trong phạm vi cây con phải của gốc. Từ đó, ta có thuật toán tìm kiếm đệ quy sau:
bool Search(T, k)
// Tìm dữ liệu với khóa k trong cây tìm kiếm nhị phân
// Hàm trả về true (false) nếu tìm thấy (không tìm thấy)
{
if (T rỗng)
return false;
else if (rootData.key = = k)
return true;
else if (k < rootData.key)
Search(T L, k);
else
Search(T R, k)’
}Phân tích thuật toán đệ quy trên, chúng ta dễ dàng đưa ra thuật toán tìm kiếm không đệ quy. Sử dụng biến v chạy trên các đỉnh của cây T bắt đầu từ gốc. Khi v là một đỉnh nào đó của cây T, chúng ta kiểm tra xem đỉnh v có chứa dữ liệu với khóa k hay không. Nếu không, tùy theo khóa k nhỏ hơn (lớn hơn) khóa của dữ liệu trong đỉnh v mà chúng ta đi xuống đỉnh con trái (con phải) của v. Thuật toán tìm kiếm không đệ quy là như sau:
bool Search(T, k) {
if (T rỗng)
return false;
else {
v = root;
do {
if (data(v).key = = k)
return true;
else if (k < data(v).key)
if (v có con trái)
v = leftchild(v);
else return false;
else
if (v có con phải)
v = rightchild(v);
else return false;
}
while (1);
}
}Các đỉnh mà biến v chạy qua tạo thành một đường đi từ gốc hướng tới một lá của cây. Trong trường hợp xấu nhất, biến v sẽ dừng lại ở một đỉnh lá.
Bởi vì độ cao của cây là độ dài của đường đi dài nhất từ gốc tới lá, do đó thời gian của phép toán Search là O(h). Chúng ta nhận thấy có sự tương tự giữa kỹ thuật tìm kiếm nhị phân (xem 4.4) và kỹ thuật tìm kiếm trên cây tìm kiếm nhị phân. Trong quá trình tìm kiếm trên cây tìm kiếm nhị phân , tại mỗi thời điểm chúng ta hạn chế tìm kiếm ở cây con trái hoặc ở cây con phải; còn trong tìm kiếm nhị phân chúng ta tiếp tục tìm kiếm ở nửa bên trái hay nửa bên phải của mảng. Tuy nhiên trong tìm kiếm nhị phân, tại mỗi thời điểm không gian tìm kiếm (mảng) được chia đôi, nửa bên trái và nửa bên phải bằng nhau; điều đó đảm bảo thời gian trong tìm kiếm nhị phân là O(logn). Nhưng trong cây tìm kiếm nhị phân, cây con trái và cây con phải có thể có số đỉnh rất khác nhau, do đó nói chung thời gian tìm kiếm trên cây tìm kiếm nhị phân không phải là O(logn), chỉ có thời gian này khi mà cây tìm
kiếm nhị phân được xây dựng “cân bằng” tại mọi đỉnh.
