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

|space_worst=
|search_avg=
|search_worst=
|insert_avg=
|insert_worst=
|delete_avg=
|delete_worst=
}}

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 O(\log n) đối với cây gồm n 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à O(n). 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. 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 \text{null} hoặc \text{key} 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à O(h) với h là độ cao của cây. Độ phức tạp trong trường hợp xấu nhất là O(n) với n 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à O(\log n).

Để 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" \text{y} được lưu làm nút cha của \text{x}. 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 \text{y} là \text{null} thì BST rỗng và \text{z} đượ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 \text{null} thì so sánh các khóa với khóa của \text{y} ở dòng 15 đến 19 và chèn nút thích hợp.

Xóa

Phép xóa một nút \text{z} khỏi cây tìm kiếm nhị phân \text{BST} gồm ba trường hợp:
Nếu \text{z} là nút lá thì thay bằng \text{null} (xem phần (a) trong hình).
Nếu \text{z} chỉ có một nút con thì đặt nút cha của \text{z} trỏ về nút con để thế chỗ \text{z} trên cây (xem phần (b) và (c)).
Nếu \text{z} có cả nút con trái và phải thì nút liền sau trung thứ tự của \text{z} là \text{y} sẽ thế chỗ \text{z} theo hai trường hợp:
Nếu \text{y} là nút con phải của \text{z} (phần (d)) thì \text{y} thế chỗ \text{z} và nút con phải của \text{y} không đổi.
Nếu \text{y} nằm bên trong cây con phải của \text{z} nhưng không phải là nút con phải của \text{z} (phần (e)) thì \text{y} được thay bằng nút con phải của nó, sau đó thế chỗ \text{z} trên cây.
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 \text{BST-Delete} 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 \text{Shift-Nodes} được gọi bên trong giải thuật xóa nhằm thay nút \text{u} bằng \text{v} trong cây tìm kiếm nhị phân \text{BST}. Thủ tục này xử lý việc xóa (và thay thế) \text{u} khỏi \text{BST}.

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. Mọi nút trong cây được duyệt tạo thành một dãy khóa không giảm.
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à n (với n 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á O(\log n) 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à 1. Tuy nhiên, độ chênh lệch này bị ràng buộc bởi tỉ số \alpha giữa các trọng số do điều kiện cân bằng mạnh tại 1 không thể được duy trì với số lần tái cân bằng cỡ O(\log n) trong các phép chèn và xóa. Cây cân bằng trọng số \alpha 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à \alpha 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

Tham khảo

Đọc thêm







Liên kết ngoài

Ben Pfaff: An Introduction to Binary Search Trees and Balanced Trees. (PDF; 1675&nbsp;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)