Ninja IT

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

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

Cây tìm kiếm nhị phân là cây với mỗi nút k thì

  • Mỗi khóa trên cây con trái đều nhỏ hơn khóa của nút k
  • Mỗi khóa trên cây con phải đều lớn hơn khóa của nút k

Ví dụ sau là cây tìm kiếm nhị phân với các khóa như sau:

    50
   ↙  ↘
  30   90
  ↙↘   ↙↘
20 40 70 100

Tìm kiếm trên cây nhị phân

Tìm một node trên cậy nhị phân tốn thời gian là O(log(n)). Giải thuật là tìm kiếm nhị phân.

Giải thuật

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

typedef struct Node {
  int key;
  struct Node* left;
  struct Node* right;
} Node;

Node* findInBinarySearchTree(Node* node, int value) {
  if (node == NULL) {
    return NULL;
  }
  if (node->key == value) {
    return node;
  }
  if (value < node->key) {
    return findInBinarySearchTree(node->left, value);
  }
  return findInBinarySearchTree(node->right, value);
}

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

Cây tìm kiếm nhị phân tự cân bằng là cây thỏa mãn hai điều kiện: nó là cây tìm kiếm nhị phân và nó tự cân bằng (sau khi thêm, xóa một phần tử). Cây cân bằng là cây khi chiều cao của hai cây con sai khác nhau không quá 1. Có hai cây tìm kiếm nhị phân tự cân bằng là cây AVL và cây đỏ đen.

Có hai phép toán quan trọng trong cây tìm kiếm nhị phân được cài đặt đó là phép chèn và phép xóa. Thuật toán của hai phép này luôn đảm bảo khi chèn hoặc xóa một node thì cây mới tạo ra sẽ luôn là cây tìm kiếm nhị phân tự cân bằng.

Việc cài đặt cây tìm kiếm nhị phân cân bằng khá phức tạp nên bạn có thể tự cài đặt.