Cấu trúc dữ liệu và giải thuật - Chương 6: Cây - Ngô Quang Thạch

CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT NGÔ QUANG THẠCH Email: thachnq@gmail.com ĐT: 01273984123 Chương 6: Cây C ây Khái niệm về cây và cây nhị phân Biểu diễn cây nhị phân và cây tổng quát Bài toán duyệt cây nhị phân Giới thiệu Cây là một cấu trúc rất gần gũi và có nhiều ứng dụng trong thực tế. Cây là một cấu trúc phân cấp trên một tập hợp nào đó các đối tượng. Một ví dụ quen thuộc về cây, đó là cây thư mục Ví dụ xuất cây từ lện TREE trong CMD ├───Code Snippets │ │ ├───SQL │ │ │ └───My Code Snippets │ │ ├───Visual Basic │ │ │ └───My Code Snippets │ │ ├───Visual C# │ │ │ └───My Code Snippets │ │ ├───Visual Web Developer │ │ │ ├───My HTML Snippets │ │ │ └───My JScript Snippets │ │ └───XML │ │ └───My Xml Snippets │ ├───Projects │ │ ├───VSMacros80 │ │ │ ├───MyMacros │ │ │ └───Samples │ │ └───Web │ ├───Settings │ ├───StartPages │ └───Templates Ví dụ cấu trúc của trang web Khái niệm về cây 1. Định nghĩa  Cây là một tập hợp T các phần tử (gọi là nút của cây) trong đó có một nút đặc biệt gọi là gốc, các nút còn lại được chia thành những tập rời nhau T1, T2,, Tn theo quan hệ phần cấp trong đó Ti cũng là cây.  Giữa các nút có một quan hệ phân cấp gọi là "quan hệ cha con"  Một số khái niệm cơ bản Bậc của một nút : là số con của nút đó. Bậc của một cây : là bậc lớn nhất của các nút trong cây ( số cây con tối đa của một nút trong cây ). Cây có bậc n thì gọi là cây n-phân. Nút lá : là nút bậc 0. Nút nhánh : là nút có bậc khác 0 và không phải là gốc. Xét một cây A là cha của B, C, D, Còn G, H, I là con của D Cấp của A là 3 Cấp của B là 2 Cấp của C là 0. Các nút lá: E, F, C, G, J, K và I Một số khái niệm cơ bản Mức của một nút :  Mức (gốc(T))=1.  Gọi T1,T2,T3,.,Tn là cây con của T0. Mức (T1)=Mức(T2)=Mức(T3)==Mức(Tn)=Mức(T0)+1 - Ðộ dài đường đi từ gốc đến nút x là số nhánh cần đi qua kể từ gốc đến x. Rừng cây: là tập hợp nhiều cây trong đó thứ tự các cây là quan trọng. Cây nhị phân 1. Ðịnh nghĩa Cây nhị phân là cây mà mỗi nút có tối đa 2 cây con. Cây nhị phân Cây nhị phân đầy đủ Cây nhị phân 2. Biểu diễn cây nhị phân  Thông tin lưu tại nút : Info.  Ðịa chỉ nút gốc của cây con trái trong bộ nhớ : L.  Ðịa chỉ nút gốc của cây con phải trong bộ nhớ : R. Cài đặt định nghĩa cấu trúc typedef struct tagNODE { DATA Info; struct tagNODE *Left,*Right; }NODE; typedef NODE *TREE; Cây nhị phân tìm kiếm 1. Ðịnh nghĩa Cây nhị phân tìm kiếm (CNPTK) là cây nhị phân trong đó tại mỗi nút, khoá của tất cả các nút thuộc cây con trái đều nhỏ hơn khoá của nút đang xét và nhỏ hơn khoá của tất cả các nút thuộc cây con phải. 2. Ví dụ Các thao tác trên CNPTK Duyệt cây  Duyệt theo thứ tự trước ( Node-Left-Right)  Duyệt theo thứ tự giữa ( Left-Node-Right)  Duyệt theo thứ tự sau ( Left-Right-Node) Tìm một phần tử x trong cây Thêm một phần tử x vào cây Huỷ một phần tử có khoá x Duyệt theo thứ tự trước ( Node-Left-Right) Kiểu duyệt này trước tiên thăm nút gốc sau đó thăm các nút của cây con trái rồi phải. Thủ tục duyệt có thể trình bày đơn giản như sau: void NLR(TREE Root) { if (root!=NULL) { ; // Xử lý tương ứng theo nhu cầu NLR(RootLeft); NLR(RootRight); } } Ví dụ NLR Duyệt theo thứ tự trước A B D G H E C F I G Duyệt theo thứ tự giữa ( Left-Node-Right)  Kiểu duyệt này trước tiên thăm các nút của cây con trái sau đó tham nút gốc rồi đến cây con phải. Thủ tục duyệt có thể trình bày đơn giản như sau: void LNR(TREE Root) { if (root!=NULL) { LNR(RootLeft); ;//Xử lý tương ứng theo nhu cầu LNR(RootRight); } } Ví dụ LNR Duyệt theo thứ giữa G D H B E A F I C G Duyệt theo thứ tự sau ( Left-Right-Node)  Kiểu duyệt này trước tiên thăm các nút của cây con trái sau đó thăm đến cây con phải rồi cuối cùng mớithăm nút gốc. Thủ tục duyệt có thể trình bày đơn giản như sau: void LRN(TREE Root) { if (root!=NULL) { LRN(RootLeft); LRN(RootRight); ; //Xửlý tương ứng theo nhu cầu } } Ví dụ LRN Duyệt theo thứ tự sau G H D E B I F G C A Tìm một phần tử x trong cây Để tìm một phần tử x trong cây ta chỉ đơn thuần duyệt qua các phần tử cho đến khi tìm thấy x. NODE *SearchTree(TREE Root, DATA x) { NODE *p=Root; while (p!=NULL) { if (x = =pInfo) return p; else if (x<pInfo) p=pLeft; else p=pRight; } return NULL; } Thêm một phần tử x vào cây void AddTree(TREE &Root, DATA x) { if (Root!=NULL) { if (x==RootInfo) //Báo X bị trùng"; else if (x<RootInfo) AddTree(RootLeft,x); else AddTree(RootRight,x); } else { Root = (NODE*)malloc(sizeof(NODE)); RootInfo = x; RootLeft = NULL; RootRight = NULL; } } Huỷ một phần tử có khoá x  Bước 1 : Tìm phần tử p có khoá x.  Bước 2 : Có 3 trường hợp :  p là nút lá : huỷ p.  p có 1 con : tạo liên kết từ phần tử cha của p đến con của p rồi huỷ p.  p có 2 con : tìm phần tử thế mạng cho p theo nguyên tắc: • "Phần tử thế mạng phải nhất của cây con trái của p (phần tử lớn nhất trong các phần tử nhỏ hơn p)" hay : • "Phần tử thế mạng trái nhất của cây con phải của p (phần tử nhỏ nhất trong các phần tử lớn hơn p)." • Sau đó chép thông tin của phần tử thế mạng vào p và huỷ phần tử thế mạng (do phần tử thế mạng có tối đa một con). Xóa nút lá Xóa nút chỉ có một nhánh con Xóa nút có 2 nhánh con Chọn cực phải của bên trái thế làm gốc Xóa nút có 2 nhánh con Chọn cực trái của nhánh con bên phải làm thế gốc Cài đặt void DelNode(TREE &Root, DATA x) { NODE *q; If (Root==NULL) “Báo cây rỗng”; else { if (x<RootInfo) DelNode(RootLeft,x); else if (x>RootInfo) DelNode(RootRight,x); else { q=Root; if (qRight==NULL) Root=qLeft; else if (qLeft==NULL) Root=qRight; else SearchStandFor(RootLeft,q); free(q); } } } void SearchStandFor(tree &p, tree &q) { if(q->right!=NULL) SearchStandFor(p,q->right); else { p->data=q->data; p=q; q=q->left; } } IV. Cây cân bằng Ðịnh nghĩa Cây nhị phân tìm kiếm cân bằng là cây mà tại mỗi nút của nó độ cao của cây con trái và của cây con phải chênh lệch không quá một. Phép duyệt cây Duyệt qua từng node của cây (mỗi node 1 lần) Cách duyệt:  Chính thức: NLR, LNR, LRN, NRL, RNL, RLN  Chuẩn: NLR (preorder), LNR (inorder), LRN (postorder) Ví dụ về phép duyệt cây NLR A B D H I N E J K O C F L P G M AKết quả: B D H I N E J O K C F L P G M Ví dụ về phép duyệt cây LNR A B D H I N E J K O C F L P G M HKết quả: D N I B J O E K A F P L C M G Ví dụ về phép duyệt cây LRN A B D H I N E J K O C F L P G M HKết quả: N I D O J K E B P L F M G C A 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ự Ví dụ BST 25 10 3 1 6 5 18 12 20 13 37 29 35 32 50 41 Duyệt inorder: 1 3 5 6 10 12 13 18 20 25 29 32 35 37 41 50 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) 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) 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 Ví dụ tìm kiếm trên BST 25 10 3 1 6 5 18 12 20 13 37 29 35 32 50 41 Tìm kiếm 13 Khác nhauGiống nhauNode gốc nhỏ hơnlớn hơn Tìm thấy Số node duyệt: 5 Số lần so sánh: 9 Ví dụ tìm kiếm trên BST 25 10 3 1 6 5 18 12 20 13 37 29 35 32 50 41 Tìm kiếm 14 Khác nhauNode gốc nhỏ hơnlớn hơn Không tìm thấy Số node duyệt: 5 Số lần so sánh: 10 Bài tập xây dựng cây nhị phân tìm kiếm Xây dựng cây nhị phân tìm kiếm sau: 50, 40, 30, 20, 10, 15, 70, 60, 80, 90, 45, 35, 25, 55, 65, 75, 85 Thực hiện Xóa nút 80 trong cây