Định nghĩa cây tìm kiếm nhị phân

Cây tìm kiếm nhị phân là cây nhị phân có các thuộc tính sau:

Giá trị phần dữ liệu của mỗi node thuộc cây con bên trái của một node nhỏ hơn giá trị phần dữ liệu của chính node đó.
Giá trị phần dữ liệu của mỗi node thuộc cây con bên phải của một node lớn hơn giá trị phần dữ liệu của chính node đó.

Để cho ngắn gọn, trong bài học này có một số chỗ tôi sẽ sử dụng từ BST (Binary Search Tree) thay cho cây tìm kiếm nhị phân.

Hình 1: Cây tìm kiếm nhị phân

Với chú ý, ở trên hình 1, cả cây con trái và cây con phải cũng là cây tìm kiếm nhị phân.

Xét ví dụ cụ thể của cây tìm kiếm nhị phân như sau, với phần dữ liệu của các node là số nguyên.

Hình 2: Cây tìm kiếm nhị phân giá trị nguyên

Như vậy cây tìm kiếm nhị phân là một trường hợp đặc biệt của cây nhị phân, và nó có cấu trúc tối ưu cho việc tìm kiếm cũng như cập nhật dữ liệu một cách nhanh chóng.

Ta cùng so sánh độ phức tạp về thời gian của các loại cấu trúc dữ liệu như sau.

	Mảng (chưa sắp xếp)	Danh sách liên kết	Mảng (đã sắp xếp)	Cây tìm kiếm nhị phân (cân bằng)
Search()	O(n)	O(n)	O(logn)	O(logn)
Insert()	O(1)	O(1)	O(n)	O(logn)
Remove()	O(n)	O(n)	O(n)	O(logn)

Cấu trúc của một node trong BST

struct node {
	int key;
	struct node *left;
	struct node *right;
};

Các thao tác cơ bản với cây nhị phân tìm kiếm

Các thao tác cơ bản với cây nhị phân tìm kiếm bao gồm:

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

* Insert: Chèn một phần tử vào cây.

* Delete: Xóa một phần tử khỏi cây tìm kiếm.

* Duyệt cây theo:

Chiều sâu:

– Preoder travesal

– Inorder traversal

– Postorder traversal

Chiều rộng:

– Level order traversal

Các thao tác duyệt của cây tìm kiếm nhị phân là hoàn hoàn giống với cây nhị phân bao gồm duyệt cây theo chiều rộng và duyệt cây theo chiều sâu. Nên trong bài học này ta sẽ chỉ xét tới các thao tác còn lại.

Thao tác tìm kiếm trong BST

Thao tác tìm kiếm trong cây tìm kiếm nhị phân được mô tả trong hình sau:

Hình 3: Tìm kiếm trong BST

Trong ví dụ trên, ta muốn tìm kiếm node có giá trị bằng 22.

Bước 1: Bắt đầu từ node gốc có giá trị bằng 30. Do 22 < 30 nên node cần tìm sẽ nằm bên phía cây con bên trái của node gốc.

Bước 2: Ở node gốc của cây con bên trái có giá trị bằng 20, do 22> 20. Nên node cần tìm sẽ nằm bên phải của cây con này, ta sẽ tiếp tục duyệt nhánh bên phải của nó.

Bước 3: Node tiếp theo có giá trị bằng 24, do 22 < 24 nên node cần tìm sẽ nằm ở nhánh trái của node này.

Bước 4: Khi duyệt đến node tiếp theo ta gặp node lá, và node này có giá trị bằng 22, nên ta thu được node cần tìm trong cây.

Mã nguồn thực hiện việc tìm kiếm trên cây tìm kiếm nhị phân BST:


/* Hàm tìm kiếm một phần tử trong cây BST */
struct node* search(struct node* root, int key)
{
    /* Base Cases: Node gốc là NULL hoặc giá trị của node gốc bằng với key */
    if (root == NULL || root->key == key)
       return root;
   
    /* Nếu giá trị cần tìm lớn hơn giá trị của node gốc
        Ta gọi đệ quy hàm tìm kiếm cho nhánh phải của node gốc */
    if (root->key < key)
       return search(root->right, key);

    /* Nếu giá trị cần tìm nhỏ hơn giá trị của node gốc
        Ta gọi đệ quy hàm tìm kiếm cho nhánh trái của node gốc */
    return search(root->left, key);
}

Thêm phần tử vào cây tìm kiếm nhị phân

Quá trình thêm phần tử vào BST khá giống với quá trình tìm kiếm một phần tử trong cây.

Hình dưới đây mô tả quá trình thêm một node vào trong cây tìm kiếm nhị phân.

Hình 4: Thêm phần tử vào cây tìm kiếm nhị phân

Gọi phần tử cần được thêm vào là key. Phần tử mới luôn luôn được thêm vào tại node lá. Ta thực hiện tìm kiếm key bắt đầu từ node gốc cho đến khi ta gặp node lá. Một khi node lá được tìm thấy. Node mới sẽ được thêm vào như là con của node lá.

Mã nguồn thực hiện việc thêm phần tử vào cây BST


/* Hàm tiện ích giúp tạo BST node */
struct node *newNode(int item)
{
    struct node *temp =  (struct node *)malloc(sizeof(struct node));
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}

/* Hàm chèn một phần tử mới vào cây BST */
struct node* Insert(struct node* node, int key)
{
    /* Nếu cây là rỗng, trả về một node mới */
    if (node == NULL) return newNode(key);
 
    /* Ngược lại, gọi đệ quy tới các con trong cây */
    if (key < node->key)
        node->left  = Insert(node->left, key);
    else if (key > node->key)
        node->right = Insert(node->right, key);   
 
    return node;
}

Độ phức tạp thời gian: O(H) với H là chiều cao của cây, và Hmax = N, và N là số các node trong cây.

Xóa một phần tử khỏi cây tìm kiếm nhị phân

Khi ta xóa một phần tử khỏi cây tìm kiếm nhị phân, có thể có 3 trường hợp xảy ra: Node bị xóa là node lá (không có con), node bị xóa có một con, hoặc node bị xóa có hai node con.

Việc xóa một phần tử ra khỏi một BST sẽ càng phức tạp nếu node đó có càng nhiều con.

Trường hợp 1: Xóa node lá ra khỏi một BST

Hình 5: Xóa node lá ra khỏi một BST

Xóa node lá ra khỏi một BST là trường hợp xóa node đơn giản nhất, ta chỉ cần tìm tới node đó và xóa nó ra khỏi cây.

Mã nguồn thực hiện

if(root->left == NULL && root->right == NULL) 
{ 		
        delete root;		
        root = NULL;		
}

Trường hợp 2: Node được xóa có một con

Hình 6: Xóa node có một con khỏi BST

Để xóa node có một con ra khỏi BST ta phải giải phóng bộ nhớ của node đó, xóa liên kết với con và cha, tạo liên kết từ node cha trực tiếp tới node code của nó.

Mã nguồn thực hiện:


if(root->left == NULL && root->right != NULL) 
{
	struct node *temp = root;
	root = root->right;
	delete temp;
}else if(root->right == NULL && root->left != NULL)
{
	struct node *temp = root;
	root = root->left;
	delete temp;
}

Trường hợp 3: Node được xóa có hai con

Trong hình phía dưới. Giả sử như node có giá trị bằng 30 được xóa ra khỏi cây. Lúc này để duy trì các quy tắc của cây tìm kiếm nhị phân, 24 là node có giá trị lớn nhất trong cây con trái hoặc 34 là node nhỏ nhất trong cây con phải của 30 sẽ được chon để thay thế cho 30.

Hình 7: Xóa node có hai con khỏi BST

Nếu 24 được chọn để thay thế cho 30. Trong trường hợp này, các quy tắc của BST được giữ nguyên. Tuy vậy, node 24 lúc này bị chuyển chỗ, node 22 mất kết nối tới cha của nó.

Hình 8: Node có giá trị lớn nhất của cây bên con trái được chon thay cho node đã được xóa khỏi BST

Do vậy để hoàn thành quá trình xóa node ta phải thiết lập 22 lúc này làm con phải của 20.

Hình 9: Thiết lập con mới

Mã nguồn hoàn thiện của chương trình với BST

#include <iostream>
using namespace std;

struct node {
	int key;
	struct node *left;
	struct node *right;
};

/* Hàm tìm kiếm một phần tử trong cây BST */
struct node* search(struct node* root, int key)
{
    /* Base Cases: Node gốc là NULL hoặc giá trị của node gốc bằng với key */
    if (root == NULL || root->key == key)
       return root;
   
    /* Nếu giá trị cần tìm lớn hơn giá trị của node gốc
        Ta gọi đệ quy hàm tìm kiếm cho nhánh phải của node gốc */
    if (root->key < key)
       return search(root->right, key);

    /* Nếu giá trị cần tìm nhỏ hơn giá trị của node gốc
        Ta gọi đệ quy hàm tìm kiếm cho nhánh trái của node gốc */
    return search(root->left, key);
}

/* Hàm tiện ích giúp tạo BST node */
struct node *newNode(int item)
{
    struct node *temp =  (struct node *)malloc(sizeof(struct node));
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}

/* Hàm chèn một phần tử mới vào cây BST */
struct node* Insert(struct node* node, int key)
{
    /* Nếu cây là rỗng, trả về một node mới */
    if (node == NULL) return newNode(key);
 
    /* Ngược lại, gọi đệ quy tới các con trong cây */
    if (key < node->key)
        node->left  = Insert(node->left, key);
    else if (key > node->key)
        node->right = Insert(node->right, key);   
 
    return node;
}

/* Hàm tìm giá trị lớn nhất trong cây */ 
node* FindMax(node* root)
{
	while(root->right != NULL) root = root->right;
	return root;
}

/* Hàm xóa một node khỏi BST */
struct node* Delete(struct node *root, int key) {
	if(root == NULL) return root; 
	else if(key < root->key) root->left = Delete(root->left,key);
	else if (key > root->key) root->right = Delete(root->right,key);
	else {
		/* Case 1:  Node lá, không có con */
		if(root->left == NULL && root->right == NULL) { 
			delete root;
			root = NULL;
		}
		/* Case 2: Có một con  */
		else if(root->left == NULL) {
			struct node *temp = root;
			root = root->right;
			delete temp;
		}
		else if(root->right == NULL) {
			struct node *temp = root;
			root = root->left;
			delete temp;
		}
		/* case 3: Có hai con */
		else { 
			struct node *temp = FindMax(root->left);
			root->key = temp->key;
			root->left = Delete(root->left,temp->key);
		}
	}
	return root;
}

/* hàm duyệt cây theo thứu tự Inorder */
void Inorder(struct node *root) {
	if(root == NULL) return;
 
	Inorder(root->left);       /* Duyệt cây con bên trái */
	printf("%d ",root->key);   /* In ra key */
	Inorder(root->right);      /* Duyệt cây con bên phải */
}

/* Hàm in ra tất cả các node theo thứ tự Inorder */
void printBST(struct node *root){
	cout<<"Inorder: ";
	Inorder(root);
	cout<<"n";
}
int main()
{
	/*Code To Test the logic
	  Creating an example tree
	            5
			   / 
			  3   10
			 /    
			1   4   11
    */
    struct node* root = NULL;
    
    root = Insert(root,5); root = Insert(root,10);
	root = Insert(root,3); root = Insert(root,4); 
	root = Insert(root,1); root = Insert(root,11);
	/* In ra tất cả các node theo thứ tự Inorder */
	printBST(root);
	
	root = Delete(root,5);
	/* In ra tất cả các node theo thứ tự Inorder */
	printBST(root);

    return 0;
}

Mã nguồn của toàn bộ chương trình thao tác với BST cũng có thể tìm thấy trên đường dẫn gitlab sau:

https://gitlab.com/thevngeek/basic-data-structure/blob/master/caytimkiemnhiphan.cpp

Tham khảo

1. http://www.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion/

2. https://gist.github.com/mycodeschool/9465a188248b624afdbf

Uncategorized

Cây tìm kiếm nhị phân