BÀI TẬP CÂY NHỊ PHÂN TÌM KIẾM

     

Cây nhị phân gồm nhiều nút, mỗi nút có rất nhiều nhất là 2 nút con, điện thoại tư vấn là nút con tráinút nhỏ phải. Các nút không tồn tại nút nhỏ nào điện thoại tư vấn là nút lá.

Bạn đang xem: Bài tập cây nhị phân tìm kiếm

Ngoài ra, mỗi nút đều có duy tốt nhất một nút cha, trừ nút gốc của cây không tồn tại cha.

Mỗi nút hoàn toàn có thể chứa thêm thông tin, gọi là khóa. Khóa của nút thường xuyên là một số nguyên, tuy nhiêncó thể là bất kể kiểu dữ liệu nào.

Sau đó là ví dụ một cây nhị phân với khóa là những số nguyên:

*

Ngoài ra, nếu giảm một nhánh của cây ta sẽ tiến hành một cây con:

*

Định nghĩa cây nhị phân tra cứu kiếm

Với cây nhị phân tìm kiếm, khóa của các đỉnh thỏa tính chất sau:

Khóa của các đỉnh không trùng lặp, mỗi đỉnh bao gồm một khóa khác với tất cả các đỉnhcòn lại. Với từng đỉnh, khóa của tất cả các đỉnh vào cây con bên trái nhỏ dại hơn khóa củađỉnh đó. Với mỗi đỉnh, khóa của toàn bộ các đỉnh trong cây con bên phải lớn hơn khóa củađỉnh đó.

Khóa của đỉnh phải là một trong những kiểu dữ liệu có thể so sánh được.

Ví dụ một cây nhị phân tìm kiếm cùng với khóa là số nguyên:

*

Khi tải đặt, ta đề xuất một kiểu tài liệu để lưu giữ nút của cây:


struct Node int key; Node *left = nullptr, *right = nullptr; Node(int key) : key(key) ;
Trong đó:

left là con trỏ mang đến nút con bên trái right là con trỏ mang đến nút nhỏ bên đề nghị key là khóa của nút

Để cho thuận tiện, ta thêm một constructor mang lại kiểu tài liệu vừa tạo.

Thao tác thêm

Phần này đang trình bày làm việc thêm một nút tất cả khóa K vào cây nhị phân tìm kiếm.Vì các khóa trong cây phải không giống nhau nên nếu K đã tồn trên trên cây thì sẽ không tồn tại nútnào có thêm vào.

Việc thêm một khóa được thực hiện một cách đệ quy:

ví như vị trí sẽ xét chưa có nút làm sao thì ta sinh sản tại kia một nút new với khóa là khóa buộc phải thêm. Ngược lại, khi nút đang xét đang tồn tại thì bao gồm 3 trường hợp: Khóa của nút đang xét bằng K, trong trường thích hợp này ta dừng, không thêm nữa. Khóa của nút đã xét lớn hơn K, ta thấy nút nên thêm đề nghị nằm trong cây con bên yêu cầu của nút đã xét, do vậy ta hotline đệ quy xuống cây con bên phải. Khóa của nút đang xét nhỏ dại hơn K, ta gọi đệ quy xuống cây con bên trái.

Với các bước như trên, nút mới luôn là nút lá. Cài đặt trong C++ như sau:


Node* insert(Node *node, int key) if (node == NULL) return new Node(key); if (key node->key) node->left = insert(node->left, key); else if (key > node->key) node->right = insert(node->right, key); return node;
Ví dụ áp dụng hàm trên:


int main() Node* root = NULL; root = insert(root, 2); root = insert(root, 1); root = insert(root, 5); cout root->key root->left->key root->right->key;
Chú ý khi hotline hàm, phải gán lại nút gốc như trên.

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

Phần này trình bày thao tác làm việc tìm một nút gồm khóa bằng K trên cây. Vào trường hợpkhông tìm thấy, trả về NULL.

Xem thêm: Có Bao Nhiêu Nhiệm Vụ Và Bao Nhiêu Nguyên Tắc Hoạt Động Và Tổ Chức Của Đội Là :

Thao tác tìm kiếm kiếm cũng khá được thực hiện đệ quy giống như như trên. Nuốm thể:

giả dụ vị trí vẫn xét chưa tồn tại nút nào, trả về NULL với chân thành và ý nghĩa là không tìm kiếm thấy. Ngược lại, ta đối chiếu K cùng với khóa của nút sẽ xét, tiếp đến đệ quy sang trọng trái/phảihoặc trả về nút hiện tại tùy trực thuộc vào công dụng so sánh phệ hơn/bé hơn hoặc bằng.

Cài để của làm việc này đơn giản và dễ dàng hơn:


Node* find(Node *node, int key) if (node == NULL) return NULL; if (key > node->key) return find(node->right, key); if (key node->key) return find(node->left, key); return node;
Việc khử đệ quy hàm trên khá dễ, chúng ta đọc hoàn toàn có thể tự tìm kiếm hiểu.

Thao tác xóa

Xóa một nút tinh vi hơn so với việc thêm với tìm kiếm. Ta có 3 trường hợp:

Nút cần xóa không có nút con nào

Ở trường vừa lòng này, chỉ đơn giản và dễ dàng là xóa đi nút đó, không làm cái gi thêm.

Nút nên xóa có 1 nút con

Ở trường hợp này, ta cố kỉnh nút cần xóa bởi nút con của nó.

Ví dụ:

*

Nút đề xuất xóa tất cả 2 nút con

Ở trường đúng theo này, ta tìm nút sửa chữa cho nút buộc phải xóa, tiếp đến chuyển khóa củanút sửa chữa lên nút phải xóa, rồi sau cuối mới xóa nút cố kỉnh thế.

Ví dụ:

*

Ta thấy, nút sửa chữa thay thế phải là 1 trong những trong 2 nút tất cả khóa gần nhất với nút bắt buộc xóa, đểviệc chuyển phủ lên trên ko vi phạm đặc thù của cây.

Khi xóa nút cố kỉnh thế, cũng đề nghị xét xem nó có bao nhiêu nút bé như khi xóa một nút bình thường.

Cài đặt

Cài đặt trong C++:


Node *find_remove(Node *root, int key) if (root == NULL) return NULL; if (root->key == key) if (root->left == NULL && root->right == NULL) return NULL; if (root->left != NULL && root->right != NULL) // kiếm tìm nút thay thế sửa chữa Node *successor = root->right; while (successor->left != NULL) successor = successor->left; root->key = successor->key; find_remove(root->right, successor->key); return root; if (root->left != NULL) return root->left; else return root->right; if (key > root->key) root->right = find_remove(root->right, key); else root->left = find_remove(root->left, key); return root;
Khi gọi hàm, giống như như lúc thêm nút, ta cũng bắt buộc gán:


root = find_remove(root, key);
Độ phức tạpĐộ phức hợp của các làm việc trên tùy ở trong vào chiều cao của cây lúc truy vấn.Với dữ liệu ngẫu nhiên, cách setup cây nhị phân vào bài này có độ phức tạp trungbình cho từng thao tác là (O(log N)), cùng với (N) là số nút bên trên cây.

Xem thêm: Thuốc Bổ Trước Khi Mang Thai, Trước Khi Mang Thai Nên Uống Gì

Tuy nhiên, độ phức tạp trong trường hợp xấu độc nhất là (O(N)), bởi vì vậy cây này khôngđược thực hiện trong thực tế.

Đọc thêm
Load comments
Comments
Please enable JavaScript lớn view the comments powered by Disqus.
© 2019 onip.vn • Products