Cây tìm kiếm nhị phân

Trong khoa học máy tính, cây tìm kiếm nhị phân (BST, viết tắt từ ) là một cấu trúc dữ liệu cây nhị phân có gốc với khóa của mỗi nút trung gian có giá trị lớn hơn mọi khóa ở cây con trái và nhỏ hơn mọi khóa ở cây con phải tương ứng. Độ phức tạp thời gian của các phép toán trên cây tìm kiếm nhị phân tỉ lệ thuận với độ cao của cây.

Cây tìm kiếm nhị phân cho phép thực thi tìm kiếm nhị phân để truy vấn, chèn và xóa nhanh đối tượng dữ liệu. Vì các nút trong BST được sắp xếp sao cho mỗi phép so sánh bỏ qua khoảng một nửa phần cây còn lại nên hiệu suất truy vấn tỉ lệ thuận theo logarit nhị phân. BST ra đời vào thập niên 1960 để giải quyết bài toán lưu trữ hiệu quả dữ liệu gán nhãn và được cho là do Conway Berners-Lee và David Wheeler phát minh.

Hiệu suất của một cây tìm kiếm nhị phân phụ thuộc vào thứ tự chèn các nút vào cây do quá trình chèn nút vào cây có khả năng dẫn đến suy biến. Một số biến thể của cây tìm kiếm nhị phân có thể được xây dựng với hiệu suất được đảm bảo trong trường hợp xấu nhất. Các phép toán cơ bản bao gồm tìm kiếm, duyệt cây, chèn và xóa. BST với độ phức tạp được đảm bảo trong trường hợp xấu nhất có hiệu suất tốt hơn một mảng chưa sắp xếp, vốn cần thời gian tìm kiếm tuyến tính.

Phân tích độ phức tạp của BST cho thấy phép chèn, xóa và tìm kiếm có độ phức tạp formula_1 đối với cây gồm formula_2 nút. Trong trường hợp xấu nhất, độ phức tạp của chúng suy biến về độ phức tạp của danh sách liên kết đơn là formula_3. Nhằm kiếm soát mức tăng độ cao của cây khi thực hiện phép chèn và xóa tùy ý, đã có một số biến thể BST tự cân bằng được giới thiệu để chặn trên độ phức tạp truy vấn xấu nhất về tương đương với logarit nhị phân. Cây AVL là cây tìm kiếm nhị phân tự cân bằng đầu tiên do Georgy Adelson-Velsky và Evgenii Landis cho ra đời năm 1962.

Cây tìm kiếm nhị phân được ứng dụng để thực thi các kiểu dữ liệu trừu tượng như tập hợp động, bảng dò và hàng đợi ưu tiên, đồng thời cũng được sử dụng trong các thuật toán sắp xếp điển hình như sắp xếp cây.

== Lịch sử ==
Giải thuật cây tìm kiếm nhị phân do một số nhà nghiên cứu như P. F. Windley, Andrew Donald Booth, Andrew Colin và Thomas N. Hibbard khám phá ra độc lập. Giải thuật được cho là do Conway Berners-Lee và David Wheeler phát minh; hai ông đã ứng dụng thuật toán này để lưu trữ dữ liệu gán nhãn trên băng từ vào năm 1960. Một trong những giải thuật cây tìm kiếm nhị phân sớm nhất và phổ biến nhất là do Hibbard phát triển.

Độ phức tạp thời gian cũng như độ cao của một cây tìm kiếm nhị phân luôn tăng lên vô hạn nếu các nút được chèn vào cây theo thứ tự tùy ý, vì vậy đã có nhiều loại cây tìm kiếm nhị phân tự cân bằng ra đời nhằm chặn trên độ cao của cây về formula_1. Một số loại cây tìm kiếm nhị phân cân bằng độ cao như cây AVL, treap hay cây đỏ đen đã được xây dựng nhằm hạn chế độ cao của cây đến mức thấp nhất.

== Tổng quan ==
Cây tìm kiếm nhị phân là cây tìm kiếm có gốc với các nút được sắp xếp theo thứ tự toàn phần, trong đó nút có khóa lớn hơn mỗi nút "K" bất kỳ được lưu ở cây con phải của "K" còn nút có khóa bằng hoặc nhỏ hơn "K" được lưu ở cây con trái của "K", thỏa mãn tính chất tìm kiếm nhị phân.

Cây tìm kiếm nhị phân đạt hiệu quả nhất định trong các thuật toán sắp xếp và tìm kiếm. Tuy nhiên, độ phức tạp tìm kiếm của BST phụ thuộc vào thứ tự chèn và xóa các nút; trường hợp xấu nhất, nhiều phép toán liên tiếp được thực hiện trên BST có thể dẫn đến việc suy biến thành một cấu trúc tương tự danh sách liên kết đơn (hay "cây không cân bằng") với độ phức tạp bằng với danh sách liên kết.

Cây tìm kiếm nhị phân cũng là một cấu trúc dữ liệu cơ bản dùng để xây dựng các cấu trúc dữ liệu trừu tượng như tập hợp, đa tập hợp và mảng kết hợp.

== Phép toán ==
=== Tìm kiếm ===
Phép tìm kiếm một khóa cụ thể trong cây tìm kiếm nhị phân có thể được lập trình theo kiểu đệ quy hoặc vòng lặp.

Quá trình tìm kiếm bắt đầu bằng cách khảo sát nút gốc. Nếu cây đó là rỗng thì khóa cần tìm không tồn tại trong cây. Ngược lại, nếu khóa này bằng với khóa của nút gốc thì tìm kiếm thành công và trả về nút gốc. Nếu khóa cần tìm nhỏ hơn khóa của nút gốc thì tiếp tục khảo sát cây con trái, còn nếu lớn hơn thì khảo sát cây con phải. Quá trình lặp lại đến khi tìm thấy khóa hoặc cây con còn lại là rỗng. Nếu không thấy khóa cần tìm sau khi đi đến cây con rỗng thì khóa đó không có trong cây.

==== Tìm kiếm đệ quy ====
Mã giả sau đây thực thi thủ tục tìm kiếm BST bằng đệ quy.
Thủ tục đệ quy tiếp tục đến khi xuất hiện formula_5 hoặc formula_6 cần tìm kiếm.

==== Tìm kiếm theo phép lặp ====
Biến thể đệ quy của phép tìm kiếm có thể chuyển thành vòng lặp while. Dạng vòng lặp được xác định là có hiệu suất cao hơn trong hầu hết máy tính.

Vì phép tìm kiếm có thể dừng lại tại một nút lá nên độ phức tạp thời gian của tìm kiếm BST là formula_7 với formula_8 là độ cao của cây. Độ phức tạp trong trường hợp xấu nhất là formula_3 với formula_2 là tổng số nút trong BST do một BST không cân bằng có thể suy biến về danh sách liên kết. Tuy nhiên nếu BST cân bằng độ cao thì độ cao đó là formula_1.

====Nút liền sau và nút liền trước====
Việc tìm kiếm nút liền sau hoặc liền trước của một nút formula_12 cho trước là cần thiết cho một số phép toán nhất định. Giả sử mọi nút trong BST là khác nhau, nút liền sau của formula_12 là nút có khóa nhỏ nhất lớn hơn khóa của formula_12. Nút liền trước của formula_12 là nút có khóa lớn nhất nhỏ hơn khóa của formula_12. Dưới đây là mã giả tìm kiếm nút liền sau và nút liền trước của một nút formula_12 trong BST.
Để xác định nút liền sau và nút liền trước, ta cần tìm một nút trong BST có khóa lớn nhất hoặc nhỏ nhất. Sau đây là mã giả cho hai phép toán này.
=== Chèn ===
Phép chèn và xóa khiến biểu diễn của BST thay đổi tự động. Cấu trúc dữ liệu cần phải được điều chỉnh sao cho các tính chất của BST vẫn được thỏa mãn. Nút mới được chèn vào BST thành nút lá. Dưới đây là mã giả thực thi phép chèn ở dạng vòng lặp.

Trong thủ tục trên, một "con trỏ đứng trước" formula_18 được lưu làm nút cha của formula_12. Sau khi khởi tạo ở dòng 2, vòng lặp while từ dòng 4 đến dòng 11 cập nhật các con trỏ. Nếu formula_18 là formula_5 thì BST rỗng và formula_22 được chèn làm nút gốc của cây tìm kiếm nhị phân, còn nếu khác formula_5 thì so sánh các khóa với khóa của formula_18 ở dòng 15 đến 19 và chèn nút thích hợp.

=== Xóa ===
Phép xóa một nút formula_22 khỏi cây tìm kiếm nhị phân formula_26 gồm ba trường hợp:
1. Nếu formula_22 là nút lá thì thay bằng formula_5 (xem phần (a) trong hình).
2. Nếu formula_22 chỉ có một nút con thì đặt nút cha của formula_22 trỏ về nút con để thế chỗ formula_22 trên cây (xem phần (b) và (c)).
3. Nếu formula_22 có cả nút con trái và phải thì nút liền sau trung thứ tự của formula_22 là formula_18 sẽ thế chỗ formula_22 theo hai trường hợp:
1. Nếu formula_18 là nút con phải của formula_22 (phần (d)) thì formula_18 thế chỗ formula_22 và nút con phải của formula_18 không đổi.
2. Nếu formula_18 nằm bên trong cây con phải của formula_22 nhưng không phải là nút con phải của formula_22 (phần (e)) thì formula_18 được thay bằng nút con phải của nó, sau đó thế chỗ formula_22 trên cây.
4. Trường hợp 3 cũng có thể xét bằng nút liền trước trung thứ tự.

Mã giả sau đây thực thi phép xóa một nút trong cây tìm kiếm nhị phân.

Thủ tục formula_46 xử lý ba trường hợp đặc biệt đã nêu ở trên, trong đó dòng 2 và 3 ứng với trường hợp 1, dòng 4 và 5 ứng với trường hợp 2 và dòng 6 đến 16 ứng với trường hợp 3. Hàm formula_47 được gọi bên trong giải thuật xóa nhằm thay nút formula_48 bằng formula_49 trong cây tìm kiếm nhị phân formula_26. Thủ tục này xử lý việc xóa (và thay thế) formula_48 khỏi formula_26.

== Duyệt cây ==
BST có thể được duyệt theo ba giải thuật cơ bản là duyệt trung thứ tự, tiền thứ tự và hậu thứ tự.
- Duyệt trung thứ tự: Thăm các nút ở cây con trái trước, sau đó là nút gốc và cây con phải.
- Duyệt tiền thứ tự: Thăm nút gốc trước, sau đó là cây con trái và cây con phải.
- Duyệt hậu thứ tự: Thăm các nút ở cây con trái trước, sau đó là cây con phải và cuối cùng là nút gốc.

Dưới đây là mã giả thực thi duyệt cây ở dạng đệ quy.

== Cây tìm kiếm nhị phân cân bằng ==
Nếu không có tự cân bằng, các phép chèn hoặc xóa trong một cây tìm kiếm nhị phân có thể dẫn đến suy biến, khiến cây có độ cao là formula_2 (với formula_2 là số đối tượng trong cây) và hiệu suất truy vấn giảm xuống còn tương đương với tìm kiếm tuyến tính. Việc giữ cây cân bằng với độ cao không quá formula_1 là yếu tố quyết định lợi ích của cây tìm kiếm nhị phân. Điều này có thể đạt được thông qua cơ chế "tự cân bằng", vốn được thiết kế nhằm đảm bảo độ cao của cây luôn tỉ lệ thuận với logarit nhị phân qua các phép cập nhật trên cây.

=== Cây cân bằng độ cao ===
Một cây được gọi là cân bằng độ cao nếu độ cao của cây con trái và cây con phải được đảm bảo là có liên hệ với nhau theo một hệ số nhân không đổi. Tính chất này có trong cây AVL và cây đỏ đen. Độ cao của mọi nút trên đường đi từ nút gốc đến nút lá đang cập nhật phải được quan sát và hiệu chỉnh (nếu có) theo mỗi phép chèn và xóa trên cây.

=== Cây cân bằng trọng số ===
Đối với cây cân bằng trọng số, tiêu chí để một cây cân bằng là số nút lá của các cây con. Trọng số của cây con trái và phải sai khác nhau nhiều nhất là formula_56. Tuy nhiên, độ chênh lệch này bị ràng buộc bởi tỉ số formula_57 giữa các trọng số do điều kiện cân bằng mạnh tại formula_56 không thể được duy trì với số lần tái cân bằng cỡ formula_1 trong các phép chèn và xóa. Cây cân bằng trọng số formula_57 cho ra một họ các điều kiện cân bằng mà trong đó mỗi cây con trái và phải chiếm tỉ lệ ít nhất là formula_57 trên tổng trọng số của cây con.

=== Các loại cây ===
Một số loại cây tìm kiếm nhị phân tự cân bằng bao gồm T-cây, treap, cây đỏ đen, B-cây, cây 2–3 và cây splay.

== Ứng dụng ==
=== Sắp xếp ===
Cây tìm kiếm nhị phân được áp dụng trong các giải thuật sắp xếp. Sắp xếp cây là một ví dụ điển hình, trong đó tất cả các phần tử được chèn vào BST cùng lúc và cây sau đó được duyệt trung thứ tự. BST cũng được ứng dụng trong sắp xếp nhanh.

=== Phép toán trên hàng đợi ưu tiên ===
Cây tìm kiếm nhị phân được sử dụng để triển khai hàng đợi ưu tiên với khóa của nút làm thứ tự ưu tiên. Phép chèn phần tử vào hàng đợi tương tự như phép chèn thông thường trên BST, nhưng phép xóa phụ thuộc vào loại hàng đợi ưu tiên:
- Nếu đây là hàng đợi ưu tiên theo thứ tự tăng dần thì phép xóa phần tử có độ ưu tiên thấp nhất được thực hiện bằng cách duyệt BST từ phải sang trái.
- Nếu đây là hàng đợi ưu tiên theo thứ tự giảm dần thì phép xóa phần tử có độ ưu tiên cao nhất được thực hiện bằng cách duyệt BST từ trái sang phải.

== Xem thêm ==
- Cây tìm kiếm
- Cây tìm kiếm nhị phân tối ưu

== Liên kết ngoài ==
- Ben Pfaff: "An Introduction to Binary Search Trees and Balanced Trees". (PDF; 1675 kB) 2004.
- Binary Tree Visualizer (minh họa một số cấu trúc dữ liệu dựa trên cây nhị phân)