Cấu trúc dữ liệu - Chương 5: Cây

ðại Học Sư Phạm Tp. Hồ Chí Minh Chương 5: CÂY CẤU TRÚC DỮ LIỆU 1 Nội dung 1. Cây 2. Cây nhị phân 3. Cây nhị phân tìm kiếm 4. Cây cân bằng 5. 1. Cây • ðịnh nghĩa 1: 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ó 1 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. –Mỗi nút ở cấp i sẽ quản lý một số nút ở cấp i+1. Quan hệ này người ta còn gọi là quan hệ cha-con. 5.1. Cây Ví dụ về cây vn comnet edu org java linuxfpt hcmup tuoitre 5.1. Cây • ðịnh nghĩa 2: cấu trúc cây với kiểu cơ sở T là: –Một nút cấu trúc rỗng ñược gọi là cây rỗng (NULL). –Một nút mà thông tin chính của nó có kiểu T, nó liên kết với một số hữu hạn các cấu trúc cây khác cũng có kiểu cơ sở T. Các cấu trúc này ñược gọi là những cây con của cây ñang xét. Bậc của nút là số cây con của một nút Bậc của một cây là bậc lớn nhất của các nút trên cây. Nút gốc là nút không có nút cha Nút lá là nút có bậc bằng 0 Nút nhánh là nút có bậc khác 0 và không phải là nút gốc 9 8 6 5 4 3 2 Một số thuật ngữ Mức của một nút:
Nút gốc (T) =0
Gọi T1, T2,,Tn là các cây con của T0
Mức(T1) = Mức(T2) = = Mức(Tn) = Mức(T0)+1 9 8 6 5 4 3 2 Một số thuật ngữ Một số thuật ngữ • ðộ 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. • ðộ 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ọng. 5.2. Cây nhị phân • ðịnh nghĩa: Cây nhị phân là cây mà mỗi nút có tối ña 2 cây con 5.2. Cây nhị phân Cây con trái Cây con phải Ví dụ về ứng dụng của cây nhị phân * - - * 5 3 + + 2 4 * 2 1 62 ((2+4)*2-5)*(2*1-(3+6)) 5.2. Cây nhị phân • Chiều cao h h=Max(mức)+1 • Tính chất – Số nút nằm ở mức i ≤ 2i. – Số nút lá ≤ 2h-1, với h là chiều cao của cây. – Số nút trong cây ≤ 2h-1. – Chiều cao của cây h > log2(số nút trong cây). 2h-1=2h-1+2h-2++1 Mức 5.2. Cây nhị phân • Cách 1 – Thông tin lưu trữ tại nút. – ðịa chỉ nút gốc của cây con trái trong bộ nhớ. – ðịa chỉ nút gốc của cây con phải trong bộ nhớ. • Cách 2 – Thông tin lưu trữ tại nút. – ðịa chỉ nút cha của cây – ðịa chỉ nút gốc của cây con trái trong bộ nhớ. – ðịa chỉ nút gốc của cây con phải trong bộ nhớ. Biểu diễn cây nhị phân 5.2. Cây nhị phân Biểu diễn cây nhị phân struct TNODE { DataType Key; TNODE *pLeft, *pRight; }; typedef TNODE* pTNODE; struct Tree{ pTNODE Root; }; Trong ñó DataType là kiểu dữ liệu ứng với thông tin lưu tại nút 5.2. Cây nhị phân Biểu diễn cây nhị phân 5.2. Cây nhị phân Biểu diễn cây nhị phân struct TNODE { DataType Key; TNODE* pParent; TNODE* pLeft; TNODE* pRight; }; typedef TNODE* TREE; 5.2. Cây nhị phân Biểu diễn cây nhị phân 5.2. Cây nhị phân Duyệt cây nhị phân • Duyệt theo thứ tự trước (Node-Left-Right) - NLR • Duyệt theo thứ tự giữa (Left- Node-Right) - LNR • Duyệt theo thứ tự sau (Left-Right-Node) - LRN 5.2. Cây nhị phân Duyệt cây nhị phân - NLR voidNLR(TREE Root) { if (Root != NULL) { ;//Xử lý theo nhu cầu NLR(Root->pLeft); NLR(Root->pRight); } } 5.2. Cây nhị phân Duyệt cây nhị phân - NLR -,/,x,+,3,1,3,+,-,9,5,2,+,x,3,-,7,4,6 (3 + 1)×3/(9 – 5 + 2) – (3×(7 – 4) + 6) = –13 5.2. Cây nhị phân Duyệt cây nhị phân - LNR void LNR(TREE Root) { if (Root != NULL) { LNR(Root->Left); ; //Xử lý theo nhu cầu LNR(Root->Right); } } 5.2. Cây nhị phân Duyệt cây nhị phân - LNR 3,+,1,x,3,/,9,-,5,+,2,-,3,x,7,-,4,+,6 (3 + 1)×3/(9 – 5 + 2) – (3×(7 – 4) + 6) = –13 5.2. Cây nhị phân Duyệt cây nhị phân - LRN void LRN (TREE Root) { if (Root != NULL) { LRN(Root->Left); LRN(Root->Right); ; //Xử lý theo nhu cầu } } 5.2. Cây nhị phân Duyệt cây nhị phân - LRN (3 + 1)×3/(9 – 5 + 2) – (3×(7 – 4) + 6) = –13 3,1,+,3,x,9,5,-,2,+,/,3,7,4,-,x,6,+,- 5.2. Cây nhị phân • Hãy so sánh thời gian tìm kiếm cho ba loại cấu trúc dữ liệu: –Mảng – Danh sách liên kết – Cây nhị phân 5.3. Cây nhị phân tìm kiếm • ðịnh nghĩa • Các thao tác trên cây – Duyệt cây – Tìm một phần tử trên cây – Thêm một phần tử vào cây – Hủy một phần tử trên cây – Tạo một cây nhị phân tìm kiếm – Hủy toàn bộ cây nhị phân tìm kiếm 5.3. Cây nhị phân tìm kiếm • Câ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ải • Nhờ ràng buộc về khóa trên CNPTK, việc tìm kiếm trở nên có ñịnh hướng. Hơn nữa, do cấu trúc cây việc tìm kiếm trở nên nhanh ñáng kể. Nếu số nút trên cây là N thì chi phí tìm kiếm trung bình chỉ khoảng log2N ðịnh nghĩa Cây nhị phân tìm kiếm 5.3. Cây nhị phân tìm kiếm Ví dụ về Cây nhị phân tìm kiếm Dựng cây nhị phân LNR: B C D F A G I H E NLR: A C B F D H G I E A C H B F G E D I 5.3. Cây nhị phân tìm kiếm • Thao tác duyệt cây trên cây nhị phân tìm kiếm hoàn toàn giống như trên cây nhị phân. • 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. Thao tác – Duyệt cây 5.3. Cây nhị phân tìm kiếm Thao tác – Tìm một phần tử trên cây 5.3. Cây nhị phân tìm kiếm Thao tác – Tìm một phần tử trên cây TNODE* SearchNode(TREE T, DataType X) { if(T) { if(T->Key == X) return T; if(XKey) return SearchNode(T->pLeft, X); else return SearchNode(T->pRight, X); } return NULL; } ðệ quy 5.3. Cây nhị phân tìm kiếm Thao tác – Tìm một phần tử trên cây TNODE * searchNode(TREE Root, DataType x) { TNODE *p = Root; while (p!= NULL) { if(x == p->Key) return p; else if(x Key) p = p->pLeft; else p = p->pRight; } return NULL; } Sử dụng vòng lặp ñể tìm kiếm 5.3. Cây nhị phân tìm kiếm Thao tác – Thêm một phần tử vào cây • Việ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 CNPTK. • Ta 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 lá 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ếm. • Khi 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êm. 5.3. Cây nhị phân tìm kiếm Thao tác – Thêm một phần tử vào cây Lưu ý phần tử có khóa 55 Còn có 2 thành phần left,right left==right==NULL (nút lá) 5.3. Cây nhị phân tìm kiếm Thao tác – Thêm một phần tử vào cây int insertNode(TREE &T, Data X) { if(T) { if(T->Key == X) return 0; //ñã có if(T->Key > X) return insertNode(T->pLeft, X); else return insertNode(T->pRight, X); } //Khi T==NULL thì thêm vào T = new TNode; if(T == NULL) return -1; //thiếu bộ nhớ T->Key = X; T->pLeft =T->pRight = NULL; return 1; //thêm vào thành công } 5.3. Cây nhị phân tìm kiếm Thao tác – Xóa một phần tử ra khỏi cây • Có 3 trường hợp xảy ra – X là nút lá. – X chỉ có 1 con (trái hoặc phải). – X có ñủ cả 2 con. 5.3. Cây nhị phân tìm kiếm • 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ác Thao tác – Xóa một phần tử ra khỏi cây 5.3. Cây nhị phân tìm kiếm • 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ó Thao tác – Xóa một phần tử ra khỏi cây 5.3. Cây nhị phân tìm kiếm • X có ñủ cả 2 con: ta không thể hủy trực tiếp do X có ñủ 2 con ⇒ Ta sẽ 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 con. Thông tin lưu tại Y sẽ ñược chuyển lên lưu tại X. Sau ñó, nút bị hủy thật sự sẽ là Y giống như 2 trường hợp ñầu • Vấn ñề là phải chọn Y sao cho khi lưu Y vào vị trí của X, cây vẫn là CNPTK. Có 2 phần tử thỏa mãn yêu cầu: – Phần tử nhỏ nhất (trái nhất) trên cây con phải. – Phần tử lớn nhất (phải nhất) trên cây con trái. Thao tác – Xóa một phần tử ra khỏi cây 5.3. Cây nhị phân tìm kiếm Thao tác – Xóa một phần tử ra khỏi cây Có thể dùng 15 ñể thế mạng 5.3. Cây nhị phân tìm kiếm • Ta có thể tạo một cây nhị phân tìm kiếm bằng cách lặp lại quá trình thêm 1 phần tử vào một cây rỗng 44,18,88,13,37,59,108,15,23,40,55,71 Thao tác – Tạo cây nhị phân tìm kiếm 5.3. Cây nhị phân tìm kiếm • Việ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ốc. void removeTree(TREE T) { if(T) { removeTree(T->pLeft); removeTree(T->pRight); delete(T); } } Thao tác – Hủy toàn bộ cây 5.3. Cây nhị phân tìm kiếm 1. Khi nào thì cây thì cây suy biến thành danh sách liên kết? 2. ðể khắc phục ñiều này ta cần làm gì? 5.4. Cây nhị phân cân bằng • Cây nhị phân cân bằng hoàn toàn – ðịnh nghĩa – ðánh giá • Cây nhị phân cân bằng (AVL) Adelson-Velskii và Landis (Nga - 1962) – ðịnh nghĩa – Chiều cao cây AVL – Cấu trúc dữ liệu – ðánh giá cây AVL 5.4. Cây nhị phân cân bằng • ðịnh nghĩa: Cây cân bằng hoàn toàn là cây nhị phân tìm kiếm mà tại mỗi nút của nó, số nút của cây con trái chênh lệch không quá một so với số nút của cây con phải Cây nhị phân tìm kiếm cân bằng hoàn toàn Cây Cân Bằng Hoàn Toàn Cây CCBHT thì h ~ log2n 5.4. Cây nhị phân cân bằng • ðánh giá – Một cây rất khó ñạt ñược trạng thái cân bằng hoàn toàn và cũng rất dễ mất cân bằng vì khi thêm hay hủy các nút trên cây có thể làm cây mất cân bằng (xác suất rất lớn), chi phí cân bằng lại cây lớn vì phải thao tác trên toàn bộ cây. – Trong trường hợp xấu nhất ta chỉ phải tìm qua log2n phần tử (n là số nút trên cây). – Do CCBHT là một cấu trúc kém ổn ñịnh nên trong thực tế không thể sử dụng. Nhưng ưu ñiểm của nó lại rất quan trọng. Vì vậy, cần ñưa ra một CTDL khác có ñặc tính giống CCBHT nhưng ổn ñịnh hơn. Cây nhị phân tìm kiếm cân bằng hoàn toàn 5.4. Cây nhị phân 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. Cây nhị phân tìm kiếm cân bằng AVL Cây AVL 5.4. Cây nhị phân cân bằng Cây nhị phân tìm kiếm cân bằng AVL 5.4. Cây nhị phân cân bằng • Chiều cao cây AVL – Ta lại có: N(h-1) > N(h-2) nên: • N(h) > 2N(h-2) • N(h) > 22N(h-4) • • N(h) > 2iN(h-2i) – Suy ra: N(h) > 2 (h-1)/2 – Hay h-1 < 2*log2(N(h)) tức là h < 2*log2(N(h)) + 1= 2*log2(n)+1 – Vậy cây AVL có chiều cao O(log2(n)) Cây nhị phân tìm kiếm cân bằng AVL ðể h-2i=1 thì i=(h-1)/2 5.4. Cây nhị phân cân bằng Cây nhị phân tìm kiếm cân bằng AVL Cây AVL tối thiểu có chiều cao 4 5.4. Cây nhị phân cân bằng struct AVLNode { char balFactor; Data key; AVLNode* pLeft; AVLNode* pRight; }; typedef AVLNode *AVLTree; • CSCB(p) = 0 ðộ cao cây trái (p) = ðộ cao cây phải (p) • CSCB(p) = 1 ðộ cao cây trái (p) < ðộ cao cây phải (p) • CSCB(p) =-1 ðộ cao cây trái (p) > ðộ cao cây phải (p) Cấu trúc dữ liệu cho cây AVL balFactor ==CSCB(p) 5.4. Cây nhị phân cân bằng • ðánh giá – Cây cân bằng là CTDL ổn ñịnh hơn hẳn CCBHT vì chỉ khi thêm hủy làm cây thay ñổi chiều cao các trường hợp mất cân bằng mới có khả năng xảy ra. – Cây AVL với chiều cao ñược khống chế sẽ cho phép thực thi các thao tác tìm thêm hủy với chi phí O(log2(n)) và bảo ñảm không suy biến thành O(n). 5.4. Cây nhị phân cân bằng • Các trường hợp mất cân bằng – Ta sẽ không khảo sát tính cân bằng của 1 cây nhị phân bất kỳ mà chỉ quan tâm ñến các khả năng mất cân bằng xảy rakhi thêm hoặc hủy một nút trên cây AVL. – Như vậy, khi mất cân bằng, ñộ lệch chiều cao giữa 2 cây con sẽ là 2. Ta có 6 khả năng (chia làm 2 trường hợp). Cây nhị phân tìm kiếm cân bằng AVL 5.4. Cây nhị phân cân bằng • Trường hợp 1: cây T lệch về bên trái(có 3 khả năng) Cây nhị phân tìm kiếm cân bằng AVL 5.4. Cây nhị phân cân bằng • Trường hợp 2: cây T lệch về bên phải(có 3 khả năng) Cây nhị phân tìm kiếm cân bằng AVL 5.4. Cây nhị phân cân bằng • Hướng giải quyết của 2 trường hợp là tương tự nhau nên ta chỉ giải quyết trường hợp 1 Cây nhị phân tìm kiếm cân bằng AVL Quay ñơn Left - Left 5.4. Cây nhị phân cân bằng Cây nhị phân tìm kiếm cân bằng AVL Quay ñơn Left - Left 5.4. Cây nhị phân cân bằng Cây nhị phân tìm kiếm cân bằng AVL Quay kép Left - Right Nội dung ôn thi • Thực hành – Thêm code vào các thuật toán ñể thực hiện một yêu cầu nào ñó – Danh sách liên kết • Tổ chức CTDL: phân số, ña thức 1 biến, quản lý sinh viên • Sắp xếp theo một thứ tự nào ñó Nội dung ôn thi • Lý thuyết – Thuật toán sắp xếp, tìm kiếm • Tìm kiếm • Thực hiện từng bước kết quả của thuật toán (HeapSort,MergeSort, ) • ShakerSort có những cải tiến gì so với BubleSort – Danh sách liên kết • Lý do sử dụng CTDL ñộng • Tổ chức dữ liệu cho một bài toán nào nào ñó -> nêu hướng giải quyết (từ ñiển, ña thức, ) • Chuyển trung tố  hậu tố, ñịnh trị hậu tố – Cây • Dựng cây, Duyệt Cây • Thêm, Xóa phần tử cho cây • Hỏi cây