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

Cây tìm kiếm nhị phân (viết tắt tiếng Anh: BST - Binary Search Tree) là một cấu trúc dữ liệu rất thuận lợi cho bài toán tìm kiếm.

Tìm kiếm (Searching)

Việc tìm một khóa trên BST có thể thực hiện nhờ đệ quy. Chúng ta bắt đầu từ gốc. Nếu khóa cần tìm bằng khóa của gốc thì khóa đó trên cây, nếu khóa cần tìm nhỏ hơn khoa ở gốc, ta phải tìm nó trên cây con trái, nếu khóa cần tìm lớn hơn khóa ở gốc, ta phải tìm nó trên cây con phải. Nếu cây con (trái hoặc phải) là rỗng thì khóa cần tìm không có trên cây.
Giả mã
Search_binary_tree(node, key);
    if node is Null then 
       return None;  /* key not found */
     
      if key < node.key:
          return search binary_tree(node.left, key);
      else  
          if key > node.key
              return search_binary_tree(node.right, key)
          else  /* key is equal to node key */
              return node.value;  # found key
Mã Python:
 def search_binary_tree(node, key):
     if node is None:
         return None  # key not found
     if key < node.key:
         return search_binary_tree(node.leftChild, key)
     elif key > node.key:
         return search_binary_tree(node.rightChild, key)
     else:  # key is equal to node key
         return node.value  # found key
Thời gian tìm kiếm trung bình là O(log 2n), và là O(n) khi cây là không cân bằng chỉ là một danh sách liên kết.

Chèn (Insertion)

Phép chèn bắt đầu giống như phép tìm kiếm; Nếu khóa của gốc khác khóa cần chèn ta tìm nó trong cây con trái hoặc phải. Nếu cây con trái hoặc phải tương ứng là rỗng (không tìm thấy) thì thêm một nút và gán cho nút ấy khóa cần chèn.
Sau đây là mã trong C++:
void InsertNode(struct node *&treeNode, struct node *newNode)
{ //Inserts node pointered by "newNode" to the subtree started by "treeNode" 
    if (treeNode == NULL)
        treeNode = newNode; //Only changes "node" when it is NULL
    else if (newNode->value < treeNode->value)
        InsertNode(treeNode->left, newNode);
    else
        InsertNode(treeNode->right, newNode);
}
Mã Python:
 def binary_tree_insert(node, key, value):
     if node is None:
         return TreeNode(None, key, value, None)
 
     if key == node.key:
         return TreeNode(node.left, key, value, node.right)
     if key < node.key:
         return TreeNode(binary_tree_insert(node.left, key, value), node.key, node.value, node.right)
     else:
         return TreeNode(node.left, node.key, node.value, binary_tree_insert(node.right, key, value))

Phép duyệt

Khi một cây tìm kiếm nhị phân được tạo ra, tất cả các nút có thể được duyệt theo thứ tự giữa nhờ duyệt đệ quy cây con bên trái, in nút đang duyệt, rồi duyệt đệ quy cây con bên phải, tiếp tục làm như vây với mỗi nút của cây trong quá trình đệ quy. Với mọi cây nhị phân, cây có thể được duyệt theo thứ tự trước() hoặc theo thứ tự sau(), cả hai cách đều hữu dụng với cây tìm kiếm nhị phân.
Đoạn mã cho duyệt theo thứ giữa được viết dưới đây với C++:
void traverse_binary_tree(struct node* n)
{
   if(n==null)     //Cay rong
       return NULL;
   else
       {
           traverse_binary_tree(n->left);     //Duyet cay con trai theo thu tu giua
           printf("%d",n.key);                //Tham nut
           traverse_binary_tree(n->right);    //Duyet cay con phai theo thu tu giua
       }
}
Phép duyệt có độ phức tạp tính toán là Ω(n), vì nó phải duyệt qua tất cả các nút. Độ phức tạp trên cũng là O("n").

Sắp xếp

Một cây tìm kiếm nhị phân có thể được sử dụng như một giải thuật sắp xếp đơn giản nhưng hiểu quả. Giống như heapsort, chúng ta chèn tất cả các giá trị chúng ta muốn sắp xếp vào một cây tìm kiếm nhị phân và in ra kết quả theo thứ tự:
def build_binary_tree(values):
    tree = None
    for v in values:
        tree = binary_tree_insert(tree, v)
    return treedef get_inorder_traversal(root):
    '''    Returns a list containing all the values in the tree, starting at *root*.    Traverses the tree in-order(leftChild, root, rightChild).    '''
    result = []
    traverse_binary_tree(root, lambda element: result.append(element))
    return result
Trường hợp xấu nhất của build_binary_tree có độ phức tạp là —nếu nhập vào một dãy giá trị đã sắp xếp, cây nhị phân tạo thành sẽ không có các nút trái. Ví dụ, traverse_binary_tree([1, 2, 3, 4, 5]) tạo thành cây (1 (2 (3 (4 (5))))).
Có một vài cách để vượt qua trường hợp này với các cây nhị phân đơn giản; cách đơn giản nhất là cây tìm kiếm nhị phân tự cân bằng. Với thủ tục này được sử dụng với cây nhị phân tự cân bằng, trường hợp xấu nhất sẽ có độ phức tạp là O(nlog n).

Mã giả bằng ngôn ngữ C

#include <conio.h>#include <stdio.h>#include <malloc.h>//Khai bao cay nhi phantypedef char TData;typedef struct TNode{
 TData  Data;
 TNode* left;
 TNode* right;};typedef TNode* TTree;/*=== Tao cay rong ===*/void MakeNull_Tree(TTree *T){
 (*T)=NULL;}/*=== Kiem tra cay rong ===*/int EmptyTree(TTree T){
 return T==NULL;}/*=== Xac dinh con trai ===*/TTree LeftChild(TTree T){
 if(T != NULL)
return T->left;
 else   return NULL;}/*=== Xac dinh con phai ===*/TTree RightChild(TTree T){
 if(T != NULL)
return T->right;
 else   return NULL;}/*=== Xac dinh nut la ===*/int isLeaf(TTree T){
  if((T != NULL) && (T->left == NULL) && (T->right == NULL))
return 1;
  else  return NULL;}/*=== Xac dinh so nut cua cay ===*/int nb_nodes(TTree T){
 if(EmptyTree(T))
return 0;
 else   return nb_nodes(T->left)+nb_nodes(T->right)+1;}// Ham xac dinh gia tri lon nhat trong hai so nguyenint max(int value1,int value2){
return ((value1 > value2) ? value1: value2);    //xac dinh gia tri lon nhat trong 2 gia tri so nguyen}// Ham xac dinh chieu cao cua cayint TreeHeight(TTree T){
int height=0;
if (!EmptyTree(T))
{
if (isLeaf(T))
return 0;
else
height = max(TreeHeight(LeftChild(T)),TreeHeight(RightChild(T)))+1;
}
return height;}// Ham xac dinh so nut la tren cayint nb_leaf(TTree T){
int leaf=0;
if(!EmptyTree(T))
{
if (isLeaf(T))
  leaf++;
else
leaf = nb_leaf(LeftChild(T))+nb_leaf(RightChild(T));
};
return leaf;}/*=== Tao cay moi tu hai cay co san ===*/TTree Create2(TData v,TTree left,TTree right){
  TTree N; // Khai bao 1 cay moi
  N       = (TNode*)malloc(sizeof(TNode)); //Cap phat vung nho cho nut N
  N->Data = v; // Nhan cua nut N la v
  N->left = left; //Con trai cua N la cay left
  N->right = right; //Con phai cua N la cay right
  return N;}/*=== Duyet cay nhi phan ===*///Duyet tien tuvoid NLR(TTree T){
  if(!EmptyTree(T))
  {
   printf(" %c",T->Data); //Xu ly nut
   NLR(LeftChild(T)); //Duyet tien tu con trai
   NLR(RightChild(T)); //Duyet tien tu con phai
  }}//Duyet trung tuvoid LNR(TTree T){
 if(!EmptyTree(T))
 {
  LNR(LeftChild(T)); //Duyet trung tu con trai
  printf(" %c",T->Data);//Xu ly nut
  LNR(RightChild(T));//Duyet trung tu con phai
  }}//Duyet hau tuvoid LRN(TTree T){
 if(!EmptyTree(T))
 {
  LRN(LeftChild(T)); //Duyet hau tu con trai
  LRN(RightChild(T));//Duyet hau tu con phai
  printf(" %c",T->Data);//Xu ly nut
  }}

Các loại cây tìm kiếm nhị phân

Có rất nhiều loại cây tìm kiếm nhị phân. cây AVL và cây đỏ đen đều là các dạng của cây tìm kiếm nhị phân tự cân bằng. () là một cây nhị phân có thể tự đẩy các phần mới vào gần nút gốc. Trong một treap ("cây heap"), mỗi nút có một sự ưu tiên (priority) và các nút cha có sự ưu tiên cao hơn các nút con của chúng.