Cấu trúc cây - Trees

1Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 1 ! Cây và các ứng dụng của cây ! Một số dạng cây thường dùng: cây nhị phân, cây nhị phân tìm kiếm, cây cân bằng (AVL) ! Các thuật toán trên cây ! Đánh giá thuật toán Cấu trúc cây - Trees Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 2 Nội dung trình bày ! Các khái niệm và thuật ngữ cơ bản ! Tổng quan về cây nhị phân (Binary Tree) ! Cây nhị phân tìm kiếm (BST – Binary Search Tree) ! Cây nhị phân tìm kiếm cân bằng (AVL Tree) 2Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 3 Các khái niệm và thuật ngữ cơ bản ! Các ví dụ ! Định nghĩa cấu trúc cây ! Các thuật ngữ liên quan Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 4 Các khái niệm và thuật ngữ cơ bản Các ví dụ ! Ví dụ 1: bài toán đưa thư ! Trên thế giới hiện có 6 tỉ người ! Tuấn, khoa CNTT, ĐH KHTN, Tp.HCM, Việt nam ! Cách tìm ra “Tuấn” nhanh nhất ? ! Sử dụng mảng (array) ? ! Sử dụng danh sách liên kết (linked list) ? 3Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 5 Các khái niệm và thuật ngữ cơ bản Các ví dụ China ... ... ... ...Korea Vietnam Trái đất Tp.HCM Hà nội ĐH.KHTN ĐH.BK Khoa CNTT Khoa Toán “Tuấn” ... ... ... ... Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 6 Các khái niệm và thuật ngữ cơ bản Các ví dụ ! Ví dụ 2: cây biểu thức (a-b)*(c/d) * 0 / a b c d 4Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 7 Các khái niệm và thuật ngữ cơ bản Các ví dụ ! Cây là 1 cấu trúc dữ liệu quan trọng để biểu diễn tính “kế thừa” ! Các cây mô tả tính kế thừa: ! Cây gia phả (trong các dòng họ) ! Cây phân cấp các loài (trong sinh vật) ! … Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 8 Các khái niệm và thuật ngữ cơ bản Định nghĩa cấu trúc cây ! Một cây (Tree) là: ! Một tập các phần tử, gọi là các nút (Node) p1,p2,…,pN ! Nếu N=0, cây gọi là cây rỗng (NULL) ! Nếu N>0: ! Tồn tại duy nhất 1 nút pk gọi là gốc của cây ! Các nút còn lại được chia thành m tập không giao nhau: T1, T2, …, Tm ! Mỗi là 1 cây con của cây 5Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 9 Các khái niệm và thuật ngữ cơ bản Định nghĩa cấu trúc cây a b k i g c h e f d j Cây rỗng (NULL) Nút gốc Cây Cây con Cây con Cây con Cây con Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 10 Các khái niệm và thuật ngữ cơ bản Định nghĩa cấu trúc cây a c k d b i h j g e f Cây con Cây con Cây con Cây con Cây 6Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 11 Các khái niệm và thuật ngữ cơ bản Định nghĩa cấu trúc cây a ck dbi h j g ef Cây con Cây con Cây con Cây con Cây Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 12 Các khái niệm và thuật ngữ cơ bản Định nghĩa cấu trúc cây ! Các tính chất của cây: ! Nút gốc không có nút cha ! Mỗi nút khác chỉ có 1 nút cha ! Mỗi nút có thể có nhiều nút con ! Không có chu trình 7Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 13 Các khái niệm và thuật ngữ cơ bản Các thuật ngữ liên quan ! Nút (Node): là 1 phần tử trong cây. Mỗi nút có thể chứa 1 dữ liệu bất kỳ ! Nhánh (Branch): là đoạn nối giữa 2 nút ! Nút cha (Parent node) ! Nút con (Child node) ! Nút anh em (sibling nodes): là những nút có cùng nút cha ! Bậc của 1 nút pi: là số nút con của pi ! Bậc (a) = 4; Bậc (j) = 3; Bậc (g) = 2; ! Bậc (k) = 1; Bậc (c) = 0 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 14 Các khái niệm và thuật ngữ cơ bản Các thuật ngữ liên quan ! Nút gốc (Root node): nút không có nút cha ! Nút lá (Leaf node, hay nút ngoài – External node): nút có bậc = 0 (không có nút con) ! Nút nội (Internal node): là nút có nút cha và có nút con ! Cây con (Subtree) ! Trắc nghiệm: có bao nhiêu cây con trong cây ? 8Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 15 Các khái niệm và thuật ngữ cơ bản Các thuật ngữ liên quan ! Bậc của cây: là bậc lớn nhất của các nút trong cây ! Bậc () = max {bậc (pi) / pi Î } ! Bậc của cây ? ! Đường đi (Path) giữa nút pi đến nút pj: là dảy các nút liên tiếp từ pi đến pj sao cho giữa hai nút kề nhau đều có nhánh ! Path(a, d) ? Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 16 Các khái niệm và thuật ngữ cơ bản Các thuật ngữ liên quan ! Mức (Level): ! Mức (p) = 0 nếu p = root ! Mức (p) = 1 + Mức (Cha (p)) nếu p!=root ! Chiều cao của cây (Height - hT): đường đi dài nhất từ nút gốc đến nút lá ! hT = max {Path(root, pi) / pi là nút lá Î } ! hT ? 9Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 17 Các khái niệm và thuật ngữ cơ bản Các thuật ngữ liên quan Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 18 Các khái niệm và thuật ngữ cơ bản Các thuật ngữ liên quan ! Cây hoàn chỉnh (Complete tree) với h mức: là 1 cây thoả các điều kiện ! Những nút từ mức 0 đến mức h-1 đều đầy đủ ! Những nút ở mức h được thêm vào cây từ trái sang phải 10 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 19 Các khái niệm và thuật ngữ cơ bản Các thuật ngữ liên quan Cây hoàn chỉnh ? Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 20 Các khái niệm và thuật ngữ cơ bản Các thuật ngữ liên quan Cây hoàn chỉnh ? 11 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 21 Các khái niệm và thuật ngữ cơ bản Các thuật ngữ liên quan ! Cây đầy đủ (Full tree): là 1 cây thoả ! Tất cả các nút lá đều nằm trên cùng 1 mức ! Tất cả những nút khác có cùng bậc với cây Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 22 Các khái niệm và thuật ngữ cơ bản Các thuật ngữ liên quan Cây đầy đủ ? 12 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 23 Các khái niệm và thuật ngữ cơ bản Các thuật ngữ liên quan Cây đầy đủ ? Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 24 Các khái niệm và thuật ngữ cơ bản Các thuật ngữ liên quan Cây đầy đủ ? 13 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 25 Các khái niệm và thuật ngữ cơ bản Các thuật ngữ liên quan ! Mức h của cây đầy đủ bậc d có dh nút ! VD. mức h=2 của cây bậc 3 có bao nhiêu nút ? ! h mức đầu tiên của cây đầy đủ bậc d có số nút là: ! 1 + d + d2 + d3 + … + dh-1 = (dh - 1)/(d – 1) ! 3 mức đầu tiên của cây bậc 3 có bao nhiêu nút ? Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 26 Tổng quan về cây nhị phân ! Định nghĩa ! Cách thức lưu trữ cây ! Các phương pháp duyệt cây 14 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 27 Tổng quan về cây nhị phân Định nghĩa ! Cây nhị phân là cây có bậc = 2 * 0 / a b c d Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 28 Tổng quan về cây nhị phân Định nghĩa ! Độ cao của cây nhị phân có N nút: ! hT(max) = N ! hT(min) = [log2N] + 1 15 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 29 Tổng quan về cây nhị phân Định nghĩa ! Trắc nghiệm: Hãy vẽ tất cả các cây nhị phân có 3 nút ? Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 30 Tổng quan về cây nhị phân Cách thức lưu trữ cây ! Có 2 cách tổ chức cây nhị phân: ! Lưu trữ bằng mảng ! Lưu trữ bằng con trỏ cấu trúc 16 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 31 Tổng quan về cây nhị phân Cách thức lưu trữ cây, sử dụng mảng * 0 / a b c d-1-1d6 -1-1c5 -1-1b4 -1-1a3 65/2 43-1 21*0 Con phảiCon tráiNút# Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 32 Tổng quan về cây nhị phân Cách thức lưu trữ cây, sử dụng mảng // Định nghĩa các cấu trúc dữ liệu typedef struct tagBT_NODE { int Data; int Left; // chỉ số nút con trái int Right; // chỉ số nút con phải } BT_NODE; // binary tree node BT_NODE tree[N]; // cây nhị phân có N nút 17 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 33 Tổng quan về cây nhị phân Cách thức lưu trữ cây, sử dụng con trỏ Nút gốc của cây con trái Data pLeft pRight pRoot Count Nút gốc của cây con phải Data pLeft pRight Data pLeft pRight BT_NODE BIN_TREE Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 34 Tổng quan về cây nhị phân Cách thức lưu trữ cây, sử dụng con trỏ // Định nghĩa các cấu trúc dữ liệu typedef struct tagBT_NODE { int Data; tagBT_NODE *pLeft; // con trỏ đến nút con trái tagBT_NODE *pRight; // con trỏ đến nút con phải } BT_NODE; // binary tree node 18 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 35 Tổng quan về cây nhị phân Cách thức lưu trữ cây, sử dụng con trỏ // Định nghĩa các cấu trúc dữ liệu … (tiếp theo) typedef struct BIN_TREE { int Count; // Số nút trong cây BT_NODE *pRoot; // con trỏ đến nút gốc }; // binary tree Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 36 Tổng quan về cây nhị phân Các phương pháp duyệt cây ! Có 3 cách duyệt cây: ! Duyệt gốc trước (Pre-Order) NLR ! Duyệt gốc giữa (In-Order) LNR ! Duyệt gốc sau (Post-Order) LRN 19 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 37 Tổng quan về cây nhị phân Các phương pháp duyệt cây void NLR(const BT_NODE *pCurr) { if (pCurr==NULL) return; “Xử lý nút gốc pCurr” NLR(pCurr->pLeft); NLR(pCurr->pRight); } Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 38 Tổng quan về cây nhị phân Các phương pháp duyệt cây Minh họa cách duyệt “gốc trước” 20 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 39 Tổng quan về cây nhị phân Các phương pháp duyệt cây void LNR(const BT_NODE *pCurr) { if (pCurr==NULL) return; LNR(pCurr->pLeft); “Xử lý nút gốc pCurr” LNR(pCurr->pRight); } Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 40 Tổng quan về cây nhị phân Các phương pháp duyệt cây void LRN(const BT_NODE *pCurr) { if (pCurr==NULL) return; LRN(pCurr->pLeft); LRN(pCurr->pRight); “Xử lý nút gốc pCurr” } 21 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 41 Tổng quan về cây nhị phân Các phương pháp duyệt cây ! Trắc nghiệm: ! Cho biết kết quả duyệt cây biểu thức ở trang #27 theo mỗi cách NLR, LNR, LRN ? ! Viết thủ tục/hàm đếm số nút trong cây ? ! Viết thủ tục/hàm đếm số nút lá trong cây ? ! Viết thủ tục/hàm tính chiều cao của cây ? Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 42 Tổng quan về cây nhị phân Các phương pháp duyệt cây ! Trắc nghiệm: ! Viết giải thuật duyệt cây theo mức ? 22 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 43 Cây nhị phân tìm kiếm (BST – Binary Search Tree) ! Ý nghĩa của cây BST ! Định nghĩa ! Ví dụ ! Mô tả cấu trúc dữ liệu ! Xây dựng các thao tác cơ bản trên cây ! Các đánh giá ! Trắc nghiệm Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 44 Cây nhị phân tìm kiếm Ý nghĩa của cây BST ! Điểm yếu và điểm mạnh của việc sử dụng mảng ? ! Điểm yếu và điểm mạnh của việc sử dụng danh sách liên kết ? ! Cần có 1 cấu trúc tổng hợp được điểm mạnh của cả mảng và danh sách liên kết. ! Trong cây nhị phân, chi phí để tìm kiếm 1 phần tử ? 23 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 45 Cây nhị phân tìm kiếm Định nghĩa ! Cây nhị phân tìm kiếm là: ! Một cây nhị phân ! Mỗi nút p của cây đều thỏa: ! Tất cả các nút thuộc cây con trái (p->pLeft) đều có giá trị nhỏ hơn giá trị của p "q Î p->pLeft: q->Data Data ! Tất cả các nút thuộc cây con phải (p->pRight) đều có giá trị lớn hơn giá trị của p "q Î p->pRight: q->Data > p->Data Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 46 Cây nhị phân tìm kiếm Ví dụ 24 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 47 Cây nhị phân tìm kiếm Ví dụ Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 48 Cây nhị phân tìm kiếm Mô tả cấu trúc dữ liệu ! Cách lưu trữ cây BST giống như cây nhị phân ! Xem lại phần “Tổng quan về cây nhị phân - Cách thức lưu trữ cây” 25 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 49 Cây nhị phân tìm kiếm Xây dựng các thao tác cơ bản trên cây ! Các thao tác trên cây BST: ! Tạo lập cây rỗng ! Kiểm tra cây rỗng ! Tìm kiếm 1 phần tử ! Thêm 1 phần tử ! Xóa 1 phần tử Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 50 Cây nhị phân tìm kiếm Xây dựng các thao tác cơ bản trên cây ! Tạo lập cây rỗng: void BSTCreate(BIN_TREE &t) { t.Count = 0; // Số nút trong cây t.pRoot = NULL; // Con trỏ đến nút gốc } 26 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 51 Cây nhị phân tìm kiếm Xây dựng các thao tác cơ bản trên cây ! Kiểm tra cây rỗng: int BSTIsEmpty(const BIN_TREE &t) { if (t.pRoot==NULL) return 1; return 0; } Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 52 Cây nhị phân tìm kiếm Xây dựng các thao tác cơ bản trên cây ! Ví dụ tìm kiếm phần tử 25: 40 6532 24 36 30 254 70 75 pRoot 27 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 53 Cây nhị phân tìm kiếm Xây dựng các thao tác cơ bản trên cây ! Ví dụ tìm kiếm phần tử “Nancy”: Jane TomBob Alan Ellen WendyNancy Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 54 Cây nhị phân tìm kiếm Xây dựng các thao tác cơ bản trên cây ! Ví dụ tìm kiếm phần tử 31: 40 6532 24 36 30 254 70 75 pRoot NULL, không tìm thấy 28 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 55 Cây nhị phân tìm kiếm Xây dựng các thao tác cơ bản trên cây ! Tìm kiếm 1 phần tử: BT_NODE *BSTSearch(const BT_NODE *pCurr, int Key) { if (pCurr==NULL) return NULL; // Không tìm thấy if (pCurr->Data==Key) return pCurr; // Tìm thấy else if (pCurr->Data > Key) // Tìm trong cây con trái return BSTSearch(pCurr->pLeft, Key); else // Tìm trong cây con phải return BSTSearch(pCurr->pRight, Key); } Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 56 Cây nhị phân tìm kiếm Xây dựng các thao tác cơ bản trên cây ! Ví dụ thêm phần tử “Frank”: Jane TomBob Alan Ellen WendyNancy NULL, kết thúc tìm kiếm ở đây 29 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 57 Cây nhị phân tìm kiếm Xây dựng các thao tác cơ bản trên cây Jane TomBob Alan Ellen WendyNancy Frank ! Ví dụ thêm phần tử “Frank”: Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 58 Cây nhị phân tìm kiếm Xây dựng các thao tác cơ bản trên cây 40 6532 24 36 30 274 70 75 pRoot! Ví dụ thêm phần tử 26: NULL, kết thúc tìm kiếm ở đây 30 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 59 Cây nhị phân tìm kiếm Xây dựng các thao tác cơ bản trên cây 40 6532 24 36 30 274 70 75 pRoot 26 ! Ví dụ thêm phần tử 26: Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 60 Cây nhị phân tìm kiếm Xây dựng các thao tác cơ bản trên cây 40 6532 24 36 30 274 70 75 pRoot! Ví dụ thêm phần tử 27: Tìm thấy, không thêm nữa 31 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 61 Cây nhị phân tìm kiếm Xây dựng các thao tác cơ bản trên cây ! Thêm 1 phần tử: int BSTInsert(BT_NODE *&pCurr, int newKey) { if (pCurr==NULL) { pCurr = new BT_NODE; // Tạo 1 nút mới pCurr->Data = newKey; pCurr->pLeft = pCurr->pRight = NULL; return 1; // Thêm thành công } if (pCurr->Data > newKey) // Thêm vào cây con trái return BSTInsert(pCurr->pLeft, newKey); else if (pCurr->Data < newKey) // Thêm vào cây con phải return BSTInsert(pCurr->pRight, newKey); else return 0; // Trùng khóa, không thêm nữa } Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 62 Cây nhị phân tìm kiếm Xây dựng các thao tác cơ bản trên cây ! Thao tác xóa 1 phần tử: ! Áp dụng giải thuật tìm kiếm để xác định nút chứa phần tử cần xóa ! Nếu tìm thấy, xóa phần tử đó khỏi cây ! Các trường hợp xảy ra: ! Xóa 1 nút không có nút con ! Xóa 1 nút có 1 nút con ! Xóa 1 nút có 2 nút con 32 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 63 Cây nhị phân tìm kiếm Xây dựng các thao tác cơ bản trên cây ! Ví dụ xóa phần tử 4 (không có nút con) 75 40 6532 24 36 30 254 70 40 6532 24 36 30 25 70 75 Gán liên kết ở nút cha thành NULL Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 64 Cây nhị phân tìm kiếm Xây dựng các thao tác cơ bản trên cây ! Ví dụ xóa phần tử 25 (chỉ có nút con phải) 75 40 6532 24 36 30 25 70 30 40 6532 24 36 70 75 liên kết = nút con phải 33 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 65 Cây nhị phân tìm kiếm Xây dựng các thao tác cơ bản trên cây Trước khi xóa pCurr Sau khi xóa pCurr P->pLeft = pCurr->pRight; delete pCurr; ! Xoá 1 nút chỉ có nút con phải: L L pCurr PP Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 66 Cây nhị phân tìm kiếm Xây dựng các thao tác cơ bản trên cây ! Ví dụ xóa phần tử 75 (chỉ có nút con trái) 75 40 6532 24 36 30 25 70 70 40 6532 24 36 30 25 liên kết = nút con trái 34 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 67 Cây nhị phân tìm kiếm Xây dựng các thao tác cơ bản trên cây Trước khi xóa pCurr Sau khi xóa pCurr P->pRight = pCurr->pLeft; delete pCurr; ! Xoá 1 nút chỉ có nút con trái: L L pCurr PP Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 68 Cây nhị phân tìm kiếm Xây dựng các thao tác cơ bản trên cây 75 40 6532 24 36 30 254 70 ! Ví dụ xóa phần tử 40 (có 2 nút con) 35 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 69 Cây nhị phân tìm kiếm Xây dựng các thao tác cơ bản trên cây 36 75 40 6532 24 30 254 70 36 ! Xóa phần tử 40 (có 2 nút con): Cách 1: thay thế bằng phần tử lớn nhất trong cây con bên trái Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 70 Cây nhị phân tìm kiếm Xây dựng các thao tác cơ bản trên cây 36 75 40 6532 24 30 254 70 65 ! Xóa phần tử 40 (có 2 nút con): Cách 2: thay thế bằng phần tử nhỏ nhất trong cây con bên phải 36 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 71 Cây nhị phân tìm kiếm Xây dựng các thao tác cơ bản trên cây ! Xóa 1 phần tử pCurr có 2 nút con: ! Thay vì xóa trực tiếp nút pCurr… ! …ta tìm 1 phần tử thay thế p, ! …copy nội dung của p sang pCurr, ! …xóa nút p. ! Phần tử thay thế p: ! là phần tử lớn nhất trong cây con bên trái; hoặc… ! …là phần tử nhỏ nhất trong cây con bên phải à phần tử p có nhiều nhất là 1 nút con Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 72 Cây nhị phân tìm kiếm Xây dựng các thao tác cơ bản trên cây ! Xóa 1 phần tử: int BSTDelete(BT_NODE *&pCurr, int Key) { if (pCurr==NULL) return 0; // Không tìm thấy phần tử if (pCurr->Data > Key) // Xóa trên cây con trái return BSTDelete(pCurr->pLeft, Key); else if (pCurr->Data < Key) // Xóa trên cây con phải return BSTDelete(pCurr->pRight, Key); // Tìm thấy nút cần xóa pCurr à Xóa ! _Delete(pCurr); return 1; } 37 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 73 Cây nhị phân tìm kiếm Xây dựng các thao tác cơ bản trên cây ! Xóa 1 phần tử (tt)…: void _Delete(BT_NODE *&pCurr) { BT_NODE *pTemp = pCurr; if (pCurr->pRight==NULL) // Chỉ có 1 nút con trái pCurr = pCurr->pLeft; // Lưu lại nhánh con trái else if (pCurr->pLeft==NULL) pCurr = pCurr->pRight; // Lưu lại nhánh con phải else // Có 2 nhánh con pTemp = _SearchStandFor(pCurr->pLeft, pCurr); delete pTemp; } Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 74 Cây nhị phân tìm kiếm Xây dựng các thao tác cơ bản trên cây ! Xóa 1 phần tử (tt)…: // Tìm phần tử thay thế: “Phần tử lớn nhất trong cây con bên trái” BT_NODE * _SearchStandFor(BT_NODE *&p, BT_NODE *pCurr) { if (p->pRight != NULL) return _SearchStandFor(p->pRight, pCurr); // Tìm thấy phần tử thay thế… pCurr->Data = p->Data; // Copy dữ liệu của p vào pCurr BT_NODE *pTemp = p; p = p->pLeft; // Lưu lại nhánh con trái return pTemp; // Xóa phần tử thay thế } 38 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 75 Cây nhị phân tìm kiếm Các đánh giá ! Cây có N nút sẽ có độ cao trong khoảng từ [log2(N+1)] đến N ! Trắc nghiệm: khi nào độ cao của cây nhỏ nhất ? Lớn nhất ? ! So sánh giữa cây BST với mảng được sắp thứ tự: ! Có cùng chi phí tìm kiếm O(log2N) ! Cây BST có chi phí thêm 1 phần tử O(log2N); mảng có chi phí thêm 1 phần tử O(N) ! Tương tự đối với thao tác xóa 1 phần tử ! Cây BST tốn nhiều bộ nhớ lưu trữ hơn Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 76 Cây nhị phân tìm kiếm Trắc nghiệm ! Viết hàm “Tìm phần tử thay thế: Phần tử nhỏ nhất trong cây con bên phải” ! Bài tập #20 ! Bài tập #22 ! Bài tập #36 ! Bài tập #31 39 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 77 Cây nhị phân tìm kiếm cân bằng (AVL Tree) ! Vì sao phải cân bằng ? ! Định nghĩa ! Ví dụ ! Mô tả cấu trúc dữ liệu ! Thao tác điều chỉnh cây ! Ví dụ tạo cây ! Các đánh giá Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 78 AVL Tree Vì sao phải cân bằng ? ! Cây BST có thể không cân bằng Tom Nancy Alan Bob Ellen Jane Wendy Cây bị lệch à Chi phí O(N) Trường hợp nào cây BST trở nên bị lệch ? Cần có 1 phương pháp để duy trì độ cân bằng cho cây ! 40 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 79 AVL Tree Vì sao phải cân bằng ? ! Cây AVL là 1 dạng cây BST cân bằng ! Cấu trúc cây AVL do 3 tác giả: Adelson, Velskii, Landis đề xuất năm 1962 ! Đây là mô hình cây cân bằng động đầu tiên được đề xuất ! Cây AVL không có độ cân bằng “tuyệt đối”, nhưng 2 cây con không bao giờ có độ cao chênh lệch quá 1. Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 80 AVL Tree Định nghĩa ! Cây AVL là: ! Một cây nhị phân tìm kiếm ! Mỗi nút p của cây đều thỏa: độ cao của cây con bên trái (p->pLeft) và độ cao của cây con bên phải (p->pRight) chênh lệch nhau không quá 1 "pÎTAVL: abs(hp->pLeft - hp->pRight)£ 1 41 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 81 AVL Tree Ví dụ Cây AVL ? Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 82 AVL Tree Mô tả cấu trúc dữ liệu ! Thêm vào mỗi nút trong cây 1 field Bal, diễn tả trạng thái của nút đó: ! Bal = -1: nút lệch trái (cây con trái cao hơn cây con phải) ! Bal = 0: nút cân bằng (cây con trái cao bằng cây con phải) ! Bal = +1: nút lệch phải (cây con phải cao hơn cây con trái) 42 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 83 AVL Tree Mô tả cấu trúc dữ liệu 10 20 30 15 4026 2725 1 0 -1 0 1 0 0 0 Hệ số cân bằng của các nút trong cây AVL Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 84 AVL Tree Mô tả cấu trúc dữ liệu Nút gốc của cây con trái pRoot Count Nút gốc của cây con phảiAVLT_NODE AVL_TREE Data Bal pLeft pRight Data Bal pLeft pRight Data Bal pLeft pRight 43 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 85 AVL Tree Mô tả cấu trúc dữ liệu // Định nghĩa các cấu trúc dữ liệu typedef struct tagAVLT_NODE { int Data; int Bal; // Hệ số cân bằng (-1,0,1) tagBT_NODE *pLeft; // con trỏ đến nút con trái tagBT_NODE *pRight; // con trỏ đến nút con phải } AVLT_NODE; // Cấu trúc nút của cây AVL Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 86 AVL Tree Mô tả cấu trúc dữ liệu // Định nghĩa các cấu trúc dữ liệu … (tiếp theo) typedef struct AVL_TREE { int Count; // Số nút trong cây AVLT_NODE *pRoot; // con trỏ đến nút gốc }; // Cấu trúc cây AVL 44 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 87 AVL Tree Thao tác điều chỉnh cây ! [Insert – Thêm 1 phần tử vào cây]: có thể làm cây mất cân bằng. ! Ta duyệt từ nút vừa thêm ngược về nút gốc, … ! …nếu tìm ra 1 nút P bị mất cân bằng, … ! …thì tiến hành điều chỉnh lại cây tại nút P Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 88 AVL Tree Thao tác điều chỉnh cây ! Ví dụ: thêm phần tử làm cây mất cân bằng tại nút P 44 17 78 32 50 88 48 62 54 P 45 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 89 AVL Tree Thao tác điều chỉnh cây ! [Delete – Xóa 1 phần tử]: có thể làm cây mất cân bằng. ! Ta duyệt từ nút vừa xóa ngược về nút gốc, … ! …nếu tìm ra 1 nút P bị mất cân bằng, … ! …thì tiến hành điều chỉnh lại cây tại nút P ! Thao tác điều chỉnh có thể làm cho những nút phía trên nút P bị mất cân bằng à cần điều chỉnh cho đến khi không còn nút nào bị mất cân bằng nữa Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 90 AVL Tree Thao tác điều chỉnh cây ! Ví dụ: xóa phần tử làm cây mất cân bằng tại nút P 44 17 78 50 88 48 62 P 32 46 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 91 AVL Tree Thao tác điều chỉnh cây Những trường hợp cây bị mất cân bằng và Các cách điều chỉnh cây Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 92 AVL Tree Thao tác điều chỉnh cây (a) (b) Hai trường hợp cây bị mất cân bằng ở nhánh trái P P1 A B C -1 h h h+1 -1 h P P1 B A C h h+1 -1 +1 47 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 93 AVL Tree Thao tác điều chỉnh cây Trường hợp (a): áp dụng phép xoay đơn Trái - Phải (LR – Single Left-Right) P P1 A C P P1 A B C -1 h h h+1 -1 B LR hhh+1 0 0 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 94 AVL Tree Thao tác điều chỉnh cây Ví dụ: thao tác xoay đơn LR 44 17 78 32 50 88 48 62 46 P P1 LR P 44 17 50 32 7848 6246 P1 88 48 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 95 AVL Tree Thao tác điều chỉnh cây h P P1 B A C h h+1 -1 +1 LR Trường hợp (b): thử áp dụng phép xoay đơn LR ? P P1 A CB hh+1h Mất CB Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 96 AVL Tree Thao tác điều chỉnh cây Phép xoay kép Trái - Phải (DLR – Double Left – Right) A h P P1 B1 C h -1 +1 P2 B2 Trường hợp (b) 49 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 97 AVL Tree Thao tác điều chỉnh cây A h P P1 B1 C h -1 +1 P2 B2 DLR Trường hợp (b): áp dụng phép xoay kép Trái - Phải (DLR) A PP1 B1 C h h 0P2 B2 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 98 AVL Tree Thao tác điều chỉnh cây Ví dụ: thao tác xoay kép DLR 44 17 78 32 50 88 48 62 54 P1 P P2 44 17 32 50 78 48 8854 62 P1 P2 P DLR 50 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 99 AVL Tree Thao tác điều chỉnh cây (a) (b) Hai trường hợp cây bị mất cân bằng ở nhánh phải P A +1 h h P1 C B h+1 +1 P A +1 h h+1 P1 CB h +1 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 100 AVL Tree Thao tác điều chỉnh cây Phương pháp xử lý cho trường hợp mất cân bằng ở nhánh phải: tương tự như các xử lý mất cân bằng ở nhánh trái. 51 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 101 AVL Tree Ví dụ tạo cây ! Tạo cây AVL với các khóa lần lượt là: 30, 20, 10,… 10 20 30 LR 10 20 30 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 102 AVL Tree Ví dụ tạo cây 10 20 30 15 4025 27 26 DRL 10 20 30 15 4026 2725 …thêm 15, 40, 25, 27, 26 52 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 103 AVL Tree Ví dụ tạo cây …thêm 5, 13, 14 5 10 20 30 15 4026 272513 14 DLR 10 20 30 14 4026 2725 5 13 15 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 104 AVL Tree Các đánh giá ! Độ cao của cây: hAVL < 1.44log2(N+1). Cây AVL có độ cao nhiều hơm 44% so với độ cao của 1 cây nhị phân tối ưu. ! Chi phí tìm kiếm O(log2N) ! Chi phí thêm phần tử O(log2N) ! Tìm kiếm: O(log2N) ! Điều chỉnh cây: O(log2N) ! Chi phí xóa phần tử O(log2N) ! Tìm kiếm: O(log2N) ! Điều chỉnh cây: O(log2N)