Lập trình CLập trình C++

Các thuật toán thao tác cơ bản trên cây nhị phân tìm kiếm trong C/C++

Cây nhị phân tìm kiếm (Binary Search Tree – BST) là một cấu trúc khá phổ biến và vô cùng quan trọng đối với ngôn ngữ lập trình C/C++. Vì vậy trong bài viết này, Isinhvien sẽ chia sẻ đến các bạn các thuật toán thao tác cơ bản trên cây nhị phân tìm kiếm: Duyệt cây theo thứ tự, tìm kiếm một phần tử trên cây, thêm một phần tử trên cây, xóa một phần tử trên cây, tạo và xóa cây nhị phân tìm kiếm. Trước khi đi vào bài này thì hãy chắc rằng bạn đã nắm rõ về các khái niệm của cây và cây nhị phân tìm kiếm. Nếu chưa thì hãy tham khảo qua bài viết Tất tần tật về cây trong ngôn ngữ lập trình của Isinhvien nhé!

Duyệt cây theo thứ tự

Thao tác duyệt cây trên cây nhị phân tìm kiếm hoàn toàn giống như trên cây nhị phân. Đặc biệt là khi duyệt theo thứ tự giữa, trình tự các nút duyệt qua sẽ cho ta một dãy các nút theo thứ tự tăng dần của khóa.


Hàm duyệt cây:

void  DuyetGiua(Tree  T)   {
      if  (T != NULL)    
      {  DuyetGiua( (*T).left );
         cout << (*T).key << " ";
         DuyetGiua( (*T).right );    
      }   
}   
Cây nhị phân tìm kiếm
Cây nhị phân tìm kiếm

Sau khi duyệt cây nhị phân trên sẽ cho ra kết quả sau:

1 2 3 4 5 6 7 8 9

Tìm kiếm một phần tử trên cây

Giả sử ta cần tìm kiếm một phân tử có giá trị x, ta có thể thực hiện như sau

Hàm tìm một phần tử trên cây:

TNODE *searchNode(TREE T, Data X) 
{ 
      if (T) { 
          if ( T -> Key == X) return T; 
          if (T -> Key > X) return searchNode( T -> Left, X); 
          else return searchNode(T-> Right, X);
      }  
return NULL; 
}

Ta cũng có thể xây dựng một hàm tìm kiếm không đệ quy như sau:


TNODE * searchNode(TREE Root, Data x) 
{ 
   NODE *p = Root; 
   while (p != NULL) { 
        if(x == p->Key) return p; 
        else if(x < p->Key) p = p-> Left; 
        else p = p-> Right; 
   } 
return NULL; 
}

Thêm một phần tử vào cây

Việc thêm một phần tử X vào cây phải bảo đảm điều kiện ràng buộc của BST. Ta có thể thêm vào nhiều chỗ khác nhau trên cây, nhưng nếu thêm vào một nút lá sẽ là tiện lợi nhất do ta có thể thực hiên quá trình tương tự như thao tác tìm kiếm. Khi chấm dứt quá trình tìm kiếm cũng chính là lúc tìm được chỗ cần thêm. Hàm insert sẽ trả về giá trị –1, 0, 1 khi không đủ bộ nhớ, gặp nút cũ hay thành công.

Hàm thêm một phần tử vào cây

int insertNode(TREE &T, Data X) 
{
    if(T) { 
       if(T->Key == X) return 0; //đã có 
       if(T->Key > X) return insertNode(T-> Left, X); 
       else return insertNode(T-> Right, X); 
     } 
     T =new Tnode; 
     if(T == NULL) return -1; //thiếu bộ nhớ 
     T-> Key = X; 
     T-> Left = NULL;
     T-> Right = NULL;
     return 1; //thêm vào thành công 
}

Xóa một phần tử trên cây

Việc hủy một phần tử ra khỏi cây phải đảm bảo điều kiện ràng buộc của cây nhị phân tìm kiếm Có 3 trường hợp khi hủy nút X có thể xảy ra:


  • X là nút lá: chỉ đơn giản hủy X vì nó không móc nối đến phần tử nào khác
  • X chỉ có 1 con (trái hoặc phải): trước khi hủy X ta móc nối cha của X với con duy nhất của nó
  • X có đủ cả 2 con: ta không thể hủy trực tiếp do X có đủ 2 con. Do đó, ta sẽ hủy gián tiếp. Thay vì hủy X, ta sẽ tìm một phần tử thế mạng Y. Phần tử này có tối đa một con. Thông tin lưu tại Y sẽ được chuyển lên lưu tại X. Sau đó, nút bị hủy thật sự sẽ là Y giống như 2 trường hợp đầu. Vấn đề là phải chọn Y sao cho khi lưu Y vào vị trí của X, cây vẫn là CNPTK. Ta có thể chọn 1 trong 2 phần tử: Phần tử nhỏ nhất trên cây con phải hoặc phần tử lớn nhất trên cây con trái.

Việc chọn lựa phần tử nào là phần tử thế mạng hoàn toàn phụ thuộc vào ý thích của ngƣời lập trình. Ở đây, chúng ta sẽ chọn phần tử lớn nhất trên cây con trái làm phần tử thế mạng.


Hàm delNode trả về giá trị 1 khi hủy thành công hoặc o nếu không có X trong cây.

int delNode(TREE &T, Data X) 
{ 
   if(T==NULL) return 0; 
   if(T->Key > X) return delNode (T->Left, X); 
   if(T->Key < X) return delNode (T->Right, X); 
   else { //T->Key == X 
     TNode* p = T; 
     if (T->Left == NULL) T = T->Right; 
     else if (T->Right == NULL) T = T->Left; 
     else { //T có cả 2 con 
        TNode* q = T->Right; 
        searchStandFor(p, q);
     } delete p; 
   } 
}

Trong đó hàm searchStandFor dùng để tìm phần tử thế mạng cho nút p, được viết như sau:

void searchStandFor(TREE &p, TREE &q) 
{ 
    if(q->Left) searchStandFor(p, q->Left); 
    else { 
      p->Key = q->Key;
      p = q; q = q->Right; 
    } 
}

Tạo và xóa cây nhị phân tìm kiếm

Tạo cây nhị phân


Để tạo một cây nhị phân tìm kiếm, ta có thể lặp lại quá trình thêm một phần tử vào một cây rỗng.

Xóa toàn bộ cây

Việc xóa toàn bộ cây có thể được thực hiện thông qua thao tác duyệt cây theo thứ tự sau. Nghĩa là ta sẽ hủy cây con trái, cây con phải rồi mới hủy nút gốc.

void removeTree(TREE &T) 
{
   if(T) { 
      removeTree(T->Left); 
      removeTree(T->Right); 
      delete(T); 
   }
}

Isinhvien hy vọng sau bài viết này sẽ giúp các bạn hiểu hơn về thuật toán của những thao tác trên cây nhị phân này và có thể áp dụng nó cho việc học tập cũng như công việc của mình. Đừng quên theo dõi Isinhvien để cập nhật các kiến thức bổ ích mỗi ngày nhé! Chúc các bạn thật nhiều sức khỏe và gặt hái được nhiều thành công trong cuộc sống!

Mới nhất cùng chuyên mục

Back to top button
Close