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à một cây trong đó tất cả các nút tuân theo các thuộc tính được đề cập dưới đây -

1. Cây con bên trái của một nút có khóa nhỏ hơn hoặc bằng khóa của nút cha.
2. Cây con bên phải của một nút có khóa lớn hơn khóa của nút cha.

Do đó, BST chia tất cả các cây con của nó thành hai phân đ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 tượng

BST là một tập hợp các nút được sắp xếp theo cách chúng duy trì các thuộc tính 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 tìm thấy, giá trị liên quan được lấy ra.

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

Chúng tôi quan sát rằng khó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 -

1. Tìm kiếm - Tìm kiếm một phần tử trong cây.
2. Chèn - Chèn một phần tử trong cây.
3. Đặt hàng trước Traversal - Đi qua một cây theo cách đặt hàng trước.
4. Theo thứ tự Traversal - Đi ngang qua một cái cây theo thứ tự.
5. Traversal sau khi đặt hàng - Đi qua một cái cây theo cách đặt hàng 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 trái và 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 yếu tố được tìm kiếm, 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, 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 yếu tố được chèn vào, đầu 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, 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;
            }
         }
      }            
   }
}

Được cập nhật: 4 tháng 4 lúc 10:32:29 | Lượt xem: 480