Chương 9 Tree

Click to edit Master title style Click to edit Master text styles Second level Third level Fourth level 18/09/2013 ‹#› /XX MÔN: CẤU TRÚC DỮ LIỆU GV: NGUYỄN XUÂN VINH TREE Nguyễn Xuân Vinh nguyenxuanvinh@hcmuaf.edu.vn CẤU TRÚC DỮ LIỆU DATA STRUCTURES [214331] - 2 Cấu trúc dữ liệu Linear Hierarchical structures - 3 Nội dung Cấu trúc cây Cây nhị phân Cây nhị phân tìm kiếm - 4 Cấu trúc cây Tập hợp các nút và cạnh nối các nút đó Có một nút gọi là gốc Quan hệ one-to-many giữa các nút Có duy nhất một đường đi từ gốc đến một nút Các loại cây: Nhị phân: mỗi nút có {0,1, 2} nút con Tam phân: mỗi nút có {0,1,2,3} nút con n-phân: mỗi nút có {0,1,..,n} nút con - 5 Cấu trúc cây - 6 Khái niệm J Z A D R B L F A K Q Lá nút gốc Cạnh - 7 Thuật ngữ Root node: nút gốc: không có nút cha Leaf node: nút lá: không có nút con Internal node: nút trong: không phải nút con và nút gốc Height: chiều cao: khoảng cách từ gốc đến lá Parent node (or ancestor, or superior): nút cha Child nodes (successor): nút con 1 2 3 5 6 7 8 4 Chiều cao Nút gốc Nút trong Nút lá - 8 Thuật ngữ Root Node A Node H Node B Node G Node F Node E Node D Node C Node K Node J Node L Node I Cây con Nút anh em Ví dụ cây Một số loại cây thường gặp: Cây nhị phân. Cây quyết định. Cây biểu thức. Cây đỏ đen. Nội dung Cấu trúc cây Cây nhị phân Cây nhị phân tìm kiếm Cây nhị phân tìm kiếm cân bằng AVL - 11 Cây nhị phân (Binary Tree) Cấu trúc cây đơn giản nhất Tại mỗi nút gồm các 3 thành phần Phần data: chứa giá trị, thông tin… Liên kết đến nút con trái (nếu có) Liên kết đến nút con phải (nếu có) Cây nhị phân có thể rỗng (ko có nút nào) Cây NP khác rỗng có 1 nút gốc Có duy nhất 1 đường đi từ gốc đến 1 nút Nút không có nút con bên trái và con bên phải là nút lá - 12 Binary Tree A B C D E F I H G Độ sâu/chiều cao = 3 Kích thước = 9 (số nút) Cây con trái Cây con phải Mức 1 Mức 2 Mức 3 Mức 0 - 13 Binary Tree Cây nhị phân đúng: Nút gốc và nút trung gian có đúng 2 con Cây nhị phân đúng có n nút lá thì số nút trên cây 2n-1 A B C D E F G H I J K - 14 Binary Tree Cây nhị phân đầy đủ với chiều sâu d Phải là cây nhị phân đúng Tất cả nút lá có chiều sâu d A B C D E F G Số nút = (2d+1 -1) Số nút trung gian = ? Biết số nút tính d của cây NP đầy đủ - 15 Binary Tree Duyệt cây: Do cây là cấu trúc phi tuyến tính 3 cách duyệt cây nhị phân Duyệt theo thứ tự trước PreOrder: NLR Duyệt theo thứ tự giữa InOrder: LNR Duyệt theo thứ tự sau PostOrder: LRN A B C D E F G - 16 Binary Tree P D S A W T M Pre-order (trước): P D A M S W T Post-order (sau): A M D T W S P In-order (giữa): A D M P S T W Level-Order (rộng): P D S A M W T Cài đặt cây Cây có thể được cài đặt bằng: Mảng Danh sách con Theo con trái nhất và anh em ruột phải Danh sách liên kết 18 Cài đặt cây: bằng mảng Cách 1: Nếu cây T có n nút, ta gán tên các nút lần lượt là 0,1,2,..n-1 sau đó ta dùng 2 mảng A và L để lưu trữ cây bằng cách: Cho A[i] = j với j là nút cha của nút i. A[i] = -1 nếu i là nút gốc. L[i] = x với x là nhãn của nút thứ i. 19 Cài đặt cây: bằng mảng Cách 2: Dùng 1 mảng A là mảng các nút mà mỗi nút bao gồm: Biến parent dùng để lưu trữ chỉ số của nút cha. Biến data dùng để lưu trữ thông tin của nút đó. Một biến maxNode để giữ số nút hiện tại đang có trên cây. 20 Cài đặt cây: bằng mảng Nhận xét: hàm PARENT(n,T) tốn chỉ một hằng thời gian để lấy ra cha của nút n trong cây T. Các hàm đòi hỏi thông tin về các con không làm việc tốt vì phải tốn vòng lặp để dò tìm. Tìm nút con trái nhất của nút i là không thể xác định được. Cách khắc phục qui ước cách đánh thứ tự như sau: Đánh số theo thứ tự tăng dần bắt đầu tại nút gốc. Nút cha được đánh số trước các nút con. Các nút con cùng một nút cha được đánh số lần lượt từ trái sang phải. 21 Cài đặt cây: bằng danh sách con Mỗi nút có 1 danh sách các nút con Danh sách có thể được cài đặt bằng bất cứ cách nào ta biết. Tuy nhiên dùng danh sách liên kết sẽ thích hợp hơn vì số nút con ta chưa biết trước. Nhận xét: Hàm đòi hỏi thông tin về các con làm việc rất thuận lợi Hàm PARENT, Root lại không làm việc tốt. Nó đòi hỏi ta phải duyệt tất cả các danh sách chứa các nút con. 22 Cài đặt cây: bằng danh sách con Các cấu trúc đã dùng để mô tả cây ở trên không trợ giúp phép tạo một cây lớn từ các cây nhỏ hơn (createI) Ta thay thế mảng các header bằng mảng CELLSPACE chứa các struct có ba trường: LABELS giữ nhãn của nút LEFTMOST_CHILD là nút con trái nhất của nó. RIGHT_SIBLING là nút anh ruột phải. Hơn nữa mảng này giữ tất cả các nút của tất cả các cây. 23 Cài đặt cây: theo con trái nhất và anh em ruột phải - 24 Cài đặt cây: bằng danh sách liên kết 8 5 10 1 3 4 7 9 20 pTree - 25 Binary Tree Các thao tác: NewNode, FreeNode, Init, IsEmpty InsertLeft, InsertRight DeleteLeft, DeleteRight PreOrder, InOrder, PostOrder Search ClearTree - 26 Binary Tree CreateNode: tạo một nút mới có giá trị là x X node new - 27 Binary Tree InsertLeft: thêm nút con bên trái nút p - 28 Binary Tree InsertRight: thêm một nút con bên phải p - 29 Binary Tree DeleteLeft: xoá nút con bên trái của p, nút này phải là nút lá - 30 Binary Tree PreOrder: xuất theo thứ tự trước PreOrder(root) visit root For each child k of root preorder(k) Thứ tự: A B C F D E A D B C E F 1 2 3 4 5 6 - 31 Binary Tree InOrder: xuất theo thứ tự giữa InOrder(root) InOrder(FirstChild) visit root For each remain child k of root InOrder(k) Thứ tự: C B A F E D A D B C E F 3 2 1 4 6 5 - 32 Binary Tree PostOder:: xuất theo thứ tự sau PostOrder(root) For each child k of root postorder(k) visit root Thứ tự: C B F E D A A D B C E F 1 2 6 3 5 4 - 33 Binary Tree Search: tìm nút có khoá x - 34 Binary Tree ClearTree: xóa lần lượt nút bên trái, bên phải và nút cha. - 35 Binary Tree Các thao tác mở rộng khác: Đếm số nút lá: CountLeaf Đếm số nút trên cây: CountNode Đếm số nút trong: CountInnerNode Xác định độ sâu/chiều cao của cây Tìm giá trị nhỏ nhất/lớn nhất trên cây Tính tổng các giá trị trên cây Đếm số nút có giá trị bằng x - 36 Nội dung Cấu trúc cây Cây nhị phân (Binary Tree) Cây nhị phân tìm kiếm (Binary Search Tree) Cây nhị phân tìm kiếm cân bằng AVL - 37 Binary Search Tree BST là cây nhị phân mà mỗi nút thoả Giá trị của tất cả nút con trái nút gốc 5 3 1 4 10 8 20 5 - 38 Binary Search Tree Ví dụ Binary search trees Non-binary search tree 5 10 30 2 25 45 5 10 45 2 25 30 5 10 30 2 25 45 - 39 Binary Search Tree: Tìm kiếm (9) x = 9 10>9, left 5 2, left 5 > 2, left 2 = 2, found 5 > 2, left 2 = 2, found - 41 Binary Search Tree: Tìm kiếm (25) 5 10 30 2 25 45 5 10 30 2 25 45 10 25, left 25 = 25, found 5 25, left 30 > 25, left 10 ko tìm thấy Nếu khoá x = khóa nút gốc => tìm thấy Ngược lại nếu khoá x Tìm trên cây bên trái Ngược lại => tìm trên cây bên phải - 44 Binary Search Tree Xây dựng cây BST Chèn Xóa Luôn duy trì tính chất Giá trị nhỏ hơn ở bên cây con trái Giá trị lớn hơn ở bên cây con phải - 45 Binary Search Tree: Insert Insert Thực hiện tìm kiếm giá trị x Tìm đến cuối nút Y (nếu x ko tồn tại trong cây) Nếu x y, thêm nút lá x bên phải của Y 5 10 30 2 25 45 20 Y X mới - 46 Binary Search Tree: Delete Delete: xóa nhưng phải đảm bảo vẫn là cây BST Thực hiện tìm nút có giá trị x Nếu nút là nút lá, delete nút Ngược lại Thay thế nút bằng một trong hai nút sau Y là nút lớn nhất của cây con bên trái Z là nút nhỏ nhất của cây con bên phải Chọn nút Y hoặc Z để thế chỗ Giải phóng nút - 47 Binary Search Tree: Delete Trường hợp 1: nút p là nút lá, xoá bình thường 5 10 30 2 25 45 5 10 30 2 45 Xóa 25 - 48 Binary Tree Search: Delete Trường hợp 2: p chỉ có 1 cây con, cho nút cha của p trỏ tới nút con duy nhất của nó, rồi hủy p 5 10 30 2 25 45 Xóa 5 10 30 2 25 45 - 49 Binary Search Tree: Delete Trường hợp 3: nút p có 2 cây con, chọn nút thay thế theo 1 trong 2 cách như sau Nút lớn nhất trong cây con bên trái Nút nhỏ nhất trong cây con bên phải Nút lớn bên trái Nút nhỏ bên phải - 50 Binary Search Tree : Delete Delete: nút 10 cách 1 5 10 30 2 25 45 50 55 5 30 2 25 45 50 55 Xóa 10 Chọn nút có khoá lớn nhất bên trái - 51 Binary Search Tree : Delete Delete: nút 10 cách 2 5 10 30 2 25 45 50 55 Xóa 10 5 25 30 2 45 50 55 Chọn nút nhỏ nhất bên phải - 52 Binary Search Tree: Delete Minh họa xóa (25) 52 25 66 15 39 9 19 27 42 31 60 99 58 62 P - 53 Binary Search Tree: Delete Minh họa xóa (25) 52 25 66 15 39 9 19 27 42 31 60 99 58 62 P rp f - 54 Binary Search Tree: Delete Minh họa xóa (25) 52 27 66 15 39 9 19 27 42 31 60 99 58 62 P rp f mới - 55 Binary Search Tree: Delete Minh họa xóa (25) 52 27 66 15 39 9 19 25 42 31 60 99 58 62 P f mới - 56 Binary Search Tree: Delete Minh họa xóa (25) 52 27 66 15 39 9 19 31 42 60 99 58 62 P f mới - 57 Binary Search Tree: Delete 25 15 39 9 19 42 P rp f Trường hợp đặc biệt: f == p Nút thế mạng rp là nút con phải của nút p cần xoá 52 - 58 Binary Search Tree: Delete 39 15 39 9 19 42 P rp f Trường hợp đặc biệt: f == p Nút thế mạng rp là nút con phải của nút p cần xoá - Đưa giá trị của nút rp lên nút p 52 - 59 Binary Search Tree: Delete 39 15 39 9 19 42 P rp f Trường hợp đặc biệt: f == p Nút thế mạng rp là nút con phải của nút p cần xoá - Chuyển liên kết phải của p đến liên kết phải của rp 52 - Binary Search Tree: Delete 39 15 39 9 19 42 P rp f Trường hợp đặc biệt: f == p Nút thế mạng rp là nút con phải của nút p cần xoá - Xoá nút rp 52 - 61 Binary Search Tree: Delete 39 15 9 19 42 P f Trường hợp đặc biệt: f == p Nút thế mạng rp là nút con phải của nút p cần xoá - Sau khi xoá 52 - 62 Binary Search Tree Remove (NodePtr T, int x) Nếu T = NULL  thoát Nếu T->info > x  Remove(T->left, x) Nếu T->info right, x) Nếu T->info = x P = T Nếu T có 1 nút con thì T trỏ đến nút con đó Ngược lại có 2 con Gọi f = p và rp = p->right; Tìm nút rp sao cho rp->left = null và nút f là nút cha nút rp Thay đổi giá trị nội dung của T và rp Nếu f = p (trường hợp đặc biệt) thì: f->right = rp->right; Ngược lại: f->left = rp->right; P = rp; // p trỏ tới rp để xoá Xoá P - 63 Bài tập Cài đặt cấu trúc dữ liệu liên kết cho cây nhị phân tìm kiếm Cài đặt các thao tác xây dựng cây: NewNode, Init, IsEmpty, CreateNode Cài đặt thao tác cập nhật: Insert, Remove, ClearTree Xuất danh sách tăng dần và giảm dần Kiểm tra xem cây có phải là cây nhị phân đúng Kiểm tra xem cây có phải là cây nhị phân đầy đủ Xác định nút cha của nút chứa khoá x Đếm số nút lá, nút giữa, kích thước của cây Xác định độ sâu/chiều cao của cây Tìm giá trị nhỏ nhất/lớn nhất trên cây Tính tổng các giá trị trên cây 64 Đọc thêm Tài liệu tham khảo Tóm tắt Trong chương này, chúng ta cần phải nắm vững các vấn đề sau: Cây Cây nhị phân Cây nhị phân tìm kiếm Các phép toán: Create, Insert, Delete (remove) HỎI ĐÁP