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ử