Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 10: Cây nhị phân

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 10: Cây nhị phân

1. Thiết kế cây liên kết template struct Binary_node { // data members: Entry data; Binary_node *left, *right; // constructors: Binary_node( ); Binary_node(const Entry &x); }; template class Binary_tree { public: // Add methods here. protected: // Add auxiliary function prototypes here. Binary_node *root; }; 11 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 10. Cây nhị phân
2. Khởi tạo và kiểm tra rỗng template Binary_tree ::Binary_tree() { root = NULL; }; template bool Binary_tree ::empty() { return root == NULL; }; 12 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 10. Cây nhị phân
3. Thiết kế các phép duyệt cây template void Binary_tree :: inorder(void (*visit)(Entry &)) { recursive_inorder(root, visit); } template void Binary_tree :: preorder(void (*visit)(Entry &)) { recursive_preorder(root, visit); } template void Binary_tree :: postorder(void (*visit)(Entry &)) { recursive_postorder(root, visit); } 13 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 10. Cây nhị phân
4. Giải thuật duyệt cây inorder Algorithm recursive_inorder Input: subroot là con trỏ node gốc và hàm visit Output: kết quả phép duyệt 1. if (cây con không rỗng) 1.1. Call recursive_inorder với nhánh trái của subroot 1.2. Duyệt node subroot bằng hàm visit 1.3. Call recursive_inorder với nhánh phải của subroot End recursive_inorder 14 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 10. Cây nhị phân
5. Mã C++ duyệt cây inorder template void Binary_tree ::recursive_inorder (Binary_node *sub_root, void (*visit)(Entry &)) { if (sub_root != NULL) { recursive_inorder(sub_root->left, visit); (*visit)(sub_root->data); recursive_inorder(sub_root->right, visit); } } 15 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 10. Cây nhị phân
6. Khai báo cây nhị phân template class Binary_tree { public: Binary_tree( ); bool empty( ) const; void preorder(void (*visit)(Entry &)); void inorder(void (*visit)(Entry &)); void postorder(void (*visit)(Entry &)); int size( ) const; void clear( ); int height( ) const; void insert(const Entry &); Binary_tree (const Binary_tree &original); Binary_tree & operator = (const Binary_tree &original); ~Binary_tree( ); protected: Binary_node *root; }; 16 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 10. Cây nhị phân
7. Cây nhị phân tìm kiếm – Binary search tree (BST) Một cây nhị phân tìm kiếm (BST) là một cây nhị phân rỗng hoặc mỗi node của cây này có các đặc tính sau: 1. Khóa của node gốc lớn (hay nhỏ) hơn khóa của tất cả các node của cây con bên trái (hay bên phải) 2. Các cây con (bên trái, phải) là BST Tính chất: Chỉ cần đặc tính 1 là đủ Duyệt inorder sẽ được danh sách có thứ tự 17 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 10. Cây nhị phân
8. Ví dụ BST 25 10 37 3 18 29 50 1 6 12 20 35 41 5 13 32 Duyệt inorder: 1 3 5 6 10 12 13 18 20 25 29 32 35 37 41 50 18 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 10. Cây nhị phân
9. Các tính chất khác của BST Node cực trái (hay phải): Xuất phát từ node gốc Đi sang trái (hay phải) đến khi không đi được nữa Khóa của node cực trái (hay phải) là nhỏ nhất (hay lớn nhất) trong BST BST là cây nhị phân có tính chất: Khóa của node gốc lớn (hay nhỏ) hơn khóa của node cực trái (hay cực phải) 19 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 10. Cây nhị phân
10. Thiết kế BST template class Search_tree: public Binary_tree { public: //Viết lại phương thức chèn vào, loại bỏ để đảm bảo vẫn là BST Error_code insert(const Record &new_data); Error_code remove(const Record &old_data); //Thêm phương thức tìm kiếm dựa vào một khóa Error_code tree_search(Record &target) const; private: // Add auxiliary function prototypes here. }; 20 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 10. Cây nhị phân
11. Tìm kiếm trên BST Chọn hướng tìm theo tính chất của BST: So sánh với node gốc, nếu đúng thì tìm thấy Tìm bên nhánh trái (hay phải) nếu khóa cần tìm nhỏ hơn (hay lớn hơn) khóa của node gốc Giống phương pháp tìm kiếm nhị phân Thời gian tìm kiếm Tốt nhất và trung bình: O(lg n) Tệ nhất: O(n) 21 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 10. Cây nhị phân
12. Giải thuật tìm kiếm trên BST Algorithm BST_search Input: subroot là node gốc và target là khóa cần tìm Output: node tìm thấy 1. if (cây rỗng) 1.1. return not_found 2. if (target trùng khóa với subroot) 2.1. return subroot 3. if (target có khóa nhỏ hơn khóa của subroot) 3.1. Tìm bên nhánh trái của subroot 4. else 4.1. Tìm bên nhánh phải của subroot End BST_search 22 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 10. Cây nhị phân
13. Mã C++ tìm kiếm trên BST template Binary_node *Search_tree :: search_for_node (Binary_node * sub_root, const Record &target) const { if (sub_root == NULL || sub_root->data == target) return sub_root; else if (sub_root->data right, target); else return search_for_node(sub_root->left, target); } 23 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 10. Cây nhị phân
14. Mã C++ tìm kiếm trên BST (không đệ qui) template Binary_node *Search_tree :: search_for_node (Binary_node * sub_root, const Record &target) const { while (sub_root != NULL && sub_root->data != target) if (sub_root->data right; else sub_root = sub_root->left; return sub_root; } 24 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 10. Cây nhị phân
15. Phương thức tree_search template Error_code Search_tree :: tree_search(Record &target) const { Error_code result = success; Binary_node *found = search_for_node(root, target); if (found == NULL) result = not_present; else target = found->data; return result; } 25 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 10. Cây nhị phân
16. Ví dụ tìm kiếm trên BST 25 10 37 3 18 29 50 1 6 12 20 35 41 5 13 32 KhácGiốngNode nhaugốc nhau nhỏlớn hơnhơn Số node duyệt: 5 Tìm kiếm 13 Tìm thấy Số lần so sánh: 9 26 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 10. Cây nhị phân
17. Ví dụ tìm kiếm trên BST 25 10 37 3 18 29 50 1 6 12 20 35 41 5 13 32 NodeKhác nhaugốc nhỏlớn hơnhơn Số node duyệt: 5 Tìm kiếm 14 Không tìm thấy Số lần so sánh: 10 27 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 10. Cây nhị phân
18. Thêm vào BST 28 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 10. Cây nhị phân
19. Giải thuật thêm vào BST Algorithm BST_insert Input: subroot là node gốc và new_data là dữ liệu cần thêm vào Output: BST sau khi thêm vào 1. if (cây rỗng) 1.1. Thêm vào tại vị trí này 2. if (target trùng khóa với subroot) 2.1. return duplicate_error 3. if (new_data có khóa nhỏ hơn khóa của subroot) 3.1. Thêm vào bên nhánh trái của subroot 4. else 4.1. Thêm vào bên nhánh phải của subroot End BST_insert 29 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 10. Cây nhị phân
20. Mã C++ thêm vào BST template Error_code Search_tree :: search_and_insert (Binary_node * &sub_root, const Record &new_data) { if (sub_root == NULL) { sub_root = new Binary_node (new_data); return success; } else if (new_data data) return search_and_insert(sub_root->left, new_data); else if (new_data > sub_root->data) return search_and_insert(sub_root->right, new_data); else return duplicate_error; } 30 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 10. Cây nhị phân
21. Algorithm BST_insert Input: subrootGiải là node thuật gốc và thêm new_data vào là dữ BST liệu cần thêm vào Output: BST sau khi(không thêm vào đệ qui) 1. parent là rỗng và left_or_right là “left” 2. while (subroot không rỗng) 2.1. if (target trùng khóa với subroot) 2.1.1. return duplicate_error 2.2. if (new_data có khóa nhỏ hơn khóa của subroot) 2.2.2. parent là subroot và left_or_right là “left” 2.2.1. Chuyển subroot sang nhánh trái của subroot 2.3. else 2.3.2. parent là subroot và left_or_right là “right” 2.3.1. Chuyển subroot sang nhánh phải của subroot 3. if (subroot là rỗng) //Thêm vào tại vị trí này 3.1. if (parent là rỗng) 3.1.1. Tạo node gốc của cây 3.2. else 3.2.1. Tạo node bên trái hay phải parent tùy theo left_or_right End BST_insert 31 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 10. Cây nhị phân
22. Xóa một node lá khỏi BST 1. Xóa node này 2. Gán liên kết từ cha của nó thành rỗng 32 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 10. Cây nhị phân
23. Xóa một node chỉ có một con A. Đường dẫn đến các node của cây con v có dạng: u x v u u B. Không còn node nào trong cây có đường đẫn có dạng như vậy. C. Sau khi xóa node x, đường x v dẫn đến các node của cây con v v có dạng: u v D. Đường dẫn của các node khác trong cây không đổi. E. Trước đó, các node của cây con v nằm trong nhánh con của x 1. Gán liên kết từ cha của nó là bên trái (bên phải) của u và bây xuống con duy nhất của nó giờ cũng nằm bên trái (bên phải) 2. Xóa node này của u nên vẫn thỏa mãn BST 33 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 10. Cây nhị phân
24. Xóa một node có đủ 2 nhánh con A. Đường dẫn đến các node của cây con v và z có dạng: u x v u u x z B. Nếu xóa node x thì đường dẫn đến các node của v z cây con v và z có dạng: u v u z D. Điều này chỉ xảy ra khi cây con u và v nằm về 2 phía của u => không còn là BST. E. Giải pháp là thay giá trị x bằng giá trị w thuộc cây này sao cho: w lớn hơn tất cả khóa của các node của cây con v w nhỏ hơn tất cả khóa của các node của cây con z 34 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 10. Cây nhị phân
25. Xóa một node có đủ 2 nhánh con (tt.) 1. Tìm w là node trước node x trên phép duyệt cây inorder (chính là node cực phải của cây con bên trái của x) 2. Thay x bằng w 3. Xóa node w cũ (giống trường hợp 1 hoặc 2 đã xét) 35 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 10. Cây nhị phân
26. Giải thuật xóa một node Algorithm BST_remove_root Input: subroot là node gốc cần phải xóa Output: BST sau khi xóa xong subroot 1. if (trường hợp 1 hoặc 2) //subroot là node lá hoặc có một con 1.1. Gán liên kết cha đến rỗng hoặc nhánh con duy nhất của subroot 1.2. Xóa subroot 2. else //trường hợp 3: có 2 nhánh con //Tìm node cực phải của cây con trái 2.1. to_delete là node con trái của subroot 2.2. while (nhánh phải của to_delete không rỗng) 2.2.1. di chuyển to_delete sang node con phải 2.2. Thay dữ liệu của subroot bằng dữ liệu của to_delete 2.4. Call BST_remove_root với to_delete End BST_remove_root 36 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 10. Cây nhị phân
27. Mã C++ xóa một node template Error_code Search_tree :: remove_root (Binary_node * &sub_root) { if (sub_root == NULL) return not_present; Binary_node *to_delete = sub_root; if (sub_root->right == NULL) sub_root = sub_root->left; else if (sub_root->left == NULL) sub_root = sub_root->right; else { to_delete = sub_root->left; Binary_node *parent = sub_root; while (to_delete->right != NULL) { parent = to_delete; to_delete = to_delete->right; } sub_root->data = to_delete->data; if (parent == sub_root) sub_root->left = to_delete->left; else parent->right = to_delete->left; } delete to_delete; return success; } 37 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 10. Cây nhị phân
28. Cây cân bằng chiều cao - AVL Cây cân bằng hoàn toàn: Số node của nhánh trái và nhánh phải chênh nhau không quá 1. ĐN cây AVL: BST Tại node bất kỳ, chiều cao nhánh trái và nhánh phải chênh nhau không quá 1. Ký hiệu cho mỗi node của cây AVL: Node cân bằng: ‘-’ Nhánh trái cao hơn: ‘/’ Nhánh phải cao hơn: ‘\’ 38 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 10. Cây nhị phân
29. Ví dụ cây AVL Cây AVL Không phải cây AVL 39 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 10. Cây nhị phân
30. Khai báo cây AVL enum Balance_factor { left_higher, equal_height, right_higher }; template struct AVL_node: public Binary_node { // additional data member: Balance_factor balance; AVL_node( ); AVL_node(const Record &x); void set_balance(Balance_factor b); Balance_factor get_balance( ) const; }; template class AVL_tree: public Search_tree { public: Error_code insert(const Record &new data); Error_code remove(const Record &old data); private: // Add auxiliary function prototypes here. }; 40 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 10. Cây nhị phân
31. Ví dụ 1 thêm vào cây AVL 41 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 10. Cây nhị phân
32. Ví dụ 2 thêm vào cây AVL \\ m – k \ t – p \ u (1) – v 42 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 10. Cây nhị phân
33. Ví dụ 2 thêm vào cây AVL (tt.) \\ m – k \ t (2) – p \ u – v Viết gọn 43 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 10. Cây nhị phân
34. Các trạng thái khi thêm vào – / \ Thêm vào bên phải và Thêm vào bên phải và Thêm vào bên phải và làm bên phải cao lên làm bên phải cao lên làm bên phải cao lên \ – \\ Chiều cao cây tăng Chiều cao cây không đổi Mất cân bằng bên phải 44 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 10. Cây nhị phân
35. Cân bằng cây AVL – Quay đơn Binary_node *right_tree = root->right; root->right = right_tree->left; right_tree->left = root; root = right_tree; 45 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 10. Cây nhị phân
36. Cân bằng cây AVL – Quay kép Binary_node *right_tree = root->right; Binary_node *sub_tree = right_tree->left; root->right = sub_tree->left; right_tree->left = sub_tree->right; sub_tree->left = root; sub_tree->right = right_tree; root = sub_tree; Hoặc: rotate_right(right_tree); rotate_left(root); 46 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 10. Cây nhị phân
37. Các trạng thái khi xóa node 47 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 10. Cây nhị phân
38. Các trạng thái khi xóa node (tt.) 48 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 10. Cây nhị phân
39. Các trạng thái khi xóa node (tt.) 49 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 10. Cây nhị phân
40. Ví dụ xóa node của cây AVL 50 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 10. Cây nhị phân
41. Ví dụ xóa node của cây AVL (tt.) 51 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 10. Cây nhị phân