Cấu trúc dữ liệu - Cây tìm kiếm nhị phân

Cây tìm kiếm nhị phân (BST) là cây trong đó tất cả các nút tuân theo các thuộc tính được đề cập bên dưới:

Giá trị của khóa của cây con bên trái nhỏ hơn giá trị của khóa của nút cha (gốc) của nó.
Giá trị của khóa của cây con bên phải lớn hơn hoặc bằng giá trị của khóa của nút cha (gốc) của nó.

Như vậy, BST chia tất cả các cây con của nó thành hai đoạn; cây con bên trái và cây con bên phải và có thể được định nghĩa là -

left_subtree (keys) < node (key) ≤ right_subtree (keys)

Đại diện

BST là tập hợp các nút được sắp xếp theo cách mà chúng duy trì các thuộc tính của BST. Mỗi nút có một khóa và một giá trị liên quan. Trong khi tìm kiếm, khóa mong muốn được so sánh với các khóa trong BST và nếu được tìm thấy, giá trị liên quan sẽ được truy xuất.

Sau đây là hình ảnh đại diện của BST -

Chúng ta quan sát thấy rằng khóa của nút gốc (27) có tất cả các khóa có giá trị thấp hơn trên cây con bên trái và các khóa có giá trị cao hơn trên cây con bên phải.

Hoạt động cơ bản

Sau đây là các hoạt động cơ bản của cây:

Search - Tìm kiếm một phần tử trong cây.
Insert - Chèn một phần tử trong cây.
Pre-order Traversal - Đi ngang cây theo cách đặt hàng trước.
In-order Traversal - Đi ngang cây theo thứ tự.
Post-order Traversal - Đi ngang cây theo thứ tự có sau.

Nút

Xác định một nút có một số dữ liệu, tham chiếu đến các nút con bên trái và bên phải của nó.

struct node {
   int data;   
   struct node *leftChild;
   struct node *rightChild;
};

Hoạt động tìm kiếm

Bất cứ khi nào một phần tử được tìm kiếm, hãy bắt đầu tìm kiếm từ nút gốc. Sau đó, nếu dữ liệu nhỏ hơn giá trị khóa, hãy tìm kiếm phần tử trong cây con bên trái. Nếu không, hãy tìm kiếm phần tử trong cây con bên phải. Thực hiện theo cùng một thuật toán cho mỗi nút.

Thuật toán

struct node* search(int data){
   struct node *current = root;
   printf("Visiting elements: ");
	
   while(current->data != data){
	
      if(current != NULL) {
         printf("%d ",current->data);
			
         //go to left tree
         if(current->data > data){
            current = current->leftChild;
         }  //else go to right tree
         else {                
            current = current->rightChild;
         }
			
         //not found
         if(current == NULL){
            return NULL;
         }
      }			
   }
   
   return current;
}

Chèn hoạt động

Bất cứ khi nào một phần tử được chèn vào, trước tiên hãy xác định vị trí thích hợp của nó. Bắt đầu tìm kiếm từ nút gốc, sau đó nếu dữ liệu nhỏ hơn giá trị khóa, hãy tìm kiếm vị trí trống trong cây con bên trái và chèn dữ liệu. Nếu không, hãy tìm kiếm vị trí trống trong cây con bên phải và chèn dữ liệu.

Thuật toán

void insert(int data) {
   struct node *tempNode = (struct node*) malloc(sizeof(struct node));
   struct node *current;
   struct node *parent;

   tempNode->data = data;
   tempNode->leftChild = NULL;
   tempNode->rightChild = NULL;

   //if tree is empty
   if(root == NULL) {
      root = tempNode;
   } else {
      current = root;
      parent = NULL;

      while(1) {                
         parent = current;
			
         //go to left of the tree
         if(data < parent->data) {
            current = current->leftChild;                
            //insert to the left
				
            if(current == NULL) {
               parent->leftChild = tempNode;
               return;
            }
         }  //go to right of the tree
         else {
            current = current->rightChild;
            
            //insert to the right
            if(current == NULL) {
               parent->rightChild = tempNode;
               return;
            }
         }
      }            
   }
}