Bài giảng Cấu trúc dữ liệu 1 - Chương 5: Cây - Lương Trần Hy Hiến

Nội dung text: Bài giảng Cấu trúc dữ liệu 1 - Chương 5: Cây - Lương Trần Hy Hiến

1. ði H c Sư Ph m Tp. H Ch í Minh Ni dung 1. Cây CU TR ÚC D LI U 1 2. Cây nh phân 3. Cây nh phân tìm kim 4. Cây cân bng Chương 5: CÂY 5. 1. Cây 5.1. Cây • ðnh ngh ĩa 1 : Cây là mt tp hp T các phn t (gi là nút ca cây) trong đĩ: – Cĩ 1 nút đc bit đưc gi là gc – Các nút cịn li đưc chia thành nhng tp ri nhau T1, T2 , , Tn theo quan h phân cp trong đĩ Ti cũng là mt cây. – Mi nút cp i s qun lý mt s nút cp i+1. Quan h này ngưi ta cịn gi là quan h chacon.
2. Ví d v cây 5.1. Cây • ðnh ngh ĩa 2 : cu trúc cây vi kiu cơ vn • ðnh ngh ĩa 2 s T là: – Mt nút cu trúc rng đưc gi là cây net edu org com rng (NULL). – Mt nút mà thơng tin chính ca nĩ cĩ kiu T, nĩ liên kt vi mt s hu hn các cu trúc cây khác cũng cĩ kiu cơ fpt hcmup java linux tuoitre s T. Các cu trúc này đưc gi là nhng cây con ca cây đang xét. Mt s thut ng Mt s thut ng Bc c a nút là s cây con c a Mc c a m t nút: mt nút
   Nút g c (T) =0 9 Bc c a m t cây là bc l n nh t
   Gi T , T , ,T là các cây con c a T ca các nút trên cây. 1 2 n 0 8 6
   Mc(T ) = M c(T ) = = M c(T ) = Nút g c là nút khơng cĩ nút 1 2 n Mc(T 0)+1 cha 5 4 3 2 9 Nút lá là nút cĩ bc b ng 0 Nút nhánh là nút cĩ bc khác 8 6 0 và khơng ph i là nút g c 5 4 3 2
3. Mt s thut ng 5.2. Cây nh phân • ð dài đưng đi t gc đn nút x : là s • ðnh ngh ĩa: Cây nh phân là cây mà mi nhánh cn đi qua k t gc đn x. • ð dài đưng đi tng ca cây : nút cĩ ti đa 2 cây con trong đĩ Px là đ dài đưng đi t gc đn X. • ð dài đưng đi trung bình : PI = PT/n (n là s nút trên cây T). • Rng cây : là tp hp nhiu cây trong đĩ th t các cây là quan trng. 5.2. Cây nh phân Ví d v ng dng ca cây nh phân * Cây con phi - - Cây con trái * 5 * + + 2 2 1 3 6 2 4 ((2+4)*25)*(2*1(3+6))
4. 5.2. Cây nh phân 5.2. Cây nh phân Mc • Chi u cao h • Cách 1 h=Max(m c)+1 – Thơng tin lưu tr ti nút. • Tính ch t – ða ch nút gc ca cây con tr ái trong b nh. – S nút nm mc i ≤≤≤ 2i. – S nút lá ≤≤≤ 2h1, vi h là – ða ch nút gc ca cây con ph i trong b nh. chiu cao ca cây. • Cách 2 – S nút trong cây ≤≤≤ 2h1. – Thơng tin lưu tr ti nút. – Chiu cao ca cây h > – ða ch nút cha ca cây log (s nút trong cây). 2 – ða ch nút gc ca cây con tr ái trong b nh. – ða ch nút gc ca cây con ph i trong b nh. 2h1=2 h1+2 h2+ +1 Biu din cây nh phân 5.2. Cây nh phân 5.2. Cây nh phân struct TNODE { DataType Key; TNODE *pLeft, *pRight; }; typedef TNODE* pTNODE; struct Tree { pTNODE Root; }; Trong đĩ DataType là kiu d liu ng vi thơng tin lưu ti nút Biu din cây nh phân Biu din cây nh phân
5. 5.2. Cây nh phân 5.2. Cây nh phân struct TNODE { DataType Key; TNODE* pParent; TNODE* pLeft; TNODE* pRight; }; typedef TNODE* TREE; Biu din cây nh phân Biu din cây nh phân 5.2. Cây nh phân 5.2. Cây nh phân • Duyt theo th t trưc void NLR(TREE Root) { (Node Left Right) NLR if (Root != NULL) • Duyt theo th t gia { ;//X lý theo nhu cu (Left Node Right) LNR NLR(Root>pLeft); • Duyt theo th t sau NLR(Root>pRight); } (Left Right Node) LRN } Duyt cây nh phân Duyt cây nh phân NLR
6. 5.2. Cây nh phân (3 + 1) ×3/(9 – 5 + 2) – (3 ×(7 – 4) + 6) = –13 5.2. Cây nh phân ,/,x,+,3,1,3,+,,9,5,2,+,x,3,,7,4,6 void L NR(TREE Root) { if (Root != NULL) { LNR(Root>Left); ; //X lý theo nhu cu LNR(Root>Right); } } Duyt cây nh phân NLR Duyt cây nh phân LNR 5.2. Cây nh phân (3 + 1) ×3/(9 – 5 + 2) – (3 ×(7 – 4) + 6) = –13 5.2. Cây nh phân 3,+,1,x,3,/,9,,5,+,2,,3,x,7,,4,+,6 void LR N (TREE Root) { if (Root != NULL) { LRN(Root>Left); LRN(Root>Right); ; //X lý theo nhu cu } } Duyt cây nh phân LNR Duyt cây nh phân LR N
7. 5.2. Cây nh phân (3 + 1) ×3/(9 – 5 + 2) – (3 ×(7 – 4) + 6) = –13 5.2. Cây nh phân 3,1,+,3,x,9,5,,2,+,/,3,7,4,,x,6,+, • Hãy so sánh thi gian tìm kim cho ba loi cu trúc d liu: – Mng – Danh sách liên kt – Cây nh phân Duyt cây nh phân LR N 5.3. Cây nh phân tìm kim 5.3. Cây nh phân tìm kim • ðnh nghĩa • Cây nh phân tìm kim (CNPTK) là cây nh phân trong đĩ ti mi nút, khĩa ca • Các thao tác trên cây nút đang xét ln hơn khĩa ca tt c các – Duyt cây nút thuc cây con trái và nh hơn khĩa – Tìm mt phn t trên cây ca tt c các nút thuc cây con phi – Thêm mt phn t vào cây • Nh ràng buc v khĩa trên CNPTK, vic – Hy mt phn t trên cây tìm kim tr nên cĩ đnh hưng. Hơn na, do cu trúc cây vic tìm kim tr – To mt cây nh phân tìm kim nên nhanh đáng k. Nu s nút trên cây – Hy tồn b cây nh phân tìm kim là N thì chi phí tìm kim trung bình ch khong log 2N ðnh nghĩa Cây nh phân tìm kim
8. 5.3. Cây nh phân tìm kim Dng 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 Ví d v Cây nh phân tìm kim D I 5.3. Cây nh phân tìm kim 5.3. Cây nh phân tìm kim • Thao tác duyt cây trên cây nh phân tìm kim hồn tồn ging như trên cây nh phân. • Khi duyt theo th t gia, trình t các nút duyt qua s cho ta mt dãy các nút theo th t tăng dn ca khĩa. Thao tác – Duyt cây Thao tác – Tìm mt phn t trên cây
9. 5.3. Cây nh phân tìm kim 5.3. Cây nh phân tìm kim TNODE * searchNode (TREE Root, DataType x) TNODE* SearchNode (TREE T, DataType X) { { TNODE *p = Root; if(T) while (p!= NULL) { ð quy { if(T>Key == X) if(x == p>Key) return T; return p; if(X Key) S dng vịng lp else đ tìm kim return SearchNode (T>pLeft, X); if(x Key) else p = p>pLeft; return SearchNode (T>pRight, X); else } p = p>pRight; return NULL; } } return NULL; Thao tác – Tìm mt phn t trên cây } Thao tác – Tìm mt phn t trên cây 5.3. Cây nh phân tìm kim 5.3. Cây nh phân tìm kim • Vic thêm mt phn t X vào cây phi Lưu ý phn t cĩ khĩa 55 Cịn cĩ 2 thành phn left,right bo đm điu kin ràng buc ca left==right==NULL (nút lá) CNPTK. • Ta cĩ th thêm vào nhiu ch khác nhau trên cây, nhưng nu thêm vào mt nút lá s là tin li nht do ta cĩ th thc hiên quá trình tương t thao tác tìm kim. • Khi chm dt quá trình tìm kim cũng chính là lúc tìm đưc ch cn thêm. Thao tác – Thêm mt phn t vào cây Thao tác – Thêm mt phn t vào cây
10. 5.3. Cây nh phân tìm kim 5.3. Cây nh phân tìm kim int insertNode (TREE &T, Data X) { • Cĩ 3 trưng hp xy ra if(T) { – X là nút lá. if(T>Key == X) – X ch cĩ 1 con (trái hoc phi). return 0; //đã cĩ if(T>Key > X) – X c ĩ đ c 2 con. 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; // thiu b nh T>Key = X; T>pLeft =T>pRight = NULL; return 1; //thêm vào thành cơng } Thao tác – Thêm mt phn t vào cây Thao tác – Xĩa mt phn t ra khi cây 5.3. Cây nh phân tìm kim 5.3. Cây nh phân tìm kim • X l à nút l á: ch đơn gin hy X vì nĩ khơng mĩc • X ch cĩ 1 con (tr ái ho c ph i) : trưc khi hy X ta ni đn phn t nào khác mĩc ni cha ca X vi con duy nht ca nĩ Thao tác – Xĩa mt phn t ra khi cây Thao tác – Xĩa mt phn t ra khi cây
11. 5.3. Cây nh phân tìm kim 5.3. Cây nh phân tìm kim • X c ĩ đ c 2 con : ta khơng th hy trc tip do X cĩ đ 2 con ⇒⇒⇒ Ta s hy gián tip. Thay vì hy X, ta s tìm mt ph n t th mng Y. Phn t này cĩ ti đa mt con. Thơng tin lưu ti Y s đưc chuyn lên lưu ti X. Sau đĩ, nút b hy tht s s là Y ging như 2 trưng hp đu • Vn đ là phi chn Y sao cho khi lưu Y vào v trí ca X, cây vn là CNPTK. Cĩ 2 phn t tha mãn yêu cu: – Phn t nh nht ( tr ái nh t) trên cây con ph i. Cĩ th dùng 15 – Phn t ln nht ( ph i nh t) trên cây con tr ái. đ th mng Thao tác – Xĩa mt phn t ra khi cây Thao tác – Xĩa mt phn t ra khi cây 5.3. Cây nh phân tìm kim 5.3. Cây nh phân tìm kim • Ta cĩ th to mt cây nh phân tìm kim • Vic tồn b cây bng cách lp li quá trình thêm 1 phn cĩ th đưc thc void removeTree (TREE T) t vào mt cây rng hin thơng qua { thao tác duyt if(T) 44,18,88,13,37,59,108,15,23,40,55,71 cây theo th t { sau. Nghĩa là ta removeTree (T>pLeft); s hy cây con removeTree (T>pRight); trái, cây con delete(T); phi ri mi hy } nút gc. } Thao tác – Hy tồn b cây Thao tác – To cây nh phân tìm kim
12. 5.3. Cây nh phân tìm kim 5.4. Cây nh phân cân bng • Cây nh phân cân bng hồn tồn 1. Khi nào thì cây thì cây suy – ðnh nghĩa bin thành danh sách liên kt? – ðánh giá • Cây nh phân cân bng ( AVL ) AdelsonVelskii và Landis (Nga 1962) – ðnh nghĩa 2. ð khc phc điu này ta cn – Chiu cao cây AVL làm gì? – Cu trúc d liu – ðánh giá cây AVL 5.4. Cây nh phân cân bng 5.4. Cây nh phân cân bng • ðnh ngh ĩa: Cây cân bng hồn tồn là cây nh • ðánh gi á phân tìm kim mà ti mi nút ca nĩ, s nút – Mt cây rt khĩ đt đưc trng thái cân bng hồn tồn và cũng rt d mt cân bng vì khi ca cây con trái chênh lch khơng quá mt so thêm hay hy các nút trên cây cĩ th làm cây vi s nút ca cây con phi mt cân bng (xác sut rt ln), chi phí cân bng li cây ln vì phi thao tác trên tồn b cây. – Trong trưng hp xu nht ta ch phi tìm Cây Cân B ng Ho àn To àn qua log 2n phn t (n là s nút trên cây). – Do CCBHT là mt cu trúc kém n đnh nên Cây CCBHT thì h ~ log n 2 trong thc t khơng th s dng. Nhưng ưu đim ca nĩ li rt quan trng. Vì vy, cn đưa ra mt CTDL khác cĩ đc tính ging CCBHT nhưng n đnh hơn. Cây nh phân tìm kim cân b ng ho àn to àn Cây nh phân tìm kim cân b ng ho àn to àn
13. 5.4. Cây nh phân cân bng 5.4. Cây nh phân cân bng • ðnh ngh ĩa: Cây nh phân tìm kim cân bng là cây mà ti mi nút ca nĩ đ cao ca cây con Cây CBHT???? trái và ca cây con phi chênh lch khơng quá mt. Cây AVL Cây nh phân tìm kim cân bng AVL Cây nh phân tìm kim cân bng AVL 5.4. Cây nh phân cân bng 5.4. Cây nh phân cân bng • Chi u cao cây AVL • Chi u cao cây AVL – Ta phi khng đnh cây AVL n nút phi cĩ – Gi N(h) là s nút ti thiu ca cây AVL cĩ chiu cao khong log 2(n). chiu cao h. – Ta cĩ N(0) = 0, N(1) = 1 và N(2) = 2. – ð đánh giá chính xác v chiu cao ca cây – Cây AVL ti thiu cĩ chiu cao h s cĩ: AVL, ta xét bài tốn: cây AVL cĩ chiu cao • 1 cây con AVL ti thiu chiu cao h1 h s phi cĩ ti thiu bao nhiêu nút? • 1 cây con AVL ti thiu chiu cao h2 – Như vy: N(h) = 1 + N(h1) + N(h2) Cây nh phân tìm kim cân bng AVL Cây nh phân tìm kim cân bng AVL
14. 5.4. Cây nh phân cân bng 5.4. Cây nh phân cân bng • Chi u cao cây AVL Cây AVL ti thiu cĩ chiu cao 4 – Ta li cĩ: N(h1) > N(h2) nên: • N(h) > 2N(h2) • N(h) > 2 2N(h4) • ð h2i=1 thì i=(h1)/2 • N(h) > 2 iN(h2i) – Suy ra: N(h) > 2 (h1)/2 – Hay h1 • ðánh gi á ð cao cây trái (p) = ð { – Cây cân bng là CTDL n đnh hơn hn cao cây phi (p) CCBHT vì ch khi thêm hy làm cây thay đi char balFactor; • CSCB(p) = 1 chiu cao các trưng hp mt cân bng Data key; ð cao cây trái (p) – Cây AVL vi chiu cao đưc khng ch s AVLNode* pRight; ð cao cây trái (p) > ð cho phép thc thi các thao tác tìm thêm }; cao cây phi (p) hy vi chi phí O(log 2(n)) và bo đm typedef AVLNode *AVLTree; khơng suy bin thành O(n) . balFactor ==CSCB(p) Cu trúc d liu cho cây AVL
15. 5.4. Cây nh phân cân bng 5.4. Cây nh phân cân bng • Các trư ng h p m t cân b ng • Trư ng h p 1 : cây T lch v bên trái(cĩ 3 kh • Các trư ng h p m t cân b ng năng) – Ta s khơng kho sát tính cân bng ca 1 cây nh phân bt kỳ mà ch quan tâm đn các kh năng mt cân bng xy rakhi thêm hoc hy mt nút trên cây AVL. – Như vy, khi mt cân bng, đ lch chiu cao gia 2 cây con s là 2. Ta cĩ 6 kh năng (chia làm 2 trưng hp). Cây nh phân tìm kim cân bng AVL Cây nh phân tìm kim cân bng AVL 5.4. Cây nh phân cân bng 5.4. Cây nh phân cân bng • Hư ng gi i quy t ca 2 trưng hp là tương t • Trư ng h p 2 : cây T lch v bên phi(cĩ 3 kh nhau nên ta ch gii quyt trư ng h p 1 năng) Quay đơn Left Left Cây nh phân tìm kim cân bng AVL Cây nh phân tìm kim cân bng AVL
16. 5.4. Cây nh phân cân bng 5.4. Cây nh phân cân bng Quay kép Left Right Quay đơn Left Left Cây nh phân tìm kim cân bng AVL Cây nh phân tìm kim cân bng AVL Ni dung ơn thi Ni dung ơn thi • Thc hành • Lý thuyt – Thut tốn sp xp, tìm kim – Thêm code vào các thut tốn đ thc hin • Tìm kim • Thc hin tng bưc kt qu ca thut tốn mt yêu cu nào đĩ (HeapSort,MergeSort, ) – Danh sách liên kt • ShakerSort cĩ nhng ci tin gì so vi BubleSort – Danh sách liên kt • T chc CTDL: phân s, đa thc 1 bin, qun lý • Lý do s dng CTDL đng sinh viên • T chc d liu cho mt bài tốn nào nào đĩ > nêu hưng • Sp xp theo mt th t nào đĩ gii quyt (t đin, đa thc, ) • Chuyn trung t  hu t, đnh tr hu t – Cây • Dng cây, Duyt Cây • Thêm, Xĩa phn t cho cây • Hi cây