Bài giảng Cấu trúc dữ liệu và Giải thuật - Chương 7: Cây (Tree)

Chương 7: CÂY (Tree)Nội dung2Cấu trúc cây (Tree)Cấu trúc cây nhị phân (Binary Tree)Cấu trúc cây nhị phân tìm kiếm (Binary Search Tree)Cấu trúc cây nhị phân tìm kiếm cân bằng (AVL Tree)Tree – Định nghĩa3Cây là một tập gồm 1 hay nhiều nút T, trong đó có một nút đặc biệt được 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à một cây A tree is a set of one or more nodes T such that:i. there is a specially designated node called a rootii. The remaining nodes are partitioned into n disjointed set of nodes T1, T2,,Tn, each of which is a treeTree – Ví dụ 4Sơ đồ tổ chức của một công ty Công ty AR&DKinh doanhTaøi vuïSaûn xuaátTVCDAmplierNoäi ñòaQuoác teáChaâu aâuMyõCaùc nöôùcTree – Ví dụCây thư mục5Tree – Ví dụ6Tree – Ví dụCó phải là cây khôngTree – Ví dụCó phải là cây không8Không vì trong cấu trúc cây không tồn tại chu trìnhTree - Một số khái niệm cơ bản Bậc của một nút (Degree of a Node of a Tree): Là số cây con của nút đó. Nếu bậc của một nút bằng 0 thì nút đó gọi là nút lá (leaf node)Bậc của một cây (Degree of a Tree):Là bậc lớn nhất của các nút trong cây. Cây có bậc n thì gọi là cây n-phânNút gốc (Root node): Là nút không có nút chaNút lá (Leaf node): Là nút có bậc bằng 09JZADRBLFAKQLánútgốcCạnhTree - Một số khái niệm cơ bản10Nút nhánh: Là nút có bậc khác 0 và không phải là gốcMức của một nút (Level of a Node): Mức (T0) = 0, với T0 là gốcGọi T1, T2, T3, ... , Tn là các cây con của T0: Mức(T1) = Mức(T2) = ... = Mức(Tn) = Mức(T0) + 1We define the level of the node by taking the level of the root node as 0, and incrementing it by 1 as we move from the root towards the subtrees.Chiều cao của cây (độ sâu) (Height – Depth of a Tree):Là mức cao nhất của nút + 1 (mức cao nhất của 1 nút có trong cây) t1t2t3Tree - Một số khái niệm cơ bản11Nút trước, nút sau của 1 nútNút T được gọi là nút trước của 1 nút (ancestor’s node) của nút S nếu cây con có gốc là T chứa cây con có gốc là S. Khi đó S được gọi là nút sau của nút T (descendant’s node)Chiều dài đường đi của 1 nútChiều dài đường đi của 1 nút là số đỉnh (số nút) tính từ nút gốc để đi đến nút đó.Chiều dài đường đi của nút gốc luôn =1, chiều dài đường đi tới 1 nút bằng chiều dài đường đi tới nút cha của nó + 1Tree - Một số khái niệm cơ bản12Chiều dài đường đi của 1 câyChiều dài đường đi của 1 cây (path’s length of the tree) là tổng tất cả các chiều dài đường đi của tất cả các nút trên cây (chiều dài đường đi trong internal path’s length).Tính chiều dài đường đi ngoài (external path’s length) bằng cách mở rộng tất cả các nút của cây sao cho các nút của cây có cùng bậc (thêm vào các nút giả) với bậc của cây. Rừng.Rừng (forest) là tập hợp các cây.Khi cây mất gốc  rừngTree – Ví dụ- Leaf node?- Degree of a Nodes of a Tree?- Degree of a Tree?- Level of a Node?- Height – Depth of a Tree?Trắc nghiệmThe depth of a tree is the _______ of a treenumber of nodes on the treenumber of levels of a treenumber of brancheslevelGive the binary tree with root A. The root has left child B and right child C. B has left child D and right child E. There are no other nodes in the tree. The height of the tree is _______.031214Một số khái niệm cơ bảnĐộ dài đường đi từ gốc đến nút x: Px = số nhánh cần đi qua kể từ gốc đến x Độ dài đường đi tổng của cây: trong đó Px là độ dài đường đi từ gốc đến XĐộ dài đường đi trung bình: PI = PT/n (n là số nút trên cây T)Rừng cây: là tập hợp nhiều cây trong đó thứ tự các cây là quan trọng15Tree – Ví dụ16Depth-first Search171.3. Biểu diễn câyDùng đồ thị, Dùng giản đồ tập hợp, Sử dụng dạng phân cấp chỉ số BIỂU DIỄN CÂY TRONG BỘ NHỚ MÁY TÍNHĐể biểu diễn cây trong bộ nhớ máy tính dùng danh sách liên kết.Để biểu diễn cây N-phân dùng danh sách có N mối liên kết để quản lý N địa chỉ nút con.Cấu trúc dữ liệu của cây N-phân tương tự cấu trúc dữ liệu đa liên kết.const int N = 100;typedef struct NTNode{ T Key; NTNode * SubNode[N];}NTOneNode;typedef struct NTOneNode * NTType;Để quản lý cây, chỉ cần quản lý địa chỉ nút gốc NTType NTree;Depth-first Search182.2. Biểu diễn và các thao tácĐể biểu diễn cây nhị phân trong bộ nhớ máy tính dùng danh sách có 2 mối liên kết để quản lý địa chỉ 2 nút con (cây con trái và cây con phải). Như vậy cấu trúc dữ liệu của cây nhị phân tương tự cấu trúc dữ liệu của danh sách liên kết đôi nhưng cách thức liên kết khác:struct TNode { int Info; struct TNode *pL,*pR; };Để quản lý cây nhị phân chỉ cần quản lý địa chỉ nút gốctypedef TNode *TREE;TREE T;Nội dung19Cấu trúc cây (Tree)Cấu trúc cây nhị phân (Binary Tree)Cấu trúc cây nhị phân tìm kiếm (Binary Search Tree)Cấu trúc cây nhị phân tìm kiếm cân bằng (AVL Tree)Binary Tree – Định nghĩa20Cây nhị phân là cây mà mỗi nút có tối đa 2 cây con (cây có bậc là 2)Binary Tree – Ví dụ21Cây con tráiCây con phảiHình ảnh một cây nhị phânBinary Tree – Ví dụCây lệch trái và cây lệch phảiBinary Tree – Ví dụCây nhị phân đầy đủ (A full binary tree)Binary Tree – Ứng dụngCây biểu thức: được dùng để biểu diễn một biểu thức toán học24Binary Tree – Ví dụCây quyết định: được dùng để hỗ trợ quá trình ra quyết định25Binary Tree – Một số tính chấtSố nút nằm ở mức i ≤ 2iSố nút lá ≤ 2h-1, với h là chiều cao của câySố nút trong cây ≤ 2h-1, với h là chiều cao của câyChiều cao của cây ≥ log2N, với N là số nút trong cây26Trắc nghiệmA binary tree is a tree in which each node references at most _____ node(s)1 0 3 2The maximum number of leaf-nodes in a binary tree of height 4 is:2 4 6 8What is the minimum height of a binary tree with 31 nodes?4 7 5 3If the depth of a binary tree is 3, then what is the maximum size of the tree?3 4 6 827Binary Tree - Biểu diễnIn general, any binary tree can be represented using an array, but it leads to the waste of storage Binary Tree - Biểu diễn29Binary Tree - Biểu diễn30Binary Tree - Biểu diễn31Sử dụng cấu trúc để lưu trữ các thông tin của một nút gồm:Dữ liệu của nútĐịa chỉ nút gốc của cây con tráiĐịa chỉ nút gốc của cây con phảiKhai báo cấu trúc cây nhị phân:Để quản lý cây nhị phân chỉ cần quản lý địa chỉ nút gốc: Tree root;struct TNode{ DataType data; TNode *pLeft, *pRight;};typedef TNode* Tree; //??Binary Tree - Biểu diễn32abcdeghifjkBinary Tree – Khởi tạo câyKhởi tạo cây rỗng:void InitTree (Tree &t){ t = NULL;}33Binary Tree - Duyệt cây nhị phân 34Có 3 kiểu duyệt chính có thể áp dụng trên cây nhị phân: Duyệt theo thứ tự trước - preorder (Node-Left-Right: NLR)Duyệt theo thứ tự giữa - inorder (Left-Node-Right: LNR)Duyệt theo thứ tự sau - postorder (Left-Right-Node: LRN)Tên của 3 kiểu duyệt này được đặt dựa trên trình tự của việc thăm nút gốc so với việc thăm 2 cây conBinary Tree - Duyệt cây nhị phân NLR35ABDHINEJKOCFLPGMAKết quả:BDHINEJOKCFLPGMBinary Tree - Duyệt cây nhị phânDuyệt theo thứ tự trước NLR (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 đến cây con phảiThủ tục duyệt có thể trình bày đơn giản như sau:36void NLR (Tree t){ if (t != NULL) { // Xử lý t tương ứng theo nhu cầu NLR(t->pLeft); NLR(t->pRight); }}Cây nhị phân Duyệt theo thứ tự trước (Node-Left-Right) Một ví dụ: đọc một quyển sách hay bài báo từ đầu đến cuối như minh họa trong hình bên dưới: 37Binary Tree - Duyệt cây nhị phân LNR38ABDHINEJKOCFLPGMHKết quả:DNIBJOEKAFPLCMGBinary Tree - Duyệt cây nhị phânDuyệt theo thứ tự giữa LNR (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 đó thăm nút gốc rồi đến cây con phảiThủ tục duyệt có thể trình bày đơn giản như sau:39void LNR(Tree t){ if (t != NULL) { LNR(t->pLeft); //Xử lý nút t theo nhu cầu LNR(t->pRight); }}Cây nhị phân Duyệt theo thứ tự sau (Left-Right-Node) Một ví dụ quen thuộc trong tin học về ứng dụng của duyệt theo thứ tự sau là việc xác định tồng kích thước của một thư mục trên đĩa40Binary Tree - Duyệt cây nhị phân LRN41ABDHINEJKOCFLPGMHKết quả:NIDOJKEBPLFMGCABinary Tree - Duyệt cây nhị phânDuyệt theo thứ tự sau LRN (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ới thăm nút gốcThủ tục duyệt có thể trình bày đơn giản như sau:42void LRN(Tree t){ if (t != NULL) { LRN(t->pLeft); LRN(t->pRight); // Xử lý tương ứng t theo nhu cầu }}(3 + 1)3/(9 – 5 + 2) – (3(7 – 4) + 6) = –1343Tính toán giá trị của biểu thức dựa trên cây biểu thức: duyệt cây theo thứ tự giữa:Binary Tree - Duyệt cây nhị phân LRNBinary Tree – Ứng dụngTính toán giá trị của biểu thức dựa trên cây biểu thức: duyệt cây theo thứ tự giữa:44Trắc nghiệmGive the binary tree with root A. The root has left child B and right child C. B has left child D and right child E. There are no other nodes in the tree. Which of the following traversals yields ABCDE?InorderPreorderAll of the others answersNone of the others answers45Trắc nghiệmThe order in which the nodes of this tree would be visited by a post-order traversal is46a) GCMBEJQDFKYb) BCDFEJKYQMGc) GCBEDFMJKQYd) BDFECKJYQMGTrắc nghiệmThe order in which the nodes of this tree would be visited by a pre-order traversal is47a) GCMBEJQDFKYb) BCDFEJKYQMGc) BCDEFGKJMYQd) GCBEDFMJKQYCây nhị phân Biểu diễn cây tổng quát bằng cây nhị phân Nhược điểm của các cấu trúc cây tổng quát:Bậc của các nút trên cây có thể dao động trong một biên độ lớn  việc biểu diễn gặp nhiều khó khăn và lãng phí. Việc xây dựng các thao tác trên cây tổng quát phức tạp hơn trên cây nhị phân nhiều. Vì vậy, thường nếu không quá cần thiết phải sử dụng cây tổng quát, người ta chuyển cây tổng quát thành cây nhị phân. 48Cây nhị phân Biểu diễn cây tổng quát bằng cây nhị phân Ta có thể biến đổi một cây bất kỳ thành một cây nhị phân theo qui tắc sau:Giữ lại nút con trái nhất làm nút con trái.Các nút con còn lại chuyển thành nút con phải.Như vậy, trong cây nhị phân mới, con trái thể hiện quan hệ cha con và con phải thể hiện quan hệ anh em trong cây tổng quát ban đầu.49Cây nhị phân Biểu diễn cây tổng quát bằng cây nhị phân Giả sử có cây tổng quát như hình bên dưới: 50ABCDEFGHIJCây nhị phân tương ứng sẽ như sau: ABCDEFGHIJMột cách biểu diễn cây nhị phân khác 51Đôi khi, khi định nghĩa cây nhị phân, người ta quan tâm đến cả quan hệ 2 chiều cha con chứ không chỉ một chiều như định nghĩa ở phần trên. Lúc đó, cấu trúc cây nhị phân có thể định nghĩa lại như sau: struct TNODE { DataType Key; TNODE* pParent; TNODE* pLeft; TNODE* pRight;};typedef TNODE* TREE;Một cách biểu diễn cây nhị phân khác52Một số thao tác trên câyĐếm số nodeĐếm số node láTính chiều cao...53Đếm số node54Đếm số nodeThuật toán:Nếu Tree rỗng, Số node (Tree) = 0Ngược lại, Số node (Tree) = 1 + Số node (Tree.Left) + Số node (Tree.Right)55Đếm số node lá56Đếm số node láThuật toán:Nếu Tree rỗng, Số nút lá (Tree) = 0Nếu Tree là nút lá, Số nút lá (Tree) = 1 + Số nút lá (Tree.Left) + Số nút lá (Tree.Right)Nếu Tree không là nút lá, Số nút lá (Tree) = Số nút lá (Tree.Left) + Số nút lá (Tree.Right)57Tính chiều cao58Tính chiều caoThuật toán:Nếu Tree rỗng, Height(Tree) = 0Ngược lại, Height(Tree) = 1 + max(Height(Tree.Left), Height(Tree.Right))59Nội dung60Cấu trúc cây (Tree)Cấu trúc cây nhị phân (Binary Tree)Cấu trúc cây nhị phân tìm kiếm (Binary Search Tree)Cấu trúc cây nhị phân tìm kiếm cân bằng (AVL Tree)Binary Search TreeTrong chương 6, chúng ta đã làm quen với một số cấu trúc dữ liệu động. Các cấu trúc này có sự mềm dẻo nhưng lại bị hạn chế trong việc tìm kiếm thông tin trên chúng (chỉ có thể tìm kiếm tuần tự)Nhu cầu tìm kiếm là rất quan trọng. Vì lý do này, người ta đã đưa ra cấu trúc cây để thỏa mãn nhu cầu trênTuy nhiên, nếu chỉ với cấu trúc cây nhị phân đã định nghĩa ở trên, việc tìm kiếm còn rất mơ hồCần có thêm một số ràng buộc để cấu trúc cây trở nên chặt chẽ, dễ dùng hơnMột cấu trúc như vậy chính là cây nhị phân tìm kiếmBinary Search Tree - Định nghĩaCây nhị phân tìm kiếm (CNPTK) là cây nhị phân trong đó tại mỗi nút, khóa của nút đang xét lớn hơn khóa của tất cả các nút thuộc cây con trái và nhỏ hơn khóa của tất cả các nút thuộc cây con phảiNhờ ràng buộc về khóa trên CNPTK, việc tìm kiếm trở nên có định hướngNếu số nút trên cây là N thì chi phí tìm kiếm trung bình chỉ khoảng log2NTrong thực tế, khi xét đến cây nhị phân chủ yếu người ta xét CNPTK62Binary Search Tree – Ví dụ63441888133759108152340557164Binary Search Tree – Ví dụ65Binary Search Tree – Ví dụTạo cây nhị phân tìm kiếmCaáu truùc Döõ lieäu - Caáu truùc caây66251031651812201337293532504125 37 10 18 29 50 3 1 6 5 12 20 35 13 32 412537101829503165122035133241Binary Search Tree – Biểu diễn67Cấu trúc dữ liệu của CNPTK là cấu trúc dữ liệu biểu diễn cây nhị phân nói chung Thao tác duyệt cây trên CNPTK hoàn toàn giống như trên cây nhị phânChú ý: khi duyệt theo thứ tự giữa, trình tự các nút duyệt qua sẽ cho ta một dãy các nút theo thứ tự tăng dần của khóa struct TNode{ DataType data; TNode *pLeft, *pRight;};typedef TNode* Tree; Tree Root ;Binary Search Tree – Duyệt cây682510316518122013372935325041Duyệt inorder: 1 3 5 6 10 12 13 18 20 25 29 32 35 37 41 50Duyệt giữa (LNR) trên CNPTKBinary Search Tree – Duyệt cây692510316518122013372935325041Duyệt postorder: 1 5 6 3 13 12 20 18 10 32 35 29 41 50 37 25Duyệt sau (LRN) trên CNPTKBinary Search Tree – Duyệt cây702510316518122013372935325041Duyệt preorder: 25 10 3 1 6 5 18 12 13 20 37 29 35 32 50 41Duyệt trước (NLR) trên CNPTKBinary Search Tree – Tìm kiếm712510316518122013372935325041Tìm kiếm 13Khác nhauGiống nhauNode gốc nhỏ hơnNode gốc lớn hơnTìm thấySố node duyệt: 5Tìm kiếm trên CNPTKBinary Search Tree – Tìm kiếm722510316518122013372935325041Tìm kiếm 14Khác nhauNode gốc nhỏ hơnNode gốc lớn hơnKhông tìm thấySố node duyệt: 5Tìm kiếm trên CNPTKBinary Search Tree – Tìm kiếmTìm một phần tử x trong CNPTK (dùng đệ quy):73TNode* searchNode(Tree T, DataType X){ if (T) { if(T->data ==X) return T; if(T->data >X) return searchNode(T->pLeft, X); return searchNode(T->pRight, X); } return NULL;}Binary Search Tree – Tìm kiếmTìm một phần tử x trong CNPTK (dùng vòng lặp):74TNode* searchNode(Tree T, DataType x){ TNode *p = T; while (p != NULL) { if(x == p->data) return p; else if(x data) p = p->pLeft; else p = p->pRight; } return NULL;}Binary Search Tree – Tìm kiếm75Nhận xét:Số lần so sánh tối đa phải thực hiện để tìm phần tử X là h, với h là chiều cao của câyNhư vậy thao tác tìm kiếm trên CNPTK có n nút tốn chi phí trung bình khoảng O(log2n)Tìm một phần tử x trong cây 764418881337591081523405571Tìm X=5544 X59 > XBinary Search Tree – Thêm77Việc thêm một phần tử X vào cây phải bảo đảm điều kiện ràng buộc của CNPTKTa có thể thêm vào nhiều chỗ khác nhau trên cây, nhưng nếu thêm vào một nút ngoài sẽ là tiện lợi nhất do ta có thể thực hiện quá trình tương tự thao tác tìm kiếmKhi chấm dứt quá trình tìm kiếm cũng chính là lúc tìm được chỗ cần thêmCách thực hiện:Tìm vị trí thêm (???)Thực hiện thêm (???) Binary Search Tree – ThêmThêm một phần tử vào cây:78int insertNode (Tree &T, DataType X){ if (T) { if (T->data == X) return 0; if (T->data > X) return insertNode(T->pLeft, X); else return insertNode(T->pRight, X); }T = new TNode;if (T == NULL) { coutdata = X;T->pLeft = T->pRight = NULL;return 1; }–1 : khi không đủ bộ nhớ0 : khi nút đã có1 : khi thêm thành côngThêm một phần tử x vào cây794418881337591081523405571Theâm X=5044 X59 > X5055 > X80 6 4 1 2 5 7 3Binary Search Tree – ThêmVí dụ tạo cây với dãy: 4, 6, 1, 2, 5, 7, 3Binary Search Tree – Thêm8130124951172256706865Ví dụ tạo cây với dãy: 30, 12, 17, 49, 22, 65, 51, 56, 70, 68Trắc nghiệmThe following items are inserted into a binary search tree: 3,6,5,2,4,7,1. Which node is the deepest?173482Bài tậpViết các hàm:Đếm số nút trên cây: CountNodeĐếm số nút lá: CountLeafĐếm số nút trong: CountInnerNodeXác định độ sâu/chiều cao của câyTìm giá trị nhỏ nhất/lớn nhất trên câyTính tổng các giá trị trên câyĐếm số nút có giá trị bằng xXuất các số nguyên tố trên cây83Binary Search Tree – Hủy một phần tử có khóa X 84Việc hủy một phần tử X ra khỏi cây phải bảo đảm điều kiện ràng buộc của CNPTKCó 3 trường hợp khi hủy nút X có thể xảy ra:X là nút láX chỉ có 1 con (trái hoặc phải)X có đủ cả 2 conBinary Search Tree – Hủy một phần tử có khóa X85Trường hợp 1: X là nút lá Chỉ đơn giản hủy X vì nó không móc nối đến phần tử nào khác4418881337591081523405571Hủy X=4023Binary Search Tree – Hủy một phần tử có khóa XTrường hợp 2: X chỉ có 1 con (trái hoặc phải) Trước khi hủy X ta móc nối cha của X với con duy nhất của nó8644188813375910815235571Hủy X=37Binary Search Tree – Hủy một phần tử có khóa XTrường hợp 3: X có đủ 2 con:Không thể hủy trực tiếp do X có đủ 2 con Hủy gián tiếp: Thay vì hủy X, ta sẽ tìm một phần tử thế mạng Y. Phần tử này có tối đa một conThông tin lưu tại Y sẽ được chuyển lên lưu tại XSau đó, nút bị hủy thật sự sẽ là Y giống như 2 trường hợp đầuVấn đề: chọn Y sao cho khi lưu Y vào vị trí của X, cây vẫn là CNPTK87Binary Search Tree – Hủy một phần tử có khóa XCách chọn phần tử thế mạng:Phần tử nhỏ nhất (trái nhất) trên cây con phải (của nút muốn xóa)Phần tử lớn nhất (phải nhất) trên cây con trái (của nút muốn xóa)Việc chọn lựa phần tử nào là phần tử thế mạng phụ thuộc vào ý thích của người lập trìnhỞ đây, ta sẽ chọn phần tử nhỏ nhất trên cây con phải làm phần tử thế mạng88Binary Search Tree – Hủy một phần tử có khóa XTrường hợp 3: X có đủ 2 con:Khi hủy phần tử X=18 ra khỏi cây: 894488133759108405571Hủy X=18302318XChọn phần tử nhỏ nhất trên cây con phải  phần tử 23 là phần tử thế mạng23Binary Search Tree – Hủy một phần tử có khóa X90Xóa 51Binary Search Tree – Hủy một phần tử có khóa X91Xóa 83Binary Search Tree – Hủy một phần tử có khóa X92Xóa 36Binary Search Tree – Hủy một phần tử có khóa X93Xóa nút gốc:Binary Search Tree – Hủy một phần tử có khóa X94Xóa nút gốc:42 là thế mạngBinary Search Tree – Hủy một phần tử có khóa X95Kết quả xóa:Binary Search Tree – Hủy một phần tử có khóa X96Xóa gốc 42Binary Search Tree – Hủy một phần tử có khóa XXóa gốc 4245 thế mạng97Binary Search Tree – Hủy một phần tử có khóa X98Kết quả xóa:Binary Search Tree – Hủy một phần tử có khóa XCác hàm dùng để hủy 1 phần tử:Hàm delNode trả về giá trị 1, 0 khi hủy thành công hoặc không có X trong cây: int delNode (Tree &T, DataType X)Hàm searchStandFor tìm phần tử thế mạng q và gán dữ liệu của q cho nút muốn xóa p void searchStandFor(Tree &p, Tree &q)99100Binary Search Tree – Hủy một phần tử có khóa XHủy một nútint delNode(Tree &T, DataType X){ if (T == NULL) return 0; if (T->data > X) return delNode(T->pLeft, X); if (T->data pRight, X); TNode* p = T; if (T->pLeft == NULL) T = T->pRight; else if (T->pRight == NULL) T = T->pLeft; else // T có đủ 2 con searchStandFor(p, T->pRight); delete p;}Binary Search Tree – Hủy một phần tử có khóa XTìm phần tử thế mạng (nhỏ nhất trên cây con phải):101void searchStandFor(Tree &p, Tree &q){ if (q->pLeft != NULL) searchStandFor (p, q->pLeft); else { p->data = q->data; p = q; q = q->pRight; }}Binary Search Tree – Hủy toàn bộ câyViệc toàn bộ cây có thể được thực hiện thông qua thao tác duyệt cây theo thứ tự sau. Nghĩa là ta sẽ hủy cây con trái, cây con phải rồi mới hủy nút gốc102void removeTree(Tree &T){ if (T) { removeTree(T->pLeft); removeTree(T->pRight); delete(T); }}Binary Search Tree103Nhận xét:Tất cả các thao tác searchNode, insertNode, delNode đều có độ phức tạp trung bình O(h), với h là chiều cao của cây Trong trong trường hợp tốt nhất, CNPTK có n nút sẽ có độ cao h = log2(n). Chi phí tìm kiếm khi đó sẽ tương đương tìm kiếm nhị phân trên mảng có thứ tựTrong trường hợp xấu nhất, cây có thể bị suy biến thành 1 danh sách liên kết (khi mà mỗi nút đều chỉ có 1 con trừ nút lá). Lúc đó các thao tác trên sẽ có độ phức tạp O(n)Vì vậy cần có cải tiến cấu trúc của CNPTK để đạt được chi phí cho các thao tác là log2(n)Đánh giá tìm kiếm104Đánh giá tìm kiếm1051, 2, 3, 4, 512345Bài tậpViết các hàm:Đếm số nút có đúng 1 conĐếm số nút có đúng 2 conĐếm số nguyên tố trên câyTính tổng các nút có đúng 1 conTính tổng các nút có đúng 2 conTính tổng các số chẵnNhập x, tìm giá trị nhỏ nhất trên cây mà lớn hơn xXuất số nguyên tố nhỏ nhất trên câyNhập x, tìm x trên cây,