Cây Tìm Kiếm Nhị Phân – Wikipedia Tiếng Việt

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)

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 ) {\displaystyle O(\log n)} đối với cây gồm n {\displaystyle 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 ) {\displaystyle 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.[1][2][3]

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ử

[sửa | sửa mã nguồn]

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.[4][5] 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.[6] 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.[4]

Độ 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 ) {\displaystyle O(\log n)} .[7] 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.[8]

Tổng quan

[sửa | sửa mã nguồn]

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.[9]:298[10]:287[11]:221

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.[12][9]:299–302[11]:238

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

[sửa | sửa mã nguồn]

Tìm kiếm

[sửa | sửa mã nguồn]

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.[10]:290–291

Tìm kiếm đệ quy

[sửa | sửa mã nguồn]

Mã giả sau đây thực thi thủ tục tìm kiếm BST bằng đệ quy.[10]:290[11]:224

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 null {\displaystyle {\text{null}}} hoặc key {\displaystyle {\text{key}}} cần tìm kiếm.

Tìm kiếm theo phép lặp

[sửa | sửa mã nguồn]

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.[10]:291[11]:224–225

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 ) {\displaystyle O(h)} với h {\displaystyle h} là độ cao của cây. Độ phức tạp trong trường hợp xấu nhất là O ( n ) {\displaystyle O(n)} với n {\displaystyle 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 ) {\displaystyle O(\log n)} .[10]:290

Nút liền sau và nút liền trước

[sửa | sửa mã nguồn]

Việc tìm kiếm nút liền sau hoặc liền trước của một nút x {\displaystyle {\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 x {\displaystyle {\text{x}}} là nút có khóa nhỏ nhất lớn hơn khóa của x {\displaystyle {\text{x}}} . Nút liền trước của x {\displaystyle {\text{x}}} là nút có khóa lớn nhất nhỏ hơn khóa của x {\displaystyle {\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 x {\displaystyle {\text{x}}} trong BST.[13][14][10]:292–293

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.[10]:291–292

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

[sửa | sửa mã nguồ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á.[10]:294–295 Dưới đây là mã giả thực thi phép chèn ở dạng vòng lặp.[10]:294[11]:226–228

1 BST-Insert(T, z) 2 y := NULL 3 x := T.root 4 while x ≠ NULL do 5 y := x 6 if z.key < x.key then 7 x := x.left 8 else 9 x := x.right 10 end if 11 repeat 12 z.parent := y 13 if y = NULL then 14 T.root := z 15 else if z.key < y.key then 16 y.left := z 17 else 18 y.right := z 19 end if

Trong thủ tục trên, một "con trỏ đứng trước" y {\displaystyle {\text{y}}} được lưu làm nút cha của x {\displaystyle {\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 y {\displaystyle {\text{y}}} là null {\displaystyle {\text{null}}} thì BST rỗng và z {\displaystyle {\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 null {\displaystyle {\text{null}}} thì so sánh các khóa với khóa của y {\displaystyle {\text{y}}} ở dòng 15 đến 19 và chèn nút thích hợp.[10]:295

Xóa

[sửa | sửa mã nguồn]

Phép xóa một nút z {\displaystyle {\text{z}}} khỏi cây tìm kiếm nhị phân BST {\displaystyle {\text{BST}}} gồm ba trường hợp:[10]:295–297[11]:228–231

1. Nếu z {\displaystyle {\text{z}}} là nút lá thì thay bằng null {\displaystyle {\text{null}}} (xem phần (a) trong hình).
2. Nếu z {\displaystyle {\text{z}}} chỉ có một nút con thì đặt nút cha của z {\displaystyle {\text{z}}} trỏ về nút con để thế chỗ z {\displaystyle {\text{z}}} trên cây (xem phần (b) và (c)).
3. Nếu z {\displaystyle {\text{z}}} có cả nút con trái và phải thì nút liền sau trung thứ tự của z {\displaystyle {\text{z}}} là y {\displaystyle {\text{y}}} sẽ thế chỗ z {\displaystyle {\text{z}}} theo hai trường hợp:
   1. Nếu y {\displaystyle {\text{y}}} là nút con phải của z {\displaystyle {\text{z}}} (phần (d)) thì y {\displaystyle {\text{y}}} thế chỗ z {\displaystyle {\text{z}}} và nút con phải của y {\displaystyle {\text{y}}} không đổi.
   2. Nếu y {\displaystyle {\text{y}}} nằm bên trong cây con phải của z {\displaystyle {\text{z}}} nhưng không phải là nút con phải của z {\displaystyle {\text{z}}} (phần (e)) thì y {\displaystyle {\text{y}}} được thay bằng nút con phải của nó, sau đó thế chỗ z {\displaystyle {\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.[10]:296–298

1 BST-Delete(BST, z) 2 if z.left = NULL then 3 Shift-Nodes(BST, z, z.right) 4 else if z.right = NULL then 5 Shift-Nodes(BST, z, z.left) 6 else 7 y := BST-Successor(z) 8 if y.parent ≠ z then 9 Shift-Nodes(BST, y, y.right) 10 y.right := z.right 11 y.right.parent := y 12 end if 13 Shift-Nodes(BST, z, y) 14 y.left := z.left 15 y.left.parent := y 16 end if

1 Shift-Nodes(BST, u, v) 2 if u.parent = NULL then 3 BST.root := v 4 else if u = u.parent.left then 5 u.parent.left := v 6 else 7 u.parent.right := v 8 end if 9 if v ≠ NULL then 10 v.parent := u.parent 11 end if

Thủ tục BST-Delete {\displaystyle {\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 Shift-Nodes {\displaystyle {\text{Shift-Nodes}}} được gọi bên trong giải thuật xóa nhằm thay nút u {\displaystyle {\text{u}}} bằng v {\displaystyle {\text{v}}} trong cây tìm kiếm nhị phân BST {\displaystyle {\text{BST}}} .[10]:298 Thủ tục này xử lý việc xóa (và thay thế) u {\displaystyle {\text{u}}} khỏi BST {\displaystyle {\text{BST}}} .

Duyệt cây

[sửa | sửa mã nguồn] 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ự.[10]:287

• 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.[10]:287–289

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

[sửa | sửa mã nguồn] 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 {\displaystyle n} (với n {\displaystyle 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.[15] Việc giữ cây cân bằng với độ cao không quá O ( log ⁡ n ) {\displaystyle 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.[7][16]:50

Cây cân bằng độ cao

[sửa | sửa mã nguồn]

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.[16]:50–51 Độ 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.[16]:52

Cây cân bằng trọng số

[sửa | sửa mã nguồn] 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 {\displaystyle 1} .[17][16]:61 Tuy nhiên, độ chênh lệch này bị ràng buộc bởi tỉ số α {\displaystyle \alpha } giữa các trọng số do điều kiện cân bằng mạnh tại 1 {\displaystyle 1} không thể được duy trì với số lần tái cân bằng cỡ O ( log ⁡ n ) {\displaystyle O(\log n)} trong các phép chèn và xóa. Cây cân bằng trọng số α {\displaystyle \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à α {\displaystyle \alpha } trên tổng trọng số của cây con.[16]:62

Các loại cây

[sửa | sửa mã nguồn]

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,[18] treap,[19] cây đỏ đen,[20] B-cây,[21] cây 2–3[22] và cây splay.[23]

Ứng dụng

[sửa | sửa mã nguồn]

Sắp xếp

[sửa | sửa mã nguồn] 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ự.[24] BST cũng được ứng dụng trong sắp xếp nhanh.[25]

Phép toán trên hàng đợi ưu tiên

[sửa | sửa mã nguồ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:[26]

• 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

[sửa | sửa mã nguồn]

• Cây tìm kiếm
• Cây tìm kiếm nhị phân tối ưu

Tham khảo

[sửa | sửa mã nguồn]

1. ^ Pitassi, Toniann (2015). "CSC263: Balanced BSTs, AVL tree" [CSC263: BST cân bằng, cây AVL] (PDF) (bằng tiếng Anh). Khoa Khoa học Máy tính, Đại học Toronto. tr. 6. Lưu trữ (PDF) bản gốc ngày 14 tháng 2 năm 2019. Truy cập ngày 10 tháng 11 năm 2025.
2. ^ Myers, Andrew (2008). "CS312 Lecture: AVL Trees" [CS312 Bài giảng: Cây AVL] (bằng tiếng Anh). Khoa Khoa học Máy tính, Đại học Cornell. Lưu trữ bản gốc ngày 27 tháng 4 năm 2021. Truy cập ngày 10 tháng 11 năm 2025.
3. ^ Adelson-Velsky, Georgy; Landis, Evgenii (1962). "An algorithm for the organization of information" [Một thuật toán cho tổ chức thông tin]. Proceedings of the USSR Academy of Sciences (bằng tiếng Nga). 146: 263–266. Bản dịch tiếng Anh của Myron J. Ricci (1962) trong Soviet Mathematics Doklady, tập 3, tr. 1259–1263.
4. ^ a b Culberson, J.; Munro, J. I. (ngày 1 tháng 1 năm 1989). "Explaining the Behaviour of Binary Search Trees Under Prolonged Updates: A Model and Simulations" [Giải thích hành xử của cây tìm kiếm nhị phân khi cập nhật kéo dài: Mô hình và mô phỏng]. The Computer Journal (bằng tiếng Anh). 32 (1): 68–75. doi:10.1093/comjnl/32.1.68. ISSN 0010-4620. Truy cập ngày 10 tháng 11 năm 2025.
5. ^ Culberson, Joseph; Munro, J. Ian (1990). "Analysis of the standard deletion algorithms in exact fit domain binary search trees" [Phân tích các thuật toán xóa thông thường trong cây tìm kiếm nhị phân]. Algorithmica (bằng tiếng Anh). 5 (1–4): 295–311. doi:10.1007/BF01840390. ISSN 0178-4617. Truy cập ngày 10 tháng 11 năm 2025.
6. ^ Windley, P. F. (ngày 1 tháng 2 năm 1960). "Trees, Forests and Rearranging" [Cây, rừng cây và tái sắp xếp]. The Computer Journal (bằng tiếng Anh). 3 (2): 84–88. doi:10.1093/comjnl/3.2.84. ISSN 0010-4620.
7. ^ a b Knuth, Donald Ervin (1998). "6.2.3 Balanced Trees" [6.2.3 Cây cân bằng]. The Art of Computer Programming [Nghệ thuật lập trình máy tính] (bằng tiếng Anh). Quyển 3 (ấn bản thứ 2). Addison-Wesley. tr. 458–481. ISBN 978-0-201-89685-5.
8. ^ Black, Paul E. (ngày 12 tháng 11 năm 2019). "red-black tree" [cây đỏ đen]. Trong Black, Paul E. (biên tập). Dictionary of Algorithms and Data Structures [Từ điển cấu trúc dữ liệu và giải thuật] (bằng tiếng Anh). Viện Tiêu chuẩn và Công nghệ Quốc gia Mỹ. doi:10.18434/T4/1422485. Truy cập ngày 10 tháng 11 năm 2025.
9. ^ a b Thareja, Reema (2018). "Hashing and Collision" [Băm và xung đột]. Data Structures Using C [Cấu trúc dữ liệu trong C] (bằng tiếng Anh) (ấn bản thứ 2). Nhà xuất bản Đại học Oxford. ISBN 978-0-19-809930-7.
10. ^ a b c d e f g h i j k l m n o Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). Introduction to Algorithms [Nhập môn thuật toán] (bằng tiếng Anh) (ấn bản thứ 2). MIT Press. ISBN 0-262-03293-7.
11. ^ a b c d e f Đinh Mạnh Tường (2007). 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. Lưu trữ (PDF) bản gốc ngày 29 tháng 6 năm 2024. Truy cập ngày 11 tháng 11 năm 2025.
12. ^ Frost, R. A.; Peterson, M. M. (ngày 1 tháng 2 năm 1982). "A Short Note on Binary Search Trees" [Ghi chú ngắn về cây tìm kiếm nhị phân]. The Computer Journal (bằng tiếng Anh). 25 (1): 158. doi:10.1093/comjnl/25.1.158. ISSN 0010-4620. Truy cập ngày 10 tháng 11 năm 2025.
13. ^ Huang, Junzhou. "CSE 5311 Lecture 10: Design and Analysis of Algorithms" [CSE 5311 Bài 10: Thiết kế và phân tích thuật toán] (PDF) (bằng tiếng Anh). Đại học Texas tại Arlington. tr. 12. Lưu trữ (PDF) bản gốc ngày 13 tháng 4 năm 2021. Truy cập ngày 10 tháng 11 năm 2025.
14. ^ Toal, Ray (2022). "CMSI 2120 Notes: Binary Search Tree" [CMSI 2120 Tóm tắt: Cây tìm kiếm nhị phân] (bằng tiếng Anh). Khoa Khoa học Máy tính, Đại học Loyola Marymount. Truy cập ngày 10 tháng 11 năm 2025.
15. ^ Thornton, Alex (2021). "ICS 46: Binary Search Trees" [ICS 46: Cây tìm kiếm nhị phân] (bằng tiếng Anh). Đại học California tại Irvine. Lưu trữ bản gốc ngày 4 tháng 7 năm 2021. Truy cập ngày 10 tháng 11 năm 2025.
16. ^ a b c d e Brass, Peter (2011). Advanced Data Structures [Cấu trúc dữ liệu nâng cao] (bằng tiếng Anh). Nhà xuất bản Đại học Cambridge. doi:10.1017/CBO9780511800191. ISBN 978-0-511-80019-1.
17. ^ Blum, Norbert; Mehlhorn, Kurt (tháng 6 năm 1978). "On the average number of rebalancing operations in weight-balanced trees" [Về số phép toán tái cân bằng trung bình trong cây cân bằng trọng số] (PDF). Theoretical Computer Science (bằng tiếng Anh). 11 (3): 303–320. doi:10.1016/0304-3975(80)90018-3. Truy cập ngày 10 tháng 11 năm 2025.
18. ^ Lehman, Tobin J.; Carey, Michael J. (ngày 25–28 tháng 8 năm 1986). A Study of Index Structures for Main Memory Database Management Systems [Một nghiên cứu về cấu trúc chỉ mục cho hệ thống quản trị cơ sở dữ liệu bộ nhớ chính]. Twelfth International Conference on Very Large Databases (VLDB 1986) (bằng tiếng Anh). Kyoto. ISBN 0-934613-18-4.
19. ^ Aragon, Cecilia R.; Seidel, Raimund G. (1989). Randomized Search Trees [Cây nhị phân ngẫu nhiên]. 30th Annual Symposium on Foundations of Computer Science (bằng tiếng Anh). Washington, D.C.: IEEE Computer Society Press. tr. 540–545. doi:10.1109/SFCS.1989.63531. ISBN 0-8186-1982-1. Truy cập ngày 10 tháng 11 năm 2025.
20. ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Red–Black Trees" [Cây đỏ đen]. Introduction to Algorithms [Nhập môn thuật toán] (bằng tiếng Anh) (ấn bản thứ 2). MIT Press. tr. 273–301. ISBN 978-0-262-03293-3.
21. ^ Comer, Douglas (1979). "The Ubiquitous B-Tree" [B-cây ở khắp nơi]. ACM Computing Surveys (bằng tiếng Anh). 11 (2): 121–137. doi:10.1145/356770.356776. ISSN 0360-0300. Truy cập ngày 10 tháng 11 năm 2025.
22. ^ Knuth, Donald Ervin (1998). "6.2.4 Multiway Trees" [6.2.4 Cây đa hướng]. The Art of Computer Programming [Nghệ thuật lập trình máy tính] (bằng tiếng Anh). Quyển 3 (ấn bản thứ 2). Addison-Wesley. tr. 483. ISBN 978-0-201-89685-5. The 2–3 trees defined at the close of Section 6.2.3 are equivalent to B-Trees of order 3. [Cây 2–3 đã định nghĩa ở cuối mục 6.2.3 tương đương với B-cây bậc 3.]
23. ^ Sleator, Daniel Dominic; Tarjan, Robert Endre (1985). "Self-adjusting binary search trees" [Cây tìm kiếm nhị phân tự điều chỉnh]. Journal of the ACM (bằng tiếng Anh). 32 (3): 652–686. doi:10.1145/3828.3835. ISSN 0004-5411. S2CID 1165848. Truy cập ngày 10 tháng 11 năm 2025.
24. ^ Narayanan, Arvind (2019). "COS226: Binary search trees" [COS226: Cây tìm kiếm nhị phân] (bằng tiếng Anh). Trường Kỹ thuật và Khoa học Ứng dụng, Đại học Princeton. Lưu trữ bản gốc ngày 22 tháng 3 năm 2021. Truy cập ngày 10 tháng 11 năm 2025.
25. ^ Xiong, Li. "A Connection Between Binary Search Trees and Quicksort" [Liên hệ giữa cây tìm kiếm nhị phân và sắp xếp nhanh] (bằng tiếng Anh). Khoa Toán và Khoa học Máy tính, Trường Đại học Oxford, Đại học Emory. Lưu trữ bản gốc ngày 26 tháng 2 năm 2021. Truy cập ngày 10 tháng 11 năm 2025.
26. ^ Myers, Andrew (2016). "CS 2112 Lecture and Recitation Notes: Priority Queues and Heaps" [CS 2112 Bài giảng và tóm tắt ghi nhớ: Hàng đợi ưu tiên và đống] (bằng tiếng Anh). Khoa Khoa học Máy tính, Đại học Cornell. Lưu trữ bản gốc ngày 21 tháng 10 năm 2021. Truy cập ngày 10 tháng 11 năm 2025.

Đọc thêm

[sửa | sửa mã nguồn]

• 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

[sửa | sửa mã nguồn] Wikimedia Commons có thêm hình ảnh và phương tiện về Cây tìm kiếm nhị phân.

• 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)

x t s Cây trong khoa học máy tính
Cây nhị phân	Cây tìm kiếm nhị phân · Cây Descartes · cây top · T-cây
Cây tìm kiếm nhị phân cân bằng	Cây AA · Cây AVL · Cây đỏ-đen · Cây Scapegoat · Cây splay · Treap
B-cây	B+ cây · B*-cây · Bx-cây · UB-cây · cây 2-3 · cây 2-3-4 · (a,b)-cây · Dancing tree · Htree
Trie	Cây hậu tố · Cây cơ số · Cây tìm kiếm tam phân · Cây X-fast · Cây Y-fast
Cây phân chia không gian nhị phân (BSP)	Cây tứ phân · Cây bát phân · cây k-d · Cây k-d ẩn · vp-cây
Cây không nhị phân	Cây lũy thừa · Cây hợp · Cây khoảng · cây PQ · Cây vùng · cây SPQR · cây van Emde Boas
Cây phân chia không gian	R-cây · R+ cây · R* cây · X-cây · M-cây · Cây đoạn · cây Fenwick · R-cây Hilbert
Các cây khác	Đống · Cây băm · Cây con trỏ · Cây metric · Cây phủ · BK-cây · cây liên kết đôi · iDistance · Cây nối-cắt

x t s Cấu trúc dữ liệu
Kiểu	Collection · Container
Trừu tượng	Danh sách · Mảng kết hợp · Multimap · Set · Multiset · Double-ended queue · Hàng đợi · Hàng đợi ưu tiên · Ngăn xếp
Mảng	Mảng động · Sparse array · Circular buffer · Mảng bit · Bảng băm
Liên kết	Danh sách liên kết · Unrolled linked list · Danh sách liên kết XOR · Skip list
Cây	B-cây · Cây tìm kiếm nhị phân (tự cân bằng: AA, AVL, đỏ đen, splay) · Đống (nhị phân, nhị thức, Fibonacci) · Trie
Đồ thị	Đồ thị có hướng · Directed acyclic graph · Sơ đồ quyết định nhị phân · Siêu đồ thị
Danh sách cấu trúc dữ liệu

"Cây tìm kiếm nhị phân" là một bài viết tốt của Wikipedia tiếng Việt.Mời bạn xem phiên bản đã được bình chọn vào ngày 11 tháng 12 năm 2025 và so sánh sự khác biệt với phiên bản hiện tại.