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  đối với cây gồm  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à . 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. Bản dịch tiếng Anh của Myron J. Ricci (1962) trong Soviet Mathematics Doklady, tập 3, tr. 1259–1263.

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ề . 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  hoặc  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à  với  là độ cao của cây. Độ phức tạp trong trường hợp xấu nhất là  với  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à .

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  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  là nút có khóa nhỏ nhất lớn hơn khóa của . Nút liền trước của  là nút có khóa lớn nhất nhỏ hơn khóa của . 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  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 := 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"  được lưu làm nút cha của . 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  là  thì BST rỗng và  đượ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  thì so sánh các khóa với khóa của  ở dòng 15 đến 19 và chèn nút thích hợp.

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

 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 

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

Thể loại:Cây (cấu trúc)
Thể loại:Kiểu dữ liệu