Bài 31 - Cấu trúc dữ liệu cây

Tree Data Structure

Cây (tree) đại diện cho các nút được kết nối bởi các cạnh. Chúng ta sẽ thảo luận cụ thể về cây nhị phân hoặc cây tìm kiếm nhị phân.

Cây nhị phân là một cấu trúc dữ liệu đặc biệt được sử dụng cho mục đích lưu trữ dữ liệu.  Cây nhị phân có một điều kiện đặc biệt là mỗi nút có thể có tối đa hai con. Một cây nhị phân tận dụng lợi thế của hai kiểu cấu trúc dữ liệu: một mảng đã sắp thứ tự và một danh sách liên kết (Linked List), do đó việc tìm kiếm sẽ nhanh như trong mảng đã sắp thứ tự và các thao tác chèn và xóa cũng sẽ nhanh bằng trong Linked List.

Các khái niệm cơ bản về cây nhị phân

Dưới đây là một số khái niệm quan trọng liên quan tới cây nhị phân:

• Path (Đường dẫn): là một dãy các nút cùng với các cạnh của một cây.
• Root (Nút gốc): Nút trên cùng của cây gọi là nút gốc. Một cây sẽ chỉ có một nút gốc và một đường xuất phát từ nút gốc tới bất kỳ nút nào khác.
• Nút cha: bất kỳ nút nào ngoại trừ nút gốc mà có một cạnh hướng lên một nút khác thì được gọi là nút cha.
• Nút con: nút ở dưới một nút đã cho được kết nối bởi cạnh dưới của nó được gọi là nút con của nút đó.
• Nút lá: nút mà không có bất kỳ nút con nào thì được gọi là nút lá.
• Cây con: cây con biểu diễn các con của một nút.
• Truy cập: kiểm tra giá trị của một nút khi điều khiển là đang trên một nút đó.
• Duyệt: duyệt qua các nút theo một thứ tự nào đó.
• Bậc: bậc của một nút biểu diễn số con của một nút. Nếu nút gốc có bậc là 0, thì nút con tiếp theo sẽ có bậc là 1, và nút cháu của nó sẽ có bậc là 2, …
• Khóa (Key): biểu diễn một giá trị của một nút dựa trên những gì mà một thao tác tìm kiếm thực hiện trên nút.

Biểu diễn cây tìm kiếm nhị phân

Cây tìm kiếm nhị phân biểu diễn một hành vi đặc biệt. Con bên trái của một nút phải có giá trị nhỏ hơn giá trị của nút cha (của nút con này) và con bên phải của nút phải có giá trị lớn hơn giá trị của nút cha (của nút con này). Hình minh họa:

Chúng ta đang triển khai cây bởi sử dụng đối tượng nút và kết nối chúng thông qua các tham chiếu.

Nút (Node) trong cây tìm kiếm nhị phân

Một nút sẽ có cấu trúc như dưới đây. Nút có phần dữ liệu và phần tham chiếu tới các nút con bên trái và nút con bên phải.

struct node {

   int data;  

   struct node *leftChild;

   struct node *rightChild;

};

Hoạt động cơ bản trên cây tìm kiếm nhị phân

Dưới đây liệt kê các hoạt động cơ bản có thể được thực hiện trên cấu trúc dữ liệu cây tìm kiếm nhị phân:

• Chèn: chèn một phần tử vào trong một cây/ tạo một cây.
• Tìm kiếm: tìm kiếm một phần tử trong một cây.
• Duyệt tiền thứ tự: duyệt một cây theo cách thức duyệt tiền thứ tự.
• Duyệt trung thứ tự: duyệt một cây theo cách thức duyệt trung thứ tự.
• Duyệt hậu thứ tự: duyệt một cây theo cách thức duyệt hậu thứ tự.

Chúng ta sẽ tìm hiểu chi tiết cách tạo (chèn) cấu trúc cây và cách tìm kiếm một phần tử dữ liệu trên một cây. Chương sau chúng ta sẽ tìm hiểu chi tiết về các cách duyệt cây.

Hoạt động chèn trong cây tìm kiếm nhị phân

Bước chèn đầu tiên sẽ tạo thành cây. Tiếp đó là sẽ chèn từng phần tử vào trong cây. Đầu tiên chúng ta cần xác định vị trí chính xác của nó. Bắt đầu tìm kiếm từ nút gốc, sau đó nếu dữ liệu là nhỏ hơn giá trị khóa, thì tìm kiếm vị trí rỗng trong cây con bên trái và chèn dữ liệu. Nếu không nhỏ hơn, tìm vị trí rỗng trong cây con bên phải và chèn dữ liệu. (Nếu bạn chưa hiểu, bạn có thể đọc lại phần Biểu diễn cây tìm kiếm nhị phân ở trên để biết tại sao lại chèn như vậy và xem hình minh họa)

Thuật toán

If root is NULL

   then create root node

return

If root exists then

   compare the data with node.data 

   while until insertion position is located

      If data is greater than node.data

         goto right subtree

      else

         goto left subtree

   endwhile   

   insert data    

end If     

Thực hiện

Việc thực hiện chức năng chèn sẽ như thế này -

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, create root node

   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;

            }

         }

      }           

   }

}

Hoạt động tìm kiếm trong cây nhị phân

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, 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

If root.data is equal to search.data

   return root

else

   while data not found

      If data is greater than node.data

         goto right subtree

      else

         goto left subtree      

      If data found

         return node

   endwhile   

   return data not found

end if     

Việc thực hiện thuật toán này sẽ giống như thế này.

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;

   } 

}

- Hiếu Kiều -