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

Cây tìm kiếm nhị phân
Kiểu	cây
Phát minh năm	1960
Phát minh bởi	P. F. Windley, A. D. Booth, A. J. T. Colin và T. N. Hibbard
Độ phức tạp thời gian theo ký hiệu O lớn Thuật toán Trung bình Xấu nhất Tìm kiếm Θ(log n) O(n) Chèn Θ(log n) O(n) Xóa Θ(log n) O(n) Độ phức tạp không gian Không gian Θ(n) O(n)

Một cây tìm kiếm nhị phân có kích thước là 9, độ sâu là 3 và nút gốc là 8

Trong khoa học máy tính, cây tìm kiếm nhị phân (BST, viết tắt từ tiếng Anh: binary search tree) 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.

Độ 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ề $O(\log 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.

Recursive-Tree-Search(x, key) if x = NULL or key = x.key then return x else if key < x.key then return Recursive-Tree-Search(x.left, key) else return Recursive-Tree-Search(x.right, key) end if

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.

Iterative-Tree-Search(x, key) while x ≠ NULL and key ≠ x.key do if key < x.key then x := x.left else x := x.right end if repeat return x

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)$.

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 ${\text{x}}$ 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 ${\text{x}}$ là nút có khóa nhỏ nhất lớn hơn khóa của ${\text{x}}$. Nút liền trước của ${\text{x}}$ là nút có khóa lớn nhất nhỏ hơn khóa của ${\text{x}}$. 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 ${\text{x}}$ trong BST.

BST-Successor(x) if x.right ≠ NULL then return BST-Minimum(x.right) end if y := x.parent while y ≠ NULL and x = y.right do x := y y := y.parent repeat return y

BST-Predecessor(x) if x.left ≠ NULL then return BST-Maximum(x.left) end if y := x.parent while y ≠ NULL and x = y.left do x := y y := y.parent repeat return y

Để 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.

BST-Maximum(x) while x.right ≠ NULL do x := x.right repeat return x

BST-Minimum(x) while x.left ≠ NULL do x := x.left repeat return x

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.

1 BST-Insert(T, z)2 y := NULL3 x := T.root4 while x ≠ NULL do5 y := x6 if z.key < x.key then7 x := x.left8 else9 x := x.right10 end if11 repeat12 z.parent := y13 if y = NULL then14 T.root := z15 else if z.key < y.key then16 y.left := z17 else18 y.right := z19 end if

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

Quá trình xóa nút trong cây tìm kiếm nhị phân

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:

1. Nếu ${\text{z}}$ là nút lá thì thay bằng ${\text{null}}$ (xem phần (a) trong hình).
2. 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)).
3. 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:
   1. 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.
   2. 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.
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.

1 BST-Delete(BST, z)2 if z.left = NULL then3 Shift-Nodes(BST, z, z.right)4 else if z.right = NULL then5 Shift-Nodes(BST, z, z.left)6 else7 y := BST-Successor(z)8 if y.parent ≠ z then9 Shift-Nodes(BST, y, y.right)10 y.right := z.right11 y.right.parent := y12 end if13 Shift-Nodes(BST, z, y)14 y.left := z.left15 y.left.parent := y16 end if

1 Shift-Nodes(BST, u, v)2 if u.parent = NULL then3 BST.root := v4 else if u = u.parent.left then5 u.parent.left := v6 else7 u.parent.right := v8 end if9 if v ≠ NULL then10 v.parent := u.parent11 end if

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

Bài chi tiết: 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.

Inorder-Tree-Walk(x) if x ≠ NULL then Inorder-Tree-Walk(x.left) thăm nút Inorder-Tree-Walk(x.right) end if

Preorder-Tree-Walk(x) if x ≠ NULL then thăm nút Preorder-Tree-Walk(x.left) Preorder-Tree-Walk(x.right) end if

Postorder-Tree-Walk(x) if x ≠ NULL then Postorder-Tree-Walk(x.left) Postorder-Tree-Walk(x.right) thăm nút end if

Cây tìm kiếm nhị phân cân bằng

Bài chi tiết: Cây tìm kiếm nhị phân tự 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ố

Bài chi tiết: 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

Bài chi tiết: Sắp xếp cây

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

Bài chi tiết: 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

Đọc thêm

• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "12: Binary search trees, 15.5: Optimal binary search trees" [12: Cây tìm kiếm nhị phân, 15.5: Cây tìm kiếm nhị phân tối ưu]. Introduction to Algorithms [Nhập môn thuật toán] (bằng tiếng Anh) (ấn bản thứ 2). MIT Press. tr. 253–272, 356–363. ISBN 0-262-03293-7.
• Đinh Mạnh Tường (2007). "8.4. Cây tìm kiếm nhị phân". Giáo trình Cấu trúc dữ liệu và thuật toán (PDF). Trường Đại học Công nghệ, Đại học Quốc gia Hà Nội. tr. 220–231. Lưu trữ (PDF) bản gốc ngày 29 tháng 6 năm 2024.
• Jarc, Duane J. (ngày 3 tháng 12 năm 2005). "Binary Tree Traversals" [Duyệt cây nhị phân]. Interactive Data Structure Visualizations (bằng tiếng Anh). Đại học Maryland. Bản gốc lưu trữ ngày 27 tháng 2 năm 2014. Truy cập ngày 30 tháng 4 năm 2006.
• Knuth, Donald (1997). "6.2.2 Binary Tree Searching" [6.2.2 Tìm kiếm cây nhị phân]. The Art of Computer Programming [Nghệ thuật lập trình máy tính] (bằng tiếng Anh). Quyển 3: "Sorting and Searching" (ấn bản thứ 3). Addison-Wesley. tr. 426–458. ISBN 0-201-89685-0.
• Long, Sean. "Binary Search Tree" [Cây tìm kiếm nhị phân] (PPT). Data Structures and Algorithms Visualization-A PowerPoint Slides Based Approach (bằng tiếng Anh). SUNY Oneonta.
• Parlante, Nick (2001). "Binary Trees" [Cây nhị phân]. CS Education Library (bằng tiếng Anh). Đại học Stanford. Lưu trữ bản gốc ngày 30 tháng 1 năm 2022.

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)