Giới thiệu Mở đầu Mảng và bé trỏ Mảng tĩnh Mảng động bé trỏ Sơ đồ bộ lưu trữ trong các chương trình C Danh sách liên kết cấp phép động Danh sách liên kết đơn Danh sách liên kết kép Cây nhị phân Khái niệm cấu trúc dữ liệu dạng cây Cây nhị phân chăm sóc cây theo chiều rộng Duyệt cây theo chiều sâu Cây tìm kiếm nhị phân Cây tìm kiếm nhị phân Cây cân nặng bằng - AVL Tree Cây cân bằng ngăn xếp ngăn xếp Hàng đợi Hàng đợi

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

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

Giá trị phần dữ liệu của mỗi node trực thuộc cây bé bên trái của một node nhỏ tuổi hơn quý hiếm phần tài liệu của chính node đó.Giá trị phần tài liệu của mỗi node trực thuộc cây con bên phải của một node to hơn giá trị phần tài liệu của chủ yếu node đó.

Bạn đang xem: Chi tiết bài học cây tìm kiếm nhị phân

Để đến ngắn gọn, trong bài học này có một trong những chỗ tôi sẽ thực hiện từ BST (Binary tìm kiếm Tree) chũm cho cây tìm kiếm kiếm nhị phân.

*

Hình 1: Cây tìm kiếm nhị phân

Với chú ý, ở trên hình 1, cả cây nhỏ trái và cây con phải cũng là cây tìm kiếm nhị phân.

Xét ví dụ cụ thể của cây tìm kiếm nhị phân như sau, với phần dữ liệu của các node là số nguyên.

*

Hình 2: Cây tìm kiếm nhị phân giá trị nguyên

Như vậy cây tìm kiếm nhị phân là một trường hợp đặc biệt của cây nhị phân, và nó có cấu trúc tối ưu mang đến việc tìm kiếm cũng như cập nhật dữ liệu một cách cấp tốc chóng.

Ta cùng so sánh độ phức tạp về thời gian của các loại cấu trúc dữ liệu như sau.

Mảng (chưa sắp xếp)

Danh sách liên kết

Mảng (đã sắp xếp)

Cây tìm kiếm nhị 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 trúc của một node trong BST

struct node int key;struct node *left;struct node *right;;Các thao tác cơ bạn dạng với cây nhị phân tìm kiếmCác thao tác làm việc cơ bản với cây nhị phân kiếm tìm kiếm gồm những:

* Search: search kiếm một trong những phần tử trên cây.

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

* Delete: Xóa một trong những phần tử khỏi cây search kiếm.

* chuẩn y cây theo:

Chiều sâu:

- Preoder travesal

- Inorder traversal

- Postorder traversal

Chiều rộng:

- màn chơi order traversal

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

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

Thao tác tra cứu kiếm trong cây search kiếm nhị phân được bộc lộ trong hình sau:

*

Hình 3: tìm kiếm kiếm vào BST

Trong ví dụ trên, ta mong mỏi tìm kiếm node có giá trị bởi 22.

Bước 1: bước đầu từ node gốc có giá trị bởi 30. Vì 22

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

Bước 3: Node tiếp sau có giá trị bởi 24, vì 22

Bước 4: khi duyệt mang lại node tiếp sau ta chạm mặt node lá, và node này còn có giá trị bằng 22, nên ta nhận được node nên tìm vào cây.

Mã nguồn thực hiện việc tìm kiếm bên trên cây tìm kiếm nhị phân BST:

/* Hàm tìm kiếm một phần tử trong cây BST */struct node* search(struct node* root, int key)

Thêm phần tử vào cây tìm kiếm nhị phân

Quá trình thêm phần tử vào BST khá giống với quá trình tìm kiếm một phần tử vào cây.

Hình dưới trên đây mô tả quá trình thêm một node vào trong cây tìm kiếm nhị phân.

*

Hình 4: Thêm phần tử vào cây tìm kiếm nhị phân

Gọi phần tử cần được thêm vào là key. Phần tử mới luôn luôn luôn được thêm vào tại node lá. Ta thực hiện tìm kiếm key bắt đầu từ node gốc cho đến lúc ta gặp node lá. Một khi node lá được tìm thấy. Node mới sẽ được thêm vào như là bé của node lá.

Mã nguồn thực hiện việc thêm phần tử vào cây BST

/* Hàm tiện ích giúp tạ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;/* Hàm chèn một phần tử mới vào cây BST */struct node* Insert(struct node* node, int key) /* Nếu cây là rỗng, trả về một node mới */ if (node == NULL) return newNode(key); /* Ngược lại, gọi đệ quy tới các bé trong cây */ if (key key) node->left = Insert(node->left, key); else if (key > node->key) node->right = Insert(node->right, key); return node;Độ phức tạp thời gian: O(H) với H là chiều cao của cây, và Hmax = N, và N là số các node trong cây.

Xóa một trong những phần tử ngoài cây search kiếm nhị phân

Khi ta xóa một trong những phần tử ngoài cây tìm kiếm kiếm nhị phân, hoàn toàn có thể có 3 trường đúng theo xảy ra: Node bị xóa là node lá (không tất cả con), node bị xóa bao gồm một con, hoặc node bị xóa gồm 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 đó gồm càng các con.

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

*

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

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

Mã mối cung cấp thực hiện

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

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

*

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

Để xóa node tất cả một con ra khỏi BST ta buộc phải giải phóng bộ nhớ của node đó, xóa liên kết với nhỏ và cha, tạo link từ node phụ thân trực tiếp cho 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 thích hợp 3: Node được xóa có hai con

Trong hình phía dưới. Mang sử như node có mức giá trị bởi 30 được xóa ra khỏi cây. Bây giờ để gia hạn các phép tắc của cây kiếm tìm kiếm nhị phân, 24 là node có mức giá trị lớn nhất trong cây bé trái hoặc 34 là node nhỏ nhất vào cây con đề nghị của 30 sẽ được chon để sửa chữa cho 30.

*

Hình 7: Xóa node bao gồm hai bé khỏi BST

Nếu 24 được lựa chọn để thay thế sửa chữa cho 30. Vào trường hợp này, các quy tắc của BST được duy trì nguyên. Tuy vậy, node 24 bây giờ bị chuyển chỗ, node 22 mất liên kết tới thân phụ của nó.

Xem thêm: Đề Thi Học Kì 1 Môn Vật Lý Lớp 12 Ôn Thi Học Kì 1 Có Đáp Án, Đề Thi Học Kì 1 Lớp 12 Môn Lý

*

Hình 8: Node có mức giá trị lớn nhất của cây bên nhỏ trái được chon gắng cho node vẫn được xóa bỏ BST

Do vậy để xong xuôi quá trình xóa node ta phải tùy chỉnh thiết lập 22 lúc này làm con nên của 20.

*

Hình 9: tùy chỉnh con bắt đầu

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

#include using namespace std;struct node int key;struct node *left;struct node *right;;/* Hàm tìm kiếm một phần tử vào cây BST */struct node* search(struct node* root, int key)/* Hàm tiện ích giúp tạ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;/* Hàm chèn một phần tử mới vào cây BST */struct node* Insert(struct node* node, int key) /* Nếu cây là rỗng, trả về một node mới */ if (node == NULL) return newNode(key); /* Ngược lại, gọi đệ quy tới các bé trong cây */ if (key 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á chỉ trị lớn số 1 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 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: tất 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: tất cả hai bé */else struct node *temp = FindMax(root->left);root->key = temp->key;root->left = Delete(root->left,temp->key);return root;/* hàm thông qua cây theo thứu trường đoản cú Inorder */void Inorder(struct node *root) if(root == NULL) return; Inorder(root->left); /* để mắt cây bé bên trái */printf("%d ",root->key); /* In ra key */Inorder(root->right); /* duyệt y cây con bên bắt buộc *//* Hàm in ra toàn bộ các node theo máy tự Inorder */void printBST(struct node *root){coutMã nguồn của toàn bộ chương trình làm việc với BST cũng hoàn toàn 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/