Bài giảng Tree Structure

Tree Structure 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 Phần mở rộng (cây n-phân) Cây Top-Down B-Tree Cấu trúc dữ liệu 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 Cấu trúc cây Sao trong máy tính, cây lại thể hiện ngược? Khái niệm J Z A D R B L F A K Q Lá nút gốc Cạnh Khái niệm Thuật ngữ Nút gốc: không có nút cha Nút lá: không có nút con Nút trong: không phải nút con và nút gốc Chiều cao: khoảng cách từ gốc đến lá Chiều cao Nút gốc Nút trong Nút lá Khái niệm 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 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 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á 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 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 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 đủ Binary Tree Duyệt cây: Do cây là cấu trúc ko tuyến tính 3 cách duyệt cây NP 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 Binary Tree PreOrder: InOrder: PostOrder: Binary Tree Cài đặt cây NP dùng liên kết typedef struct node { DataType info; struct node * left; struct node * right; } NODE; typedef NODE * NodePtr; NodePtr pTree; Trỏ nút gốc của cây NP Cấu trúc của một nút Chứa thông tin của nút Trỏ đến nút con trái Trỏ đến nút con phải Binary Tree 8 5 10 1 3 4 7 9 20 pTree Con trỏ pTree trỏ đến nút gốc của cây Binary Tree Các thao tác: NewNode, CreateNode, FreeNode, Init, IsEmpty InsertLeft, InsertRight DeleteLeft, DeleteRight PreOrder, InOrder, PostOrder Search ClearTree Phần minh hoạ dùng DataType là kiểu int Binary Tree CreateNode: tạo một nút mới có giá trị là x NodePtr CreateNode(int x) { NodePtr node; node = NewNode(); node->info = x; node->left = NULL; node->right = NULL; return node; } X node new Binary Tree InsertLeft: thêm nút con bên trái nút p int InsertLeft(NodePtr p, int x) { if (p == NULL) return FALSE; if (p->left != NULL) return FALSE; p->left = CreateNode(x); return TRUE; } Binary Tree InsertRight: thêm một nút con bên phải p int InsertRight(NodePtr p, int x) { if (p == NULL) return FALSE; if (p->right != NULL) return FALSE; p->right = CreateNode(x); return TRUE; } Binary Tree DeleteLeft: xoá nút con bên trái của p, nút này phải là nút lá int DeleteLeft(NodePtr p) { NodePtr q; int value; if (p == NULL) return -1; q = p->left; if (q == NULL) return -1; if (q->left != NULL || q->right !=NULL) return -1; value = q->info; p->left = NULL; FreeNode(q); return value; } Binary Tree PreOrder: xuất theo thứ tự trước void PreOrder(NodePtr pTree) { if (pTree != NULL) { printf(“%d ”, pTree->info); PreOrder(pTree->left); PreOrder(pTree->right); } } Binary Tree InOrder void InOrder(NodePtr pTree) { if (pTree != NULL) { InOrder(pTree->left); printf(“%d ”, pTree->info); InOrder(pTree->right); } } Binary Tree PostOder void PostOrder(NodePtr pTree) { if (pTree != NULL) { PostOrder(pTree->left); PostOrder(pTree->right); printf(“%d ”, pTree->info); } } Binary Tree Search: tìm nút có khoá x NodePtr Search(NodePtr pTree, int x) { NodePtr p; if (pTree == NULL) return NULL; if (pTree->info == x) return pTree; p = Search(pTree->left, x); if (p == NULL) p = Search(pTree->right, x); reutrn p; } Binary Tree ClearTree: xóa lần lượt nút bên trái, bên phải và nút cha. void ClearTree(NodePtr pTree) { if (pTree != NULL) { ClearTree(pTree->left); ClearTree(pTree->right); FreeNode(pTree); } } 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 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 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 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 Binary Search Tree 5 10 30 2 25 45 8 3 6 9 14 33 66 x = 9 10>9, left 5 2, left 5 > 2, left 2 = 2, found 5 > 2, left 2 = 2, found Binary Search Tree Tì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 Binary Search Tree Search NodePtr Search(NodePtr node, int x) { NodePtr p = node; if (p != NULL) if (node->info >x) p = Search(node->left, x); else if (node->info right, x); return p; } 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 Binary Search Tree 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 Binary Search Tree void Insert(NodePtr pTree, int x) { NodePtr node; if ( pTree == NULL) return; if (pTree->info == x) return; if (pTree->info > x) { if (pTree->left == NULL) { node = CreateNode(x); pTree->left = node; } else Insert(pTree->left, x); } else if (pTree->right == NULL) { node = CreateNode(x); pTree->right = node; } else Insert(pTree->right, x); } Binary Search Tree 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 Binary Search Tree 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 Binary Tree Search 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 Binary Search Tree 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 Binary Search Tree 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 Binary Search Tree 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 Binary Search Tree Minh họa xóa (25) P Binary Search Tree Minh họa xóa (25) P rp f Binary Search Tree Minh họa xóa (25) P rp f mới Binary Search Tree Minh họa xóa (25) P f mới Binary Search Tree Minh họa xóa (25) P f mới Binary Search Tree 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á Binary Search Tree 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 Binary Search Tree 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 Binary Search Tree 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 Binary Search Tree 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á 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 Binary Search Tree int Remove(NodePtr &T, int x) { if ( T == NULL) return FALSE; // không tìm thấy nút cần xoá if (T->info >x) // tìm bên trái return Remove(T->left, x); if (T->info right, x); NodePtr p, f, rp; p = T; // p biến tạm trỏ đến T if ( T->left == NULL) // có 1 cây con T = T->right; else if (T->right == NULL) // có 1 cây con T = T->left; Binary Search Tree else { // trường hợp có 2 con chọn nút nhỏ nhất bên con phải f = p; // f để lưu cha của rp rp = p->right; // rp bắt đầu từ p->right while ( rp->left != NULL) { f = rp; // lưu cha của rp rp = rp->left; // rp qua bên trái } // kết thúc khi rp là nút có nút con trái là null p->info = rp->info; // đổi giá trị của p và rp if ( f == p) // nếu cha của rp là p f->right = rp->right; else // f != p f->left = rp->right; p = rp; // p trỏ đến phần tử thế mạng rp } FreeNode(p); // xoá nút p return TRUE; Binary Search Tree 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 Mở rộng BST Quá trình cập nhật cây nhị phân tìm kiếm thường làm cây mất cân bằng Thao tác: Xoay trái RotateLeft Xoay phải RotateRight Mở rộng BST RotateLeft a b c Xoay trái nút r Cây con a Cây con b Cây con c Nút p sẽ trở thànhnút gốc sau khi xoay Mở rộng BST RotateLeft a b c c a b Sau khi xoay Mở rộng BST Minh họa xoay trái Mở rộng BST Minh họa xoay trái pRoot p Mở rộng BST Minh họa xoay trái pRoot p Mở rộng BST Minh họa xoay trái pRoot p Mở rộng BST Minh họa xoay trái pRoot p Gốc mới Mở rộng BST Thủ tục RotateLeft xoay nút root qua trái và trả về địa chỉ của nút gốc mới (thay cho root). NodePtr RotateLeft(NodePtr root) Nếu pRoot khác rỗng & có cây con phải p = root->right root->right = p->left p->left = root return p return NULL Mở rộng BST Sử dụng thủ tục RotateLeft Xoay trái toàn cây nhị phân: trả về con trỏ là nút gốc mới của cây pTree = RotateLeft(pTree) Xoay trái nhánh cây con bên trái của p: trả về con trỏ đến nút gốc mới của nhánh này p->left = RotateLeft(p->left) Xoay trái nhánh cây con bên phải của p: P->right = RotateLeft(p->right) Lưu ý: phải cập nhật link từ nút cha đến nút gốc mới Ví dụ xoay nút p, trong đó p trỏ đến nút con trái của f p = RotateLeft(p) // xoay trái nút p f->left = p // cập nhật lại link từ nút cha đến nút gốc mới Mở rộng BST RotateRight c a b a b c Sau khi xoay phải Mở rộng BST Minh họa xoay phải Mở rộng BST Thủ tục RotateRight xoay nút root qua phải và trả về địa chỉ của nút gốc mới (thay cho root). NodePtr RotateRight(NodePtr root) Nếu pRoot khác rỗng & có cây con trái p = root->left root->left = p->right p->right = root return p return NULL Mở rộng BST Sử dụng thủ tục RotateRight Xoay phải toàn cây nhị phân: trả về con trỏ là nút gốc mới của cây pTree = RotateRight(pTree) Xoay phải nhánh cây con bên trái của p: trả về con trỏ đến nút gốc mới của nhánh này p->left = RotateRight(p->left) Xoay phải nhánh cây con bên phải của p: P->right = RotateRight(p->right) Lưu ý: phải cập nhật liên kết từ nút cha đến nút gốc mới 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 Đánh giá tìm kiếm Đánh giá việc tìm kiếm Tìm giá trị 32 (T1) (T2) Đánh giá tìm kiếm Độ phức tạp của thao tác trên BST: chiều dài đường dẫn từ gốc đến nút thao tác Trong cây cân bằng tốt, chiều dài của đường đi dài nhất là logn 1 triệu entry  đường dẫn dài nhất là log2 1.048.576 = 20 Trong trường hợp cây “cao”, ko cân bằng, độ phức tạp là O(n) Mỗi phần tử thêm vào theo thứ tự đã sắp Sự cân bằng cây là rất quan trọng Cây NP hoàn toàn cân bằng Cây NP hoàn toàn cân bằng Là cây nhị phân Tại mỗi nút: số nút trên nhánh trái và nhánh phải chênh lệch ko quá 1 nút! P Cây con bên trái Cây con bên phải nL(p): số nút cây con trái nút p nR(p): số nút cây con phải nút p Cây NP hoàn toàn cân bằng Trong cây NP hoàn toàn cân bằng Có 3 trường hợp có thể có của một nút (p) nL(p) = nR(p) nL(p) = nR(p)+1 nR(p) = nL(p) +1 Chiều dài đường đi lớn nhất trong cây NP hoàn toàn cân bằng với n nút là log(n) Quá trình thêm hay xóa một nút dễ làm mất trạng thái cân bằng Cây NP hoàn toàn cân bằng Minh họa Nhãn của nút p cho biết số lượng nút của cây có gốc là p Cây NP hoàn toàn cân bằng Cây nhị phân tìm kiếm hoàn toàn cân bằng Tối ưu nhất cho thao tác trên cây Tốc độ tìm kiếm tỉ lệ với O(logn) với n là số nút Thường bị mất cân bằng Do thêm hay xoá Chi phí để cân bằng rất lớn do thao tác trên toàn bộ cây Thực tế ít sử dụng cây NPTK hoàn toàn cân bằng! Xây dựng cây NPTK đạt trạng thái cân bằng yếu hơn (giảm chi phí) Cây AVL Cây AVL: ra đời 1962 Do tác giả Adelson-Velskii và Landis khám phá Cây nhị phân cân bằng đầu tiên Tính chất Là cây nhị phân tìm kiếm Độ cao của cây con trái và cây con phải chênh lệch ko quá 1 Các cây con cũng là AVL Cây AVL Mô tả hl(p) là chiều cao của cây con trái nút p hr(p) là chiều cao của cây con phải của p Các trường hợp có thể xảy ra trên cây AVL Nút p cân bằng hl(p) = hr(p) Lệch về trái: hl(p) > hr(p) (lệch 1 đơn vị) Lệch về phải: hl(p) < hr(p) (lệch 1 đơn vị) Thao tác thêm hay xoá có thể làm AVL mất cân bằng Thao tác cân bằng lại trên AVL xảy ra ở cục bộ Cây AVL Nút p cân bằng P TL TR hl(P) = hr(P) 30 25 15 27 35 54 30 25 15 32 35 54 30 25 15 32 35 54 27 (T1) (T2) (T3) Cây AVL Nút p lệch trái P TL TR hl(P) = hr(P) + 1 hl(P) hr(P) 30 25 15 27 35 (T1) 30 25 15 32 35 54 27 (T3) 20 30 25 15 32 35 54 27 (T3) 20 10 Cây AVL Nút p lệch phải P TR TL hr(P) = hl(P) + 1 hl(P) hr(P) 30 25 32 35 54 (T1) 30 25 15 32 35 54 27 (T2) 40 30 25 15 32 35 54 (T3) 40 55 31 Cây AVL Chỉ số cân bằng bf (Balance Factor) Hiệu số chiều cao cây con trái với cây con phải Xét một nút p bất kỳ trong cây AVL thì bf bf(p) = 0: hl(p) = hr(p) bf(p) = 1: hl(p) = hr(p) + 1 bf(p) = -1: hr(p) = hl(p) +1 Cây AVL Minh họa chỉ số 0 1 0 1 0 0 0 0 -1 -1 0 1 0 0 (T4) 0 0 0 (T1) (T2) (T3) -1 0 -1 1 -1 -1 (T5) 0 1 0 -1 0 0 0 Độ cao của cây rỗng là -1 Cây AVL Thêm một nút vào cây  phức tạp Thêm một nút vào giống như thêm vào cây NPTK Tính lại chỉ số cân bằng của các nút có ảnh hưởng Sau đó xét cây có bị mất cân bằng ko, nếu có thì phải cân bằng lại cây Cân bằng các nút theo các phép xoay thích hợp! Cây AVL Khảo sát việc thêm nút vào cây Sau khi thêm vào thì nút mới là nút lá Có thể mất cân bằng ? Trường hợp nào ko ? Nguyên nhân: Lệch trái: cây sẽ mất cân bằng nếu nút thêm vào là vị trí sau bên trái của một nút trước gần nhất đang bị lệnh trái Lệch phải: ngược với lệch trái Cây AVL -1 1 0 0 0 0 0 1 0 0 0 0 -1 0 0 0 0 U1 U2 U3 U4 U5 U6 U7 U8 U9 U10 U11 U12 B1 B2 B3 B4 B5 B6 Cây AVL Xoay để cân bằng lại cây 1 0 T1 h = n T2 h = n T3 h = n r p Cây AVL Khi thêm x vào T1 2 1 T1 h = n T2 h = n T3 h = n x r p Cây AVL Sau khi cân bằng 0 0 T1 h = n T2 h = n T3 h = n x r p h = n+1 Cây AVL Thêm vào T2 như thế nào? 1 0 T1 h = n T2 h = n T3 h = n r p Cây AVL Khi thêm x vào T2 2 -1 T1 h = n T2 h = n T3 h = n x r p Cây AVL Khi thêm x vào T2: xoay kép 2 -1 T1 h = n T3 h = n x r p 1 q T2-1 h=n-1 T2-2 h=n-1 1 2 Xoay lần 1 xoay trái P Xoay lần 2 xoay phải r Cây AVL Khi thêm x vào T2 2 0 T1 h = n T3 h = n x r p 2 q T2-1 h=n-1 T2-2 h=n-1 2 Cây AVL Khi thêm x vào T2 -1 0 T1 h = n T3 h = n x r p 0 q T2-1 h=n-1 T2-2 h=n-1 Cây AVL Tóm lại: thêm vào AVL Khi thêm vào cây nếu cây bị mất cân bằng Thực hiện cân bằng lại, có 2 trường hợp Có thể chỉ dùng 1 phép xoay Dùng 2 phép xoay như trường hợp 2 Trường hợp cây lệch về bên phải thì tương tự (đối xứng) Cây AVL Cài đặt cây AVL: Bổ sung thêm trường bf cho cấu trúc cây BST typedef struct node { DataType info; int bf; struct node * left; struct node * right; } NODE; typedef NODE * NodePtr; NodePtr pAVLTree; Trỏ nút gốc của cây AVL Chỉ số cân bằng balance factor Cây AVL Các thao tác trên cây AVL tương tự như BST Khác biệt khi thêm/xoá sẽ làm mất cân bằng Ảnh hưởng đến chỉ số cân bằng của nhánh cây liên quan Sử dụng thao tác xoay phải, trái để cân bằng Sinh viên tự tìm hiểu & đọc thêm phần AVL