1. Đặc điểm của cây nhị phân kiếm tìm kiếm

Cây nhị phân kiếm tìm kiếm (Binary tìm kiếm Tree) là 1 trong cây nhị phân bao gồm đặc điểm:Tất cả những nút trong cây con bên trái tàng trữ giá trị bé dại hơn nút đang xétTất cả các nút vào cây bé bên phải lưu trữ giá trị lớn hơn nút đã xét

*
Cây phía trái là cây nhị phân kiếm tìm kiếm, cây bên phải không thỏa ràng buộc cây nhị phân kiếm tìm kiếm
Nhờ trật tự bố trí các nút bên trên cây giúp triết lý việc search kiếm các nút vào cây. Cũng chính vì thế cơ mà nó được call là cây nhị phân search kiếm.

Bạn đang xem: Binary search tree là gì

2. Màn biểu diễn cây nhị phân tra cứu kiếm

Chúng ta có thể sử dụng danh sách liên kết để màn trình diễn cây nhị phân search kiếm. Đầu tiên, nên định nghĩa một nút trong cấu tạo dữ liệu dạng cây.struct tNodeint data;tNode *pLeft, *pRight;;Dữ liệu (data) tàng trữ trong nút của cây nhị phân kiếm tìm kiếm phải là dữ liệu hoàn toàn có thể so sánh giá chỉ trị bé dại hơn hoặc to hơn giữa những nút trong cây.Để tàng trữ cây, bọn họ chỉ cần xác định nút nơi bắt đầu của cây.tNode *root;Tạo một cây rỗngvoid CreateEmptyTree()root = NULL;Tạo một nút lưu giá trị xtNode *newNode(int data)tNode *node = new tNode;if(node==NULL)//cannot allocate memoryexit(1);elsenode->data = data;node->pLeft = NULL;node->pRight = NULL;return node;

3. Các làm việc cơ bản trên cây nhị phân search kiếm

Các thao tác trên cây nhị phân tìm kiếm như duyệt cây, thêm 1 nút vào cây, diệt một nút vào cây, search kiếm một nút trong cây,Duyệt câyCách duyệt giống hệt như cây nhị phân bình thường với 3 vẻ bên ngoài duyệt đó là NLR, LNR, LRN.Tìm một nút trong câyNhờ vào điểm sáng của cây nhị phân tra cứu kiếm mà việc tìm kiếm nút tiện lợi hơn. Có thể dùng đệ quy hoặc không sử dụng đệ quy nhằm tìm một nút vào cây nhị phân tìm kiếm.Sử dụng đệ quytNode *searchNodeByRecursion(tNode *root, int x)if(root != NULL )if(root->data == x)return root;if(root->data > x)return searchNodeByRecursion(root->pLeft,x);elsereturn searchNodeByRecursion(root->pRight,x);return NULL;Không thực hiện đệ quytNode *searchNodeWithoutRecursion(tNode *root, int x)tNode *p=root;while(p != NULL)if(p->data == x)return p;else if(p->data > x)p = p->pLeft;elsep = p->pRight;return NULL;Thêm một nút vào câySau lúc thêm nút vào cây thì đảm bảo vẫn là cây nhị phân tra cứu kiếm. Giữ ý, không thêm nút lưu quý giá đã gồm trong cây.tNode *insertNode(tNode *node, int value)if(node!=NULL)if(node->data == value)return node;else if(node->data > value)node->pLeft = insertNode(node->pLeft, value);elsenode->pRight = insertNode(node->pRight, value);elsenode = newNode(value);return node;Hủy một nút lưu quý giá x trong câyKhi hủy 1 nút phải bảo đảm an toàn điều kiện ràng buộc của cây nhị phân search kiếm.Có 3 trường hòa hợp khi hủy 1 nút bên trên cây:Trường hòa hợp 1: x là nút lá. Diệt nút lá nhưng không ảnh hưởng đến các nút khác trên cây.Trường hợp 2: x chỉ có một cây nhỏ (cây con trái hoặc cây bé phải). Trước lúc hủy x, ta link nút phụ vương của x với nhỏ duy duy nhất của x.Trường hợp 3: x có tương đối đầy đủ 2 cây con. Thực hiện các bước sau nhằm hủy x:Bước 1: tra cứu nút y nỗ lực mạng đến nút x, có 2 cách tìm:Cách 1: y là phần tử nhỏ tuổi nhất (trái nhất) trên cây nhỏ phải.Cách 2: y là bộ phận lớn nhất (phải nhất) trên cây bé trái.Bước 2: Lưu thông tin của y vào x.

Xem thêm: Tam Giác Đều Là Gì ? Định Nghĩa, Tính Chất Về Tam Giác Đều Chi Tiết

Bước 3: diệt y (giống như diệt nút lá).tNode *minValueNode(tNode *node)tNode *current = node;while(current && current->pLeft != NULL)current = current->pLeft;return current;tNode *deleteNode(tNode *root, int x)if(root == NULL)return root;if(root->data > x)root->pLeft = deleteNode(root->pLeft, x);else if(root->data pRight = deleteNode(root->pRight, x);elsetNode *p = root;if(root->pLeft == NULL)root=root->pRight;delete p;else if(root->pRight== NULL)root=root->pLeft;delete p;elsetNode *temp = minValueNode(root->pRight);root->data = temp->data;root->pRight = deleteNode(root->pRight, temp->data);return root;}

4. Ví dụ công tác C++ làm việc với cây nhị phân tìm kiếm

Cho cây nhị phân kiếm tìm kiếm như hình bên dưới.
*

Chương trình C++ thao tác với cây nhị phân tìm kiếm như hình trên#include using namespace std;struct tNodeint data;tNode *pLeft, *pRight;;tNode *root;//create empty treevoid createEmptyTree()root = NULL;//create new nodetNode *newNode(int data)tNode *node = new tNode;if(node==NULL)//cannot allocate memoryexit(1);elsenode->data = data;node->pLeft = NULL;node->pRight = NULL;return node;//insert new Node into treetNode *insertNode(tNode *node, int value)if(node!=NULL)if(node->data == value)return node;else if(node->data > value)node->pLeft = insertNode(node->pLeft, value);elsenode->pRight = insertNode(node->pRight, value);elsenode = newNode(value);return node;void NLR(tNode *root)if(root!=NULL)if(root!=NULL)coutdatapLeft);NLR(root->pRight);tNode *searchNodeByRecursion(tNode *root, int x)if(root != NULL )if(root->data == x)return root;if(root->data > x)return searchNodeByRecursion(root->pLeft,x);elsereturn searchNodeByRecursion(root->pRight,x);return NULL;tNode *searchNodeWithoutRecursion(tNode *root, int x)tNode *p=root;while(p != NULL)if(p->data == x)return p;else if(p->data > x)p = p->pLeft;elsep = p->pRight;return NULL;tNode *minValueNode(tNode *node)tNode *current = node;while(current && current->pLeft != NULL)current = current->pLeft;return current;tNode *deleteNode(tNode *root, int x)if(root == NULL)return root;if(root->data > x)root->pLeft = deleteNode(root->pLeft, x);else if(root->data pRight = deleteNode(root->pRight, x);elsetNode *p = root;if(root->pLeft == NULL)root=root->pRight;delete p;else if(root->pRight== NULL)root=root->pLeft;delete p;elsetNode *temp = minValueNode(root->pRight);root->data = temp->data;root->pRight = deleteNode(root->pRight, temp->data);return root;int main(){//create binary search treecreateEmptyTree();root = insertNode(root, 8);root = insertNode(root, 3);root = insertNode(root, 1);root = insertNode(root, 6);root = insertNode(root, 7);root = insertNode(root, 10);root = insertNode(root, 14);root = insertNode(root, 4);coutKết quảtraverse tree with NLR:8 3 1 6 4 7 10 14Found x=10traverse tree with NLR after delete node:8 4 1 6 7 10 14