Chương 5: Cây ( Tree)

CH

NG V CÂY (TREE)

ƯƠ

ụ ề ấ

1. M t s khái ni m ệ ộ ố 1.1. Đ nh nghĩa ị 1.2. Các ví d v c u trúc cây 1.3. Các khái ni mệ

2. Cây nh phân

ị

ổ

ị 2.1. Đ nh nghĩa ị 2.2. Tính ch tấ 2.3. Bi u di n cây nh phân ễ ể 2.4.* Cây k-phân 2.5.* Cây t ng quát 3. Cây tìm ki m nh phân ị ế b ph n 4. Cây có th t ứ ự ộ

ậ

ầ

ệ

ấ



1. M t s khái ni m ộ ố ệ

1.1. Đ nh nghĩa ị C= V: T p h u h n các ph n ữ ậ ạ (nút) t ử E: T p h u h n(cung) th ể ạ ữ ậ hi n m i quan h ệ ố phân c p là quan h ệ “ cha – con”. Nút g c (root). ố Cây r ng (null tree) ỗ

1. M t s khái ni m

ộ ố

ệ

ị ệ

ỗ ộ

ủ ố

Đ nh nghĩa đ quy:  M i nút là m t cây  n là nút và n1, n2,...,nk là g c c a các (không có nút

 n là cha c a các nút n1, n2,….,nk thì

cây C1,C2,…Ck; chung).

ủ

có m t cây m i C. ớ ộ

ố

ụ ụ ủ ấ

1. M t s khái ni m ộ ố ệ

b) Các ví d v c u trúc cây ụ ề ấ  M c l c c a m t cu n sách ộ  C u trúc th m c trên đĩa máy tính. ư ụ  Dùng cây đ bi u di n bi u th c s h c, ể ể

ứ ố ọ

ể

ễ

ẳ

ạ

ch ng h n: ( a+b) x (c-d/e)

ườ

ng đ i h c ạ ọ

Khu A

Khu B

. . .

Khoa 2

Khoa 1

Khoa N

Khoa 1

Khoa M

. . . . .

Gi ng viên

ả

. . . . .

Sinh viên chính qui

Sinh viên t i ch c ạ

ứ

ố

ủ

ấ

ọ

ộ

ủ ằ

ấ

1. M t s khái ni m ộ ố ệ

c) Các khái ni m ệ i) S các con c a m t nút g i là c p c a nút đó ii) Nút có c p b ng 0 g i là nút lá (leaf) ọ iii) Các nút không ph i nút lá g i là nút nhánh ọ

ả

( branch)

iv) C p cao nh t có trong các nút c a m t cây g i là

ủ

ộ

ọ

ấ

ấ c p c a cây đó. ấ

ủ

ủ ế ộ

ủ ứ

V)G c c a cây có m c 1, n u m t nút có ố ứ m c i thì các nút con c a nút đó có m c ứ i+1.

vi) Chi u cao (height) c a cây là s m c ứ ủ ề

ố cao nh t c a các nút có trên cây đó

vii) T p h p các cây phân bi t g i là m t ậ ệ ọ ộ ấ ủ ợ

r ng (forest). ừ

ị

a) Đ nh nghĩa:  Cây nh phân

2. Cây nh phân (Binary tree) ị

ị

ủ

ọ

là cây mà m i nút c a nó có i đa hai cây con. V i m i nút xác đ nh cây

ỗ

ị

ớ

t ố con trái và cây con ph i.ả

. Cây nh phân (Binary tree) ị

ị

ế :  Cây nh phân suy bi n cây l ch trái, cây l ch ph i, cây dích ả ệ

ệ d c.ắ

2. Cây nh phân (Binary tree) ị

ị

ỉ

 Cây nh phân hoàn ch nh ề

ứ

(complete binary tree) có chi u cao là h thì m i nút có m c < ọ h-1 đ u có đúng 02 nút con.

ề

2. Cây nh phân (Binary tree) ị

ầ ủ ( full Binary tree)

ị

 Cây nh phân đ y đ có chi u cao h thì m i nút có m c

ứ <=h-1 đ u có

ề

ọ

đúng 02 nút con

2. Cây nh phân (Binary tree) ị

b) M t s các tính ch t:

ấ

ị ị

ng nút là nh nhau thì cây nh phân ư suy bi n có chi u cao l n nh t, cây nh phân ấ ớ ề đ y đ có chi u cao nh nh t. ỏ ề

ấ

i đa các nút trên m c i là 2

i-1 và t

ố

ứ

i ố

ng t thi u là 1 ( i>=1)

ộ ố  N u s l ố ượ ế ế ủ ầ  S l ố ượ ể

ng t

i đa các nút trên cây nh phân có

ố

ị

h-1 và t

 S l ố ượ ề

ể

i thi u là h ( h>=1) ố  Cây nh phân hoàn ch nh có n nút thì chi u ỉ

chi u cao h là 2 ị

ề

cao c a nó là h=[ lg(n)] +1

ủ

ả

ễ

2. Cây nh phân (Binary tree) ị

ể ể

các nút i” và “trái

ố ứ ự ướ

c) Bi u di n cây nh phân ị ễ  Bi u di n b ng m ng: ằ  Đánh s th t theo “ trên – d – ph i”.ả  V i nút i thì

ớ

ủ

 nút con trái c a nó 2i và nút con ph i là 2i+1. ả

A B E C D F G

 Nút cha là [i/2].

ể

 Bi u di n b ng danh sách liên k t ế

i nút con trái

ằ ng Data l u giá tr ị ư ng Left ch a liên k t tr t ứ

ế ỏ ớ

 M t tr

ng Right ch a liên k t tr t

i nút con

ỏ ớ

ứ

ế

ễ  M t tr ộ ườ  M t tr ộ ườ ho c Null. ặ ộ ườ ph i ho c Null. ả ặ ư ậ

ủ

ẽ

ầ

 Nh v y nút g c s là nút đ u tiên c a danh ng Left và

ườ

ố sách móc n i, v i các nút lá các tr ố ớ Right đ u ch a giá tr Null. ứ

ề

ị

2. Cây nh phân (Binary tree) ị

ệ

ị

c (preorder

d) Duy t cây nh phân Cách 1. Duy t theo th t ệ

tr ứ ự ướ

traversal)  Nút đang xét  Cây con trái  Cây con ph i.ả

Tree Traversal

‹

ﬁ

• Traversal = visiting every node of a tree • Three basic alternatives ˚ Pre-order • Root • Left sub-tree • Right sub-tree

›

ﬂ

(cid:176)

x A + x + B C x D E F

R

L R L L

gi a (inorder Cách 2. Duy t theo th t ệ ứ ự ữ

traversal)  Cây con traí  Nút dang xét  Cây con ph i. ả

Tree Traversal

• Traversal = visiting every node of a tree • Three basic alternatives ¸In-order

›

• Left sub-tree • Root • Right sub-tree

(cid:181) ‹

–

11

‡ ﬂ

A x B + C x D x E + F

ﬁ † (cid:176)

L

L R

sau (postorder Cách 3. Duy t theo th t ệ ứ ự

traversal)  Cây con trái  Cây con ph iả  Nút đang xét.

Tree Traversal

• Traversal = visiting every node of a tree • Three basic alternatives (cid:204) Post-order

11

• Left sub-tree • Right sub-tree • Root

(cid:181) ‹

‡

ﬂ †

A B C + D E x x F + x

– › (cid:176) ﬁ

L L R

2. Cây nh phân (Binary tree) ị

e) Cây k-phân m i nút có không quá k ỗ

nút con.

ƯƠ

NG V: CÂY (TREE) CH 2. Cây nh phân (Binary tree)

ể

ả

ị

e) Cây k-phân  Bi u di n cây k-phân b ng m ng ễ  B sung thêm m t s nút gi ả

ằ ộ ố

ỗ

ề

ề t ứ ự ừ

ế

ấ

sao cho m i nút ổ c a cây đ u có đúng k nút con, các nút con đ u ủ x p th t nút con th nh t cho đ n nút con ứ ế th k.ứ

 Đánh s th t

trên cây cũng theo nguyên t c “

ắ

ả

ố ứ ự ố

là k.i

trên-xu ng” và “ trái ph i”  Nút con th j c a nút i s có s th t ứ

ố ứ ự

ủ

ẽ

 N u i không ph i là nút g c thì nút cha c a

ủ

ả

ố

+j. ế

nút I là [( i-1)/k]

 Dùng m ng C đ l u tr cây thì C[i] s l u tr ữ

ẽ ư

ữ

ể ư giá tr c a nút th i. ứ

ả ị ủ

 Bi u di n cây k-phân b ng DS liên k t ế ễ ng Data ghi giá tr c a nút.

ườ

ằ ị ủ

ng, tr

ng j là liên k t tr đ n nút con ng h p không có

ườ ứ ủ

ế ỏ ế ợ ườ

ườ th j c a nút đang xét. Tr nút con thì ghi giá tr null.

ị

ể  Tr  K tr

2. Cây nh phân (Binary tree) ị

f) Cây t ng quát ổ  Đ nh nghĩa: cây không h n ch s l

ng nút con

ế ố ượ

ạ

ị c a m i nút. ỗ ủ ễ ể

 Bi u di n cây t ng quát b ng m ng ổ

ả

ượ

c gán m t s th t ữ ệ

ộ ấ

ể

ọ

, ph n t

Data[i]

ằ Cho cây có n nút, các nút đ ộ ố ứ ự tùy ch n. Ta có th xây d ng m t c u trúc d li u ự nh sau:  M t m ng Data g m n ph n t ộ

ầ ử

ả

ồ l u giá tr c a nút i ư

ị ủ

ạ

ả

ộ

ỉ ố

ộ ồ

ư ậ

ớ

ầ ạ

ứ

ẽ

ớ

. Head[i] là v trí

ị

c Head[n+1]=n-1

c đo n i. Quy

ướ

 M t m ng Children chia thành n đo n, đo n th ứ i g m m t dãy liên ti p các ch s các nút con ế c a nút i. Nh v y m ng Children s có n ph n ủ ẽ ả ng ng v i lá s là đo n ( v i các đo n t t ạ ươ ử r ng, không có nút con). ỗ ộ ứ ộ

 M t m ng Head g m n ph n t ầ ử ướ  M t bi n l u ch s c a nút g c ố

ả đ ng li n tr ề ế ư

ồ ạ ỉ ố ủ

ế

f) Cây t ng quát  L u tr cây t ng quát b ng danh sách liên k t: ổ

ứ

ằ ị ủ

ư Tr ườ  Tr ườ

ỏ ế

ứ

ầ

ế

 Tr

ổ ữ ng Data ch a giá tr c a nút ng FirstChild ch a liên k t tr đ n nút con đ u ế tiên c a nút t ng ng. N u nút không có con thì ghi ươ ứ ủ t là Null. giá tr đ c bi ệ ị ặ ng Sibling ch a liên k t tr t ứ

ế ỏ ớ

ế ậ

ế

t null.

i nút em k c n bên ườ ph i ( nút cùng cha). N u không có nút em thì ghi giá ả tr đ c bi ị ặ

ệ

2. Cây nh phân (Binary tree) ị

ấ ằ ự

ừ ộ ư ậ ể

ế ả

 B ng cách xây d ng c u trúc nh v y rõ m t nút i b t kì ta có th đi theo ràng là t ấ liên k t FirstChild đ đ n nút con c sau ể ế đó đi theo liên k t Sibling ta có th duy t qua t

ế ể ệ

t c các nút con c a nút i. ấ ả ủ

3. Cây tìm ki m nh phân ế ị

ị

a) Đ nh nghĩa Là m t cây nh phân:  Giá tr c a các nút c a cây con trái nh h n giá

ỏ ơ

ủ

ị ủ

ố

 Giá tr c a các nút cây con ph i l n h n giá tr ị

ả ớ

ộ ị ủ tr c a nút g c; ị ủ c a nút g c; ố ủ

 Cây con trái và cây con ph i cũng là cây tìm ki m

ế

ả

nh phân.

ị

 Cac giá tr khóa là khác nhau.

ị

3. Cây tìm ki m nh phân ế ị

b) Phép tìm ki m:ế

ị ằ

ứ gôc, đ i sánh giá tr nút v i khóa:

̀ ừ

ớ

ị

ố ế

Có nút nào ch a giá tr b ng khóa?  Băt đâu t  B ng nhau thì K t thúc ằ  Nh h n th c hi n trên cây con trái ệ ự  L n h n th c hi n trên cây con ph i ả ệ ự

ỏ ơ ơ

ớ

́ ́

ộ ng Data c a nút m i. ớ ủ ườ ng Right c a nút m i đ u ớ ề

ủ

t Null.

3. Cây tìm ki m nh phân ế ị

c) Phép chèn  Xin c p b nh cho m t nút m i, ộ ớ ớ ấ  Gán giá tr m i vào tr ị ớ ng Left và tr  Tr ườ c gán giá tr đ c bi đ ị ặ

ườ ượ

ệ

3. Cây tìm ki m nh phân ế

ị

ị ớ ầ ế

T g c, đ i sánh v i giá tr m i c n thêm vào: ớ ừ ố  N u b ng nhau k t thúc ế  Ng

i duy t theo cây con trái ( n u

ế

<) ho c cây con ph i (n u >)

ố ằ c l ượ ạ ặ

ả

ệ ế

3. Cây tìm ki m nh phân ế

ị

 Khi g p nút x không có nút con trái/ph i xác

ả

ị

ườ

ể

trái/ph i c a nút x tr t

i nút m i.

ặ c ví trí c n chèn. đ nh đ ầ ượ  Ch nh s a các tr ữ ỉ ả ủ

ng liên k t đ con tr ỏ ỏ ớ

ế ớ

3. Cây tìm ki m nh phân ế ị

d) Phép xóa  N u nút x là nút lá ta ch c n “c t b ” x



ắ ỏ ỉ ầ ế

ỗ

ộ ạ

ủ

ằ ỏ ế

3. Cây tìm ki m nh phân ế ị

d) Phép xóa  N u x có m t trong hai cây con là cây r ng thì i con tr c a nút cha c a x b ng ỏ ủ ng ng thay vì tr đ n x ế ươ i nút g c c a cây con duy nh t ố

ứ ủ

ấ

ế đi u ch nh l ỉ ề cách tr ườ thì bây gi c a x và gi ủ

ng liên k t t tr t ờ ỏ ớ ả

i phóng b nh đã c p cho x ớ

ấ

ộ



ế

ứ

3. Cây tìm ki m nh phân ế ị

d) Phép xóa  N u nút x có hai cây con (có g c t ố ươ ẳ

ộ

ạ ủ

ng ng là x1 và x2) và m t trong hai cây con (ch ng h n x1) không có con thì ta thay nút x1 làm nút cha c a cây con có g c là x2. Ta thay đ i tr

ng liên k t nh sau: ế

ổ ườ

ố

 Tr

ng liên k t nút cha c a x thay vì tr t

i x

ỏ ớ

ườ

thì nay tr t

ỏ ớ

 Tr

ườ

ủ ế i nút con x1. ế ủ nay tr vào nút x2

ng liên k t c a nút con x1 thay vì là null ỏ



3. Cây tìm ki m nh phân ế

ị

 Tr

ng h p t ng quát:

ườ

ợ ổ

ị ủ

ằ

ủ

ặ

ị

1. Thay giá tr c a x b ng giá tr nút lá bên ph i ị ả cùng c a cây con trái ( ho c b ng giá tr nút lá ằ bên trái cùng c a cây con ph i) ủ

ả

ắ ỏ

ị ừ ể

ượ ự

ế

ọ

ả ắ ỏ

ệ

2. C t b nút có giá tr v a gán cho nút x. c l a ch n đ thay th là bên ph i/ trái Vì nút đ cùng nên không th có hai con, vi c c t b nó ể s th c hi n theo các cách đã nêu trên ẽ ự

ệ

ƯƠ

CH 3. Cây tìm ki m nh phân ế

NG V: CÂY (TREE) ị

d) Phép xóa



3. Cây tìm ki m nh phân ế ị

e) Đánh giá th i gian th c hi n các phép toán ờ ệ ự  V i phép tìm ki m. ế

ớ

ộ

ủ

ế

ế ng đi t

Phép toán tích c c: phép so sánh . ự gian th c m t phép toán so sánh = la th i gian đi ự t m t đ nh đ n đ nh con c a nó ừ ộ ỉ ỉ th c hi n tìm ki m có th coi là th i gian đi trên ể ệ ự qu ng đ ả

Coi th i ờ ̀ ờ  th i gian ờ ờ g c đên m t đ nh nào đó. ộ ỉ

ừ ố

ườ

ng h p v i cây nh phân đ y đ thì đ cao c a

ủ

ầ

ộ

ị ườ cây là x p x logn. Gi ả ử ứ

ủ s m c th p nh t là k: ấ

ợ ấ

ớ ỉ

ấ

1+ 2+ 22 +…..+2k-1 < n 1+ 2+ 22 +…..2k >=n

ậ

ế ộ

ứ

ỉ

ế

ấ

ứ ạ

ả

ậ

ộ

Hay 2k -1 =n, do v y log(n+1) -1 <=k < log(n+1) , nghĩa là k x p x logn. Vì th đ ph c ấ t p thu t toán là O( logn) ậ ạ ng h p x u nh t, nghĩa là cây suy bi n Trong tr ấ ợ ườ l ch trái ho c l ch ph i thì đ ph c t p thu t toán ặ ệ ệ là O(n)

 V i các phép toán chèn và xóa cũng có cách đánh

ớ

giá t

ng t

ươ

ự

ậ

b ph n còn g i là c u trúc Heap: ấ m c cu i cùng, t ố ̣ ở ứ

ứ ự ộ ị

4. Cây có th t b ph n ứ ự ộ ậ

Cây có th t ọ  Cây nh phân hoan thiên, ề

các nút lá đ u xu t hi n liên ti p t ấ

ế ừ

ệ

 Giá tr khóa c a m i nút không nh h n giá tr nút

t c ấ ả trái sang ph i. ả ỏ ơ

ị

ỗ

ị

ủ hai con c a nó.

ủ

 Môi cây con trai va phai cua no cung la cây co th ́ ứ

̃ ́ ̀ ̉ ̉ ́ ̃ ̀

Ta g i các đi u ki n trên là các tính ch t Heap.

t bô phân. ự ề ọ

ệ

ấ

̣ ̣

(a)

(b)

(c)

 Môt sô heap khac nhau tao t

cung môt ̣ ừ ̣ ́ ́ ̀ ̣

d liêu ữ ̣

 Phép chèn (Insert)

s ta c n chèn thêm m t nút m i có giá tr ị

ớ

ầ

ộ

ả ử ẳ

Gi ch ng h n là X. ạ  T o nút m i, ghi giá tr X vào tr

ng Data c a nút

ớ

ị

ườ

ủ

m i đó.

ạ ớ

ng liên k t c a nút có ế ủ

 Thay giá tr Null trong tr ườ ị m t nút lá tr vào nút m i. ớ ỏ

ộ

4. Cây có th t b ph n ứ ự ộ ậ

4. Cây có th t

b ph n

ứ ự ộ

ậ

ỡ

ế

ử

ị nút lá đó “ đi ng

t t

ượ

ấ ầ ượ ừ ộ

ủ

ị

ủ

ổ

ị

 N u tính ch t Heap b phá v thì s dung thu tuc c lên”. Upheap: L n l N u t i m t nút mà giá tr khóa c a nút đó l n ớ ạ ế h n giá tr khóa c a nút cha nó thì tráo đ i hai giá ơ tr đó cho nhau. ị

̣ ̉ ̣

 Vi du thêm nut 15

́ ̣ ́

 Phép xóa

 Thay giá tr c a nút g c b ng giá tr nút lá sau ố

ị

ằ

cùng

ở ứ

ị ủ m c cu i cùng ố  Xóa nút lá đó đi  S dung thu tuc Downheap: L n l

t t

ử

ố

4. Cây có th t b ph n ứ ự ộ ậ

ố

ầ ượ ừ ị

ổ

̣ ̉ ̣

ủ

ị

nút g c “ đi xu ng “, Khi cân, tráo đ i giá tr khóa c a nó ủ v i giá tr khóa c a nút con có giá tr không nh ỏ ớ h n. ơ

 Quá trình trên cùng l m là d ng l

ừ

ắ

ạ

i khi đ n nút lá. ế

 Xoa nut gôc

́ ́ ́

 Phép xóa

4. Cây có th t b ph n ứ ự ộ ậ

CH

NG VII: S P X P

ƯƠ

Ắ

Ế

ự

ố

ộ

i thi u 1. Gi ệ ớ 2. S p x p b ng l a ch n ế ọ ằ ắ 3. S p x p b ng tráo đ i ắ ổ ằ ế 4. S p x p chèn ế ắ 5. S p x p vun đ ng ế ắ 6. S p x p tr n ế ắ 7. S p x p nhanh ế ắ 8. S p x p theo c s ơ ố ế ắ 9. Tính n đ nh c a thu t toán s p x p ủ ổ

ế

ắ

ậ

ị

 S p x p là b trí l

i v trí các ph n t

c a m t t p

ố

ầ ử ủ

ộ ậ

ng theo m t tr t t

nào đó.

ạ ị ộ ậ ự

trong t

đi n

ừ ể

ể

ABC,…

 S p x p các t ừ ế  S p x p d li u trong máy tính, ữ ệ ế  S p x p k t qu đi m thi tuy n sinh ả ể ế ế  S p x p danh sách sinh viên theo th t ế

ứ ự

ế ắ đ i t ố ượ  Ví d : ụ ắ ắ ắ ắ

1. Gi i thi u ớ ệ

Sorting

• Card players all know how to sort …

• First card is already sorted • With all the rest,

¶Scan back from the end until you find the first card larger

than the new one,

¸Move all the lower ones up one slot

‚

insert it

• “ “

Q

A

K

10

2 J

2

9

‚

9

ng có th thuôc nhi u ki u

ố ượ

ề

ể

1. Gi i thi u ớ ệ

ữ ệ  Thông th

 Cac thuôc tinh đ i t d li u khác nhau. ườ

ứ

ầ

ỉ

́ ̣ ́ ̣

ng yêu c u s p x p ch căn c vào ế ng khóa săp xêp

ườ

́ ́

ắ tr ọ ng khoa).

các thành ph n g i là ầ ( goi tăt la tr ̀ ườ

̣ ́ ́

 Th c hi n qua hai pha

ự

ệ

ự

ị ườ

ng khóa và yêu c u ầ ng

ố ượ

ủ

ỗ

ế ậ

ị ắ  Pha 2: Chuy n toàn b thông tin c a đ i t

 Pha 1: D a vào giá tr tr ị ế ộ

ủ

ng ố ượ ng ng đã xác đ nh ị

́ ươ

ứ

ị

s p x p ta xác đ nh v trí c a m i đ i t ắ trong t p sau khi s p x p. ể ( STRUCT) v đúng v tri t ề trong Pha 1.

ị

ế

ầ

1, k2,…, kn. C n x p

1. Gi ớ

ệ Cho dãy K g m n giá tr khóa k l ạ ̣ ́ ́

1, k2,…, kn.}

b) Sau khi s p x p

a) D li u g c ố ữ ệ

ế

ắ

i thi u ồ i vi tri cac khóa sao cho: k’1 <= k’2<=.. k’n, ki thu c t p { k ộ ậ

 Ý t

2. S p x p b ng l a ch n ằ ự ế ắ ọ

ngưở ổ ị ấ t th ứ

ọ ỏ ổ

ị ng t ươ ự nh ư

Tráo đ i giá tr nh nh t khóa k l ở ươ ỏ i hai ta ch n trong s ( n-1) khóa còn l ạ ố khóa nh nh t và tráo đ i giá tr đó cho ấ khóa k2,.. Ti p t c quá trình t ế ụ v y. ậ

Cai đăt C++

template void selectionsort(T data[], int n){ for (int i = 0; i < n-1; i++){

int j, least = i; T tmp; for (j = i+1; j < n; j++) if (data[j] < data[least]) least = j;

tmp = data[i]; 

data[i] = data[least];



data[least] = tmp;



}



}

̀ ̣

t 1ượ

t 2ượ

t 3ượ

t 4ượ

t 5ượ

2. S p x p b ng l a ch n ằ

ự

ế

ắ

ọ

 Phép toán so sánh là phép toán tích c c. ự

ố ượ

ự

ng các phép toán tích c c là: S l (k-1) +(k-2) +………+2+1= k* (k-1)/2

 Do đó O(k2)

Đánh giá

3. S p x p b ng tráo đ i ổ ằ ế ắ

Ý t 

ngưở ớ

ố ạ

ỗ ặ

ứ

ề ề

ề ệ

ắ

ầ

ế

i, cho đ n khi không co

 Vi c làm đó đ

V i m i c p s h ng đ ng li n k trong dãy K, n u chúng không tho mãn đi u ki n c n s p ả ế x p ta ti n hành đ i ch chúng cho nhau. ỗ ổ ế c l p l ượ ặ ạ ệ

ế

bât ki môt căp sô hang liên kê nao cân đôi chô.

́ ̀ ̣ ̣ ́ ̣ ̀ ̀ ̀ ̀ ̉ ̃

3. S p x p b ng tráo đ i ổ ằ

ế

ắ

template void bubblesort(T data[], int n){ for (int i = 0; i < n-1; i++)

for (int j = n-1; j > i; --j)

if (data[j] < data[j-1]) { T tmp = data[j]; data[j] = data[j-1]; data[j-1] = tmp;

}

Mô ph ng các b

ỏ

ướ

c th c hi n c a thu t toán ủ

ự

ệ

ậ

Dãy A

t 1ượ

t 2ượ

t 3ượ

t 4ượ

t 5ượ

t 6ượ

t 7ượ

t 8ượ

t 9ượ

t 10

ượ

Ắ

CH Ế 3. S p x p b ng tráo đ i ổ ằ

NG VII: S P X P ế

ƯƠ ắ

ự

ng các phép toán tích c c là: (N-1) +(N-2) +………+2+1= N* (N-1)/2

 Do đó O(N2)

Đánh giá T ng s l ố ượ ổ

4. S p x p chèn ế ắ

Y t ng ́ ưở

ắ ế k1 có th coi là đã s p x p.

c k ướ

1. ầ ử 1 và k2 là đã

̀ ể  Thêm k2, n u kế  Thêm k3, vi dãy 02 ph n t

k s p x p, c n tìm cách chèn k3? ế ắ ầ

4. S p x p chèn ế

ắ

 T ng quát, day k

ổ ̃ ̀ ̃ ̃ ́

1, k2,…, ki-1 la day đa săp, i vao day đo sao cho

̀ ̀ ̃ ́

ta cân chèn thêm k day sau khi chen cung la day đa săp. ̃ ̀ ̃ ̀ ̃ ̃ ́

4. S p x p chèn ế

ắ

ủ ớ

 So sánh ki l n l ầ ượ dãy đã s p t k c j mà k đ

ắ

ượ i. ạ ừ t v i các khóa c a ừ i-1 cho đ n khi tìm ế j-1 <= ki < kj thì d ng l

v trí th j đ n (i-1)

ể

ừ ị

ứ

ế

ả

c sau khi chuy n

ạ ị sang ph i m t ví trí. ỗ

ượ

ể

 Chuy n d ch đo n con t ộ  Chèn ki vào ví trí r ng có đ

d ch. ị

C++

 template void insertionsort(T data[], int n){ for (int i=1,j; i 0 && tmp < data[j-1]; j--)

data[j] = data[j-1];

data[j]=tmp;



}

 }

tượ

4. S p x p chèn ế

ắ

 Đánh giá

ắ

c là dãy đã s p, O(n).  Dãy cho tr ướ c v i th t ng  Dãy có th t ứ ự ầ ớ ứ ự l  Trung bình, có th coi ở ượ

ượ ể

ứ

2).

c n s p O(n ắ t th i thu t toán ậ c n trung bình i/2 phép so sánh nên t ng là: ổ ầ (1/2) +(2/2)+(3/2) +……+(n/2) = (n+1) * n/4 V y thu t toán có đ ph c t p là O(n ộ

ứ ạ

ậ

 Ý t

5. S p x p vun đ ng ế ắ ố

ngưở

ấ

Heapsort do W.j.William đ xu t d a trên ấ ự ề c u trúc heap ( xem ch ng VI) g m các ồ ươ thao tác sau:  (i) T dãy a ừ ướ

ự ấ

ầ ử ủ ữ

ộ ể ấ ấ

c ta xây 1 …. an cho tr d ng c u trúc heap b ng cách s d ng ằ ử ụ (N-1) phép chèn, m i l n chèn m t ỗ ầ c a dãy K và ch nh s a đ c u ph n t ỉ trúc sau m i l n chèn luôn có tính ch t ỗ ầ ng VI). heap ( Xem ch ươ

ừ ấ ượ

ầ

 (ii) T c u trúc heap đã xây d ng đ c th c ự ự g c v i giá ớ ị ở ố ắ ầ ừ n ( t th i, b t đ u t

a ổ ứ ở ượ ệ ị ứ ́ ̣

hi n (N-1) l n tráo đ i giá tr l tr sô hang th i i= N, (N-1),… 3,2).

5. S p x p vun đ ng

ế

ắ

ố

 Sau m i l n tráo đ i nh v y:



ỗ ầ ổ

Sô hang K ́ ̣ ̀ ̀

ư ậ I không con tham gia vao gôc l n nhât (năm ̀ ử ớ ̀ ở ́ ̀ ́ ̀ ́ ́



đông va đo la phân t c th i-1); tai b ứ

ạ ể ấ ươ i đ c u trúc b o toàn tính ả ng VI) đôi v i cây co ́ ớ ́

̣ ướ “ vun đ ng” l ố ch t heap ( Xem ch ấ (i-1) nut.́

C++ Heapsort

 template  void heapsort(T data[], int size) { for (int i = size/2 – 1; i >= 0; --i) 

// t o cây heap;



ạ moveDown (data, i, size - 1);



for (int i = size – 1; i >= 1; --1) swap(data[0], data[i]); // đ i nút l n nh t ra v trí i;

{ ớ

ấ i cây heap t

ph n còn l

ị ầ

ừ

i; ạ

ổ  moveDown (data, 0, i-1);// t o l ạ ạ 

}

 }

 Đánh giá

 Nêu cân săp theo tiêu chi tăng dân thi phai

5. S p x p vun đ ng ế ắ ố

dung môt phep đao day kêt qua.

́ ̀ ́ ́ ̀ ̀ ̉

ự

̀ ̣ ́ ̉ ̃ ́ ̉

ộ

ỉ

ế ộ

ứ

 Phép toán tích c c la phép so sánh. Nh đã t, heap là m t cây hoàn ch nh, có N nút thì bi ế chi u cao c a nó là [lg(N)] +1, vì th đ ph c ề tap c a thu t toán này s là

ẽ O( NlgN).

ủ ậ

ủ

 Ý t

6. S p x p tr n ế ắ ộ

ưở ̉ ầ ế ớ ̣ ̀

ộ

ượ ̣ ̣ ̀

ậ ́ ́ ̉ ̣

Chi c n s p x p dãy con nhâp m i rôi ắ c s p thành m t “tr n” hai dãy đã đ ắ ượ ộ ắ Nh vây thao tác “trôn” la c s p. dãy đ ư phep toan chu đao c a thu t toán ủ Mergesort.

ắ ế

ộ

 Tr nộ Cho hai dãy đã s p x p: B={b1,b2 bm} C={c1.. Cn }c n tr n thành ầ c dãy D={d1, dn+m } phai la dãy đ s p.ắ

ượ ̉ ̀

(i) L n l

i ( 1<=i<=n+m) b ng ằ nh h n trong hai i ạ

ỏ ơ

t xác đ nh d ị ầ ượ cách ch n ph n t ử ầ ọ ầ ử j và ck ( 1<=j<=m; 1<=k<=n) t b ph n t c. m i b ỗ ướ

Chu ý

ườ

ng thêm m t ph n t ị

(ii) Trong cài đ t th ặ ơ ị ớ ỗ ố ử ủ ượ ự ọ

ầ ử

còn l ầ có ầ ử trong dãy t c các ấ ả c l a ch n i c a dãy ạ ủ i còn l ạ ử

ộ giá tr l n h n giá tr các ph n t ầ ử vào cu i m i dãy B và C đ khi t ể ph n t c a m t dãy đã đ ộ ầ cho dãy D thì các ph n t kia s chuy n thành các ph n t ể ẽ c a dãy D. ủ

Ví d , cân trôn hai day đ

c săp (B)= (1, 5, 7, 8, 9) va (C)=(2, 6, 10, 11, 12, 35).

ụ

ượ

Day C

Khoa nho nhât

Day B̃

́ Day D̃

̀ ̣ ̃ ́ ̀

1,5,7,8,9

2,6,10,11,12,35

5,7,8,9

1, 2

6,10,11,12,35

5,7,8,9

1,2,5

6,10,11,12,35

7,8,9

1,2,5,6

10,11,12,35

7,8,9

1,2,5,6,7

10,11,12,35

8,9

1,2,5,6,7,8

10,11,12,35

1,2,5,6,7,8,9

10,11,12,35

[]

8,9,10,11

̃ ́ ̉

3 Đ a phân con lai vao D

1,2,5,6,7,8,9,10,11, 12,35

̀ ̀

̣ ̀

 Đánh giá

6. S p x p tr n ế ắ ộ

ậ ế ắ

ộ ấ

 S p x p tr n là m t thu t toán s p x p ộ ế ắ c đi n nh t ( do J. Von Neumann đ ề ổ ể i nay đó là xuât năm 1945), nh ng cho t ớ ư c coi là thu t toán s p thu t toán đ ậ ượ x p ngoài m u m c nh t. ẫ

ậ ắ

ự ế ấ

ộ

ộ ế ư

O(N). ộ ả

 Phép toán tích c c trong phép tr n là ự khóa vào dãy k t ầ ử ủ ử ụ

ắ phép đ a m t ph n t qu nên đ ph c t p c a tr n là ứ ạ ộ ộ ế

ủ ậ

 Nh

ứ ạ O(NlgN). ộ

ượ

 Trong s p x p tr n s d ng không quá [lgn] l n tr n nên đ ph c t p c a thu t ộ ộ ầ toán s p x p tr n là ế ắ c đi m là ph i dùng thêm không ả ể gian đ l u tr dãy khóa d ( trong vi c ể ư tr n).ộ

ữ ệ

 S p x p tr n ế

ộ ắ

 V i m i dãy con đ u và cu i đ

ầ ữ

 Chia đôi dãy đã cho thành 02 n a đ u và cu i ( h n kém nhau không quá ơ ố m t ph n t ). ầ ử ỗ ế

c ượ ố

ầ ệ

i . s p x p m t cách đ quy. ộ  Tr n hai dãy con đã s p l ắ ạ ộ ớ ắ ộ

ế

ắ

ườ

ự ế

S p x p tr n ( tr n 02 đ ộ ộ  M i ph n t ỗ

ớ ộ dãy đã đ

ng tr c ti p) ầ ử i là m t dãy con v i đ dài ộ c ử ầ

a ộ ượ

b ng 1( dãy m t ph n t ằ s p).ắ ộ ề ắ ộ

 Tr n hai dãy con li n k đã s p thành m t ề c s p. ắ ượ ng các dãy con

ớ

ố ượ ụ ế

dãy con l n h n cũng là dãy đ ơ Ti p t c nh v y, s l ư ậ trong dãy gi m d n sau m i l n tr n. ầ ả ỗ ầ ộ

Săp xêp trôn hai đ

ng

ườ

́ ́ ̣

Cho day: ( 3,5,4,6,9,7,12,13,11, 8)  Trôn t ng căp hai sô hang liên kê, thu đ c: ̣ ừ ượ ̣ ́ ̣ ̀ ̀

c: ̣ ừ ượ ̣ ̃ ̀ ̀

c: ượ ̣ ̣

c kêt qua: ̣ ̃ ̃ ́ ̣ ́ ̉

(3,5), (4,6), (7,9), (12, 13),(8,11)  Trôn t ng căp hai day liên kê, thu đ (3,4,5,6) , (7,9,12,13), (8,11)  Lăp lai nh trên, thu đ ư (3,4,5,6,7,9,12,13) va (8,11) Trôn hai day con đa săp, nhân đ ượ  ( 3,4,5,6,7,8 ,9,11,12,13).

 Ý t

7. S p x p nhanh ế ắ

ngưở

ộ ệ ấ

ự ̀

ồ

Quicksort là m t thu t toán r t hi u qu ả ậ do C.A.R. Hoare xây d ng vao năm 1960, g m hai pha:  Phân đo n ( partition) ạ  S p x p (sort). ế ắ

ọ ẫ

m t ch s j làm ỉ ố

 V i dãy đã cho ta ch n ng u nhiên ố

 Phân đo nạ ớ ộ  Chuy n t

ướ

ch t (Pivot) t c các s h ng c a dãy có ủ ể ấ ả ố ạ giá tr nh h n k c ch t và j đ ng tr ố ứ ỏ ơ ị t c các s h ng có giá tr l n h n t ị ớ ố ạ ấ ả j. j. đ u đ ng sau k ho c b ng k ứ ề ằ ặ

Quicksort

• Partition

• Choose a pivot • Find the position for the pivot so that • all elements to the left are less • all elements to the right are greater

< pivot

pivot

> pivot

Ắ

Ế

CH NG VII: S P X P 7. S p x p nhanh ế

ƯƠ ắ

 Phân đo nạ

Đê phân đoan ta th hiên cac b c sau: ự ướ ̉ ̣ ̣ ́

̣ ̣ ́ ̣ ̀ ́ ̉ ̣ ̀ ́

́ ̣ ́ ̣ ̀ ́ ́

̣ ̉ ́ ̀ ́ ́ ̣

̣ ̀

̀ ượ ơ ̉ ̃ ̀ ́ ̣

̉ ơ ́ ̣ ́ ̣ ́ ̀

(i) Chon môt sô hang nao đo gia đinh la chôt, vi du sô hang đâu tiên ( bên trai nhât); (ii) Tao hai chi sô left va right co gia tri kh i ở tao left=1 va right= N; (iii) Giam lân l t right môi lân xuông 1 đ n vi cho đên khi găp sô hang nho h n chôt thi d ng lai. ừ ̣

(iV) Tăng lân l ̀ ượ ̃ ̀

t left môi lân lên 1 đ n vi cho đên khi găp sô hang l n h n chôt thi d ng lai. ớ ơ ́ ̣ ́ ̣ ́ ̣

ừ ở ́ ̣ ́ ̣ ̉

(V) Hoan vi hai sô hang xây ra d ng (Vi) Tiêp tuc th c hiên cac b ướ ự ́ ̣ ̣ ́ ̀ ́

̀ ừ ́ ̉ ́

ơ ̀ ừ trên c iii va iV cho đên khi cac chi sô giao nhau ( left>=right) thi d ng lai.̣

(Vii) Hoan vi chôt v i k[right] va kêt thuc phân ́ ớ ́ ̣ ̀ ́ ́

đoan.̣

 Chia đê tri va đê quy

7. S p x p nhanh ế ắ

̉ ̣ ̀ ̣

ượ ̃ ́ ̣ ̣ ́ ̉ ́

̃ ̀ ̣ ̉

̃ ́ ́ ̣ ̃ ̣ ̣

́ ̀ ̣ ̣ ́

ờ ̃ ̣ ̉ ̀ ̣

ượ ́ ́ ̣ ̃ ̃ ̀ ̃

c vi tri cua chôt, Sau khi đa xac đinh đ c chia thanh 02 đoan, thoa day cho tr ướ man tinh chât phân đoan. V i môi đoan lai ớ tiên hanh phân đoan đê quy cho đên khi trong day con hiên th i chi con lai không c se la day qua hai sô hang. Day thu đ đ c săp. ượ ́

Quicksort

•

Implementation

quicksort( void *a, int low, int high )

{ int pivot; /* Termination condition! */ if ( high > low )

Divide

Conquer

{ pivot = partition( a, low, high ); quicksort( a, low, pivot-1 ); quicksort( a, pivot+1, high ); }

}

7. S p x p nhanh ế

ắ

Quicksort - Partition

int partition( int *a, int low, int high ) {

This example uses int’s to keep things simple!

int left, right; int pivot_item; pivot_item = a[low]; pivot = left = low; right = high; while ( left < right ) {

Any item will do as the pivot, choose the leftmost one!

/* Move left while item < pivot / while( a[left] <= pivot_item ) left++; / Move right while item > pivot */ while( a[right] >= pivot_item ) right--; if ( left < right ) SWAP(a,left,right); }

low

high

23 12 15 38 42 18 36 29 27 /* right is final position for the pivot */ a[low] = a[right]; a[right] = pivot_item; return right; }

ắ

7. S p x p nhanh ế Quicksort - Partition

int partition( int *a, int low, int high ) {

Move the markers until they cross over

int left, right; int pivot_item; pivot_item = a[low]; pivot = left = low; right = high; while ( left < right ) {

/* Move left while item < pivot / while( a[left] <= pivot_item ) left++; / Move right while item > pivot */ while( a[right] >= pivot_item ) right--; if ( left < right ) SWAP(a,left,right); }

left

right

23 12 15 38 42 18 36 29 27

low

high

pivot: 23

/* right is final position for the pivot */ a[low] = a[right]; a[right] = pivot_item; return right; }

Quicksort - Partition

int partition( int *a, int low, int high ) {

Swap the two items on the wrong side of the pivot

int left, right; int pivot_item; pivot_item = a[low]; pivot = left = low; right = high; while ( left < right ) {

/* Move left while item < pivot / while( a[left] <= pivot_item ) left++; / Move right while item > pivot */ while( a[right] >= pivot_item ) right--; if ( left < right ) SWAP(a,left,right); }

left

right

pivot: 23

/* right is final position for the pivot */ a[low] = a[right]; a[right] = pivot_item; 23 12 15 38 42 18 36 29 27 return right; } low

high

7. S p x p nhanh ế

ắ

Quicksort - Partition

int partition( int *a, int low, int high ) {

right

left

int left, right; int pivot_item; pivot_item = a[low]; pivot = left = low; right = high; while ( left < right ) {

23 12 15 18 42 38 36 29 27

high

low

pivot: 23

/* Move left while item < pivot / while( a[left] <= pivot_item ) left++; / Move right while item > pivot */ while( a[right] >= pivot_item ) right--; if ( left < right ) SWAP(a,left,right); }

Finally, swap the pivot and right

/* right is final position for the pivot */ a[low] = a[right]; a[right] = pivot_item; return right; }

7. S p x p nhanh ế

ắ

Quicksort - Partition

int partition( int *a, int low, int high ) {

int left, right; int pivot_item; pivot_item = a[low]; pivot = left = low; right right = high; while ( left < right ) {

pivot: 23

18 12 15 23 42 38 36 29 27

high

low

/* Move left while item < pivot / while( a[left] <= pivot_item ) left++; / Move right while item > pivot */ while( a[right] >= pivot_item ) right--; if ( left < right ) SWAP(a,left,right); }

Return the position of the pivot

/* right is final position for the pivot */ a[low] = a[right]; a[right] = pivot_item; return right; }

Ắ

Ế

CH NG VII: S P X P 7. S p x p nhanh ế

ƯƠ ắ

Quicksort - Conquer

pivot

pivot: 23

18 12 15 23 42 38 36 29 27

Recursively sort left half

Recursively sort right half

Ắ

Ế

CH NG VII: S P X P 7. S p x p nhanh ế

ƯƠ ắ

̉ ́ ́

̣ ́ ̀

ự ́ ́ ́ ̃ ̀ ́ ́

Đánh giá và nh n xét ậ  Co h ng tông quat tôt ́ ướ  S dung it tai nguyên ử  Phep toan tich c c cung la phep toan so sanh, thoa man công th c truy hôi sau:

ứ ́ ̉ ̃ ̀

N = NlgN

 CN = 2CN/2 +N  Dê dang nhân đ  Chi s dung trung binh NlgN thao tac đê

c: C ượ ̃ ̀ ̣

̉ ử ̣ ̀ ́ ̉

săp xêp N phân t ̀ ử ́ ́

 Vân đê chon chôt.

́ ̀ ̣ ́

́ ̣ ́ ̣ ̉

̀ ̉ ́

 Quyêt đinh tinh hiêu qua ̣ điêm chôt tôt h n  Cân chon ́ ơ  Chon ngâu nhiên 03 phân t ̀ ử gi a cua 03 phân t

̣ ̃ ̃

̀ ử ữ ́ ̣ ̉ ̀

̀ ̣ ̉ ̣ ́ ̣ ́

ươ ̉ ́ ̀ ̉ ̉

ng h p xâu nhât không thê xây ra. trong day, sau nay đo chon phân t ̀ ử lam phân hoach. Chăng han sô hang trai , phai, gi a. Ph ng phap nay đam bao, ữ tr ợ ườ ́ ́ ̉ ̉

 Ý t

8. S p x p b ng c s ơ ố ế ằ ắ

ngưở  Áp d ng t ụ ế ạ

ng phân đo n đ s p x p không nhiên theo th t ể ắ ứ ự ố ự

t ư ưở dãy khóa là s t gi m.ả ế ắ ằ ơ ố theo kiêu hoan vi ̉ ́ ̣

 S p x p b ng c s ́ cac khoa  Ta có th coi m i s nguyên là m t dãy z

ể ộ

bit đánh s t ố ừ ỗ ố 0 đ n z-1. ế

ạ ể

ấ ằ ể ư ề ầ ữ

ố

ằ ở

 Đ phân đo n ta có th đ a các khóa có bít cao nh t b ng 0 v đ u dãy, nh ng khóa có bit cao nh t bàng 1 v cu i dãy ề ấ bít cao (vì nh ng khóa b t đ u b ng 0 ữ ắ ầ nh t s nh h n nh ng khóa có bít cao ấ ẽ ữ nh t b ng 1). ấ ằ ụ ế

ỏ ơ

ạ ớ

 Ti p t c phân đo n v i hai đo n dãy ạ khóa, m t đo n có bít cao nh t bàng 1 và m t đo n có bít cao nh t b ng 0.

ạ ấ

ấ ằ ộ ạ ộ

 Ví d , dãy xu t phát là 1,3,7,6,,5,2,3,4,4,5,6,7 t

ụ

ấ

ươ

ng v i dãy 03 bit:

ứ

ớ

ạ

ự

ấ

trái sang

ừ

ạ

 001 011 111 110 101 010 011 100 100 101 110 111  Phân đo n d a vào bit cao nh t ( bên trái cùng) 001 011 011 010 101 110 111 100 100 101 110 111  Pân đo n d a vào bít th 2 t ứ ự  001 011 011 010 101 101 100 100 111 110 110 111 ……………….

ế ụ

hàng đ n v ị

ự

ạ

ở

Ti p t c phân đo n d a vào bit 001 010 011 011 100 100 101 101 110 110 111 111

̣ ơ ́ ̣ ́ ́ ́ ̀

̉ ự ứ ̣ ̣ ̣ ́ ̉ ̣

ờ ̀ ́ ̀ ̀

̣ ̀ ̀ ̀

ườ ợ ̀ ́ ̣ ́ ̀ ̣

 Co thê th c hiên v i hê c sô khac bât ki ớ  Đô ph c tap thuât toan: Đê phân đoan băng 1 bit thi cân Cn th i gian, nên th i ờ gian phân đoan băng z bit se la C.N.z ( C la ng h p xâu thi đô ph c hăng sô), vây tr ng h p tap thuât toan la O(N.z) con tr trung binh la O(N. min (z,lgN)

ứ ợ ườ ̣ ̣ ́ ̀ ̀

̀ ̀

 S p x p b ng c s

8. S p x p b ng c s ơ ố ế ằ ắ

ơ ố

ế

ằ

ắ

ử ̣ ̣ ̣ ́ ̀ ́ ̉ ́

 S dung môt thuât toan nao đo đê săp xêp day khoa tăng dân theo gia tri ch ữ sô hang đ n vi.

́ ̃ ́ ̀ ́ ̣

ơ ́ ̀ ̣

ử ̣ ̣ ̣ ́ ́ ́ ̉ ̣

 S dung môt thuât toan săp xêp ôn đinh nao đo đê săp xêp day khoa tăng dân theo gia tri ch sô hang chuc. ữ

̀ ́ ̉ ́ ́ ̃ ́ ̀

́ ̣ ́ ̀ ̣

 Tiêp tuc th c hiên t hang trăm, ngan,…

ng t v i ch sô ự ươ ự ớ ữ ́ ̣ ̣ ́

̀ ̀

 Nh n xét và đánh giá

ậ

́ ̉ ́ ́ ̉ ̃ ́ ̀

 Co thê coi sô ch sô cua môi khoa la ữ băng nhau ( bô sung cac ch sô 0 vao ữ bên trai môi sô hang con thiêu).

̀ ̉ ́ ́ ̀

́ ̃ ́ ̣ ̀ ́

ứ ̣ ̣ ̣ ̣ ̉ ́ ̀ ̣

̣ ́ ̣ ́ ́ ́ ́

 Đô ph c tap phu thuôc chu yêu vao đô ph c tap cac thuât toan săp xêp khac ứ đa đ ̃ ượ ự

c l a chon. ̣

ổ ậ ắ ị

9. Tính n đ nh c a thu t toán s p ủ x pế

ọ ổ ắ ế

 M t ph ươ ộ ế ị ằ ố

c g i là n b n ghi có

 Trong s các thu t toán đã xét: ổ

ng pháp s p x p đ ượ đ nh n u nó b o toàn th t ứ ự ả ả khóa b ng nhau trong danh sách. ậ

ế ậ ậ ọ

ữ ế ắ

 Các thu t toán s p x p n i b t, thu t ắ toán s p x p chèn là nh ng thuâth toán i là không ổ ổ

ậ ạ

n đ nh, các thu t toán còn l ị n đ nh. ị

 Nói chung m i ph

ọ ế

ổ ề ắ ổ ể

ở ươ

ố ượ ầ

ng pháp s p x p ươ không n đ nh đ u có th bi n đ i đ nó ể ế ị ng pháp chung là tr thành n đ nh. Ph ổ ị ban thêm m t tr ng khóa ch s là th t ứ ự ỉ ố ộ ườ đ u c a đ i t ng. Khi đ i sánh, n u g p ặ ế ố ủ ng có cùng khóa s p x p nh các đ i t ắ ư ế ố ượ nhau thì ta d a vào th t ch s đ x p ỉ ố ể ế ự ban đ u. ng đó theo th t 02 đ i t ứ ự ứ ự ố ượ ầ

CH

NG VIII: TÌM Ki M

ƯƠ

Ế

ớ ệ

1. Gi 2. Thu t toán tìm ki m tu n t ế 3. Thu t toán tìm ki m nh phân ế 4. Cây tìm ki m s h c ố ọ 5. Cây tìm ki m c s ơ ố

i thi u ậ ậ ầ ự ị

ế ế

NG VIII: TÌM Ki M

Ế

CH 1. Gi

i thi u

ƯƠ ớ

 Bai toan.

ệ

Cho tâp N đôi t ́ ượ ̀ ́ ̣ ̃ ́ ̣

ng, hay xac đinh ng ́ ượ ́ ̣ ́ ̣

̣ ̉

xem co hay không trong tâp đo môt đôi t cu thê.  Tâp đ i t ướ ể ề ̣ ̣

ng cho tr ữ ệ ố ượ ́ ể ườ ́

ứ ộ ộ ̀ ́

ườ ầ ọ

c có th có nhi u thuôc tinh co ki u d li u khác nhau. Thông th ng tim kiêm ch căn c m t ho c m t vài thành ặ ỉ ng). Các thành ph n đó g i là ph n ( tr tr ng khóa tim kiêm. ầ ườ ̀ ́

 Qua trinh tim kiêm th

 Pha 1: D a vao gia tri tr

ườ ́ ̀ ̀ ́ ̀

ng gôm 02 pha: ̣ ườ ự ̀ ́ ́ ̀ ́ ̉

̣ ườ ́ ượ ́ ̣ ́ ́ ́ ̀

ớ ́ ̀ ́ ̣ ̉ ̣ ̀

 Pha 2: Kêt xuât toan bô thông tin vê đôi t

ng khoa va khoa đê xac đinh đôi t ng khoa băng ng co gia tri tr v i khoa tim kiêm hăc khăng đinh không tim thây đôi t ng cân tim; ́ ượ ́ ̀ ̀

ng ́ ượ ́ ́ ̀ ̣ ̀

tim đ c. ượ ̀

CH

NG VIII: TÌM Ki M

ƯƠ

Ế

ộ ̉ ́ ̀ ́

ứ

ằ

 Ta chi xet pha 1 cho bai toan: Cho m t dãy ng i ( 1<=i<=n) ng, m i đ i t ố ượ ỗ ố ượ i. Hãy tìm đ i ố ng ng v i m t khóa k ộ ớ ng có giá tr khóa b ng x cho tr ướ ị c đ i t ố ựợ

g m n đ i t ồ t ươ t ượ  Tìm đ ng i có k ựợ c. i = x; tìm ki m ế

ng nào có khóa b ng x; ằ

thành công;  Không có đ i t ế ố ượ tìm ki m th t b i. ấ ạ

2. Tìm ki m tu n t ế ầ ự

ồ ́

 Input: Dãy khoa A g m N s nguyên k k2,..., kn đôi m t khác nhau và s nguyên x;

 Output: Ch s i mà k

ố ố ộ

ặ

i = x ho c thông báo ủ

không có s h ng nào c a dãy A ỉ ố ố ạ

2. Tìm ki m tu n t ế

ầ ự

ng: Ý t ưở  L n l M t cách t ự ộ t t ầ ượ ừ ố ạ

nhiên. ứ ế

ự ả ứ ́

s h ng th nh t, so sánh v i ớ ấ khoá tìm ki m x cho đ n khi có s trùng ế ớ n mà không x y ra s nhau. N u đã xét t i k ự ế trùng nhau thì dãy khoa không ch a giá tr ị x tìm ki m.ế

2. Tìm ki m tu n t ế ầ ự

1, k2,..., kn ;

i = x thi ̀ thông báo I; K t thúc.

ế

i + 1;

́ ̀

. Nh p N, X va k ậ . i (cid:220) 1; . N u kế . i (cid:220) . Nêu i>N thi Thông báo không có s ố ớ ồ ế

. Quay l c 3.

 Thu t toán ậ B c 1 ướ B c 2 ướ B c 3 ướ B c 4 ướ B c 5 ướ h ng nào có giá tr trùng v i x, r i k t thúc. ạ B c 6 ướ

ị i b ạ ướ

Mô ph ng các b ỏ

ướ

c th c hi n c a thu t toán ủ

ự

ệ

ậ

k = 2 và N = 10

k = 6 và N = 10

V i i = 5 thì a

V i m i

không

có

ớ

ọ

ớ

ừ

đ n ế

5 = 2.

giá tr b ng 6. ị ằ

 Nhân xet va đanh gia.

̣ ́ ̀ ́ ́

́ ́ ́ ̀ ́ ́

 Phep toan tich c c la phep so sanh: ự  Tr  Tr

ứ ́ ́ ̣ ̣ ̀

ng h p tôt nhât đô ph c tap la O(1) ng h p xâu nhât va trung binh đô ợ ợ ́ ́ ̀ ̀ ̣

ph c tap la O(N) ườ ườ ứ ̣ ̀

ƯƠ

Ế

CH 3. Tìm ki m nh phân

NG VIII: TÌM Ki M ế

 Input: Dãy g m N s nguyên k ồ

1, k2,..., kN đôi

ị

 Output: Ch s i mà k

ố m t khác nhau và là dãy tăng; sô nguyên x. ộ ́

ỉ ố ặ

i = x ho c thông báo ớ

trong dãy không có giá tr trùng v i x. ị

 Ý t

ng: ử ưở ̣ ̃ ̃ ́ ́ ̀

́ ̣ ̣ ̀ ́ ̃ ̀

Giua

S dung day đa săp xêp ta tim cach thu hep pham vi tim kiêm sau môi lân so sanh khoa v i sô hang đ c chon. a ượ ớ ́ ́ ́ ̣ ̣

Giua=[ (N+1)/2].

 N u kế

ỉ ố ầ

Giua = x thì Giua là ch s c n tìm. Giua > k thì vi c tìm ki m ti p theo

ệ ế

 N u kế ỉ

 N u aế

ch xét trên dãy k1, ka2,..., k ế Giua–1

Giua < k thì th c hi n tìm ki m trên ệ dãy kGiua+1, kGiua+2,..., kN.

 Quá trình trên s đ

ự ế

c l p l i ẽ ượ ặ ạ

ị .

N Giua (cid:220)

. Nh pậ N, k1 k2,..., kn và giá tr khóa x. . Dau (cid:220) . N u kế

ỉ ố

1, Cuoi (cid:220) Giua = x thì thông báo ch s Giua, r i ồ

. N u kế

ặ

Giua > x thì đ t Cuoi = Giua – 1 r i ồ

3. Tìm ki m nh phân ế ị

c 7. ướ Giua + 1

̉ ́

ồ ế

ớ

ị

Quay l

c 3.

́ ̀

 Thu t toán ậ B c 1 ướ B c 2 ướ B c 4 ướ k t thúc ế B c 5 ướ chuyên đên b . Dau (cid:220) B c 6 ướ B c 7 . Nêu Dau > Cuoi thi thông báo dãy không ướ có s h ng có giá tr trùng v i x, r i k t thúc. ố ạ B c 8. ướ

i b ạ ướ

k = 21, N =10

k = 25, N =10

Dau 1

Cuoi 10

Giua 5

aGiua

aGiua 9

tượ 0

t th t

Dau > Cuoi nên k t lu n trong dãy A không có toán

ế

ậ

Sau hai l

t thì a

ượ

ỉ ố ầ

ậ

Giua = k. V y ch s c n tìm là i = Giua = 6.

T i l ứ ư ạ ượ h ng nào có giá tr là 25 c . ả ạ

ị

 Nh n xét và đánh giá

ậ  Tr ườ ợ ứ ́ ́ ̣ ̣ ́ ́

ng h p tôt nhât, đô ph c tap tinh toan ng h p xâu va trung binh ợ ườ ̀ ́ ̀ ̀

la O(1), trong tr la O(lgN) , ̀

 Tuy nhiên v i day ch a đ ớ

c săp xêp thi ư ượ ̃ ́ ́ ̀

cân co chi phi cho viêc săp xêp. ̀ ́ ́ ̣ ́ ́

 Đ nh nghĩa

4. Cây tìm ki m s h c ố ọ ế

ị

1, k2,…kn môi gia tri khoa khi 0 đên

́ ̃ ́ ̃ ́ ̣ ́

́ ừ ̉ ́ ̣ ́ ́ ́

Xet day khoa k đôi ra sô nhi phân co z bit, đanh sô t z-1 ( phai-trai) ̉ ́

Cây tim kiêm sô hoc

̀ ́ ́ ̣

Cây sô hoc ch a cac gia tri khoa: ứ ́ ̣ ́ ́ ̣ ́

ứ ̀ ̣ ̃ ́ ̣ ́ ̣ ́

́ ́ ́ ́ ́ ̉ ́ ́ ́

 La cây nhi phân, môi nut ch a môt gia tri khoa;  Nut gôc co tôi đa 02 cây con; tât ca cac khoa co cây con trai, tât ca cac ở cây con phai.

́ ́ ̀ ̀ ́ ́ ̉ ́

 Cây con trai va phai cung co tinh chât nh vây.

bit cao nhât la 0 năm khoa co bit cao nhât la 1 năm ̀ ở ́ ́ ́ ́ ̀ ̉

ư ́ ̀ ̉ ̃ ́ ́ ́ ̣

6 = 0110 5 = 0101 2 = 0010 7 = 0111 8 = 1000 10 = 1010 12 = 1100 11 = 1011 4 = 0100

 Phep toan tim kiêm

4. Cây tìm ki m s h c ố ọ ế

 T gôc, xet lân l

́ ́ ̀ ́

t cac bit cua x t ừ ̀ ượ ừ ́ ́ ́ ̉ ́

̉ ́ ̣ ̀

 Hoăc đi t

trai sang phai, nêu găp bit 0 thi đi sang cây con trai, nêu găp bit 1 thi sang cây con phai; ́ ́ ̣ ̀ ̉

i môt nut rông, tim kiêm thât bai ớ ̣ ̣ ́ ̃ ̀ ́ ́ ̣

 Hăc găp nut co gia tri băng x, tim kiêm

(không co gia tri x trong day khoa); ́ ́ ̣ ̃ ́

̣ ̣ ́ ́ ́ ̣ ̀ ̀ ́

thanh công. ̀

 Phep chen

: ́ ̀

ư ̀ ́ ̃ ́

ứ ư ớ ́ ́ ̀ ́ ́

 Tim xem khoa đa co trong cây hay ch a, nêu ch a co thi thêm nut m i ch a khoa cân chen va nôi nut đo vao cây tai nut rông v a se sang khiên tim kiêm thât bai.

̀ ̀ ̀ ́ ́ ́ ̀ ̣ ́

ừ ̃ ̃ ́ ̀ ́ ́ ̣

 Phep xoa

́ ́

 Tim kiêm đê xac đinh nut cân xoa;  Tim trong cây con ma nut cân xoa la nut gôc

̀ ́ ̉ ́ ̣ ́ ̀ ́

̀ ̀ ́ ̀ ́ ̀ ́ ́

 Chuyên đôi gia tri cua nut la va nut cân xoa

môt nut la bât ki; ̣ ́ ́ ́ ̀

̉ ̉ ́ ̣ ̉ ́ ́ ̀ ́ ̀ ́

cho nhau;  Xoa nut la. ́ ́ ́

 Đô ph c tap trong cac tr

̣ ́ ̀ ́ ́

ườ ̣ ̣ ́ ̀

ườ ợ ́ ́ ̀

 Nhân xet va đanh gia ng h p la ợ ứ ng h p xâu nhât la O(min(z,lgN)), tr O(z) vi chiêu cao cua cây tim kiêm sô hoc không qua z+1.

̀ ̀ ̉ ̀ ́ ́

̣ ́

5. Cây tìm ki m c s ơ ố ế

ơ ố ̀: Cây tim kiêm c s la ̀ ́

 La môt cây nhi phân, chi co nut la ch a ứ cung

̀ ̣ ̣ ̉ ́ ́ ́

̀ ở ́ ̣ ́ ̀ ́ ́ ́ ̀

gia tri khoa va cac nut la đêu m c z-1; ứ

 Nut gôc co tôi đa la 02 nhanh con  Moi nut la cua nhanh con trai đêu co bit

́ ́ ́ ́ ̀ ́

̣ ́ ́ ̉ ́ ́ ̀ ́ ́

z-2 la 0 ( đêu băt đâu băng 00); ̀ ̀ ́ ̀ ̀

 Moi nut la cua nhanh con phai đêu co bit z-2

̣ ́ ́ ̉ ́ ̉ ̀ ́ ́

̀ ̀ ́ ̀ ̀

la 1 ( đêu băt đâu băng 01); ớ ̉ ́ ́ ̀ ́ ́

́ ̣ ́ ́ ̉ ́ ́

 Tông quat, v i nut m c d đêu co tôi đa hai ứ nhanh con, moi nut la cua nhanh con trai đêu co bit z-d la 0 va moi nut la cua nhanh con phai đêu co bit z-d la 1

̀ ́ ́ ̀ ̀ ̣ ́ ́ ̉ ́

 Cây tim kiêm c sô đ

̉ ̀ ́ ̀

ở ơ ̀ ́ ̣ ̀

́ ́ ̀ ́ ́ ̀ ̣ ́ ̉ ́

c kh i tao gôm 01 ́ ượ nut gôc va nut đo tôn tai trong suôt ca qua trinh. ̀

NG VIII: TÌM Ki M

ƯƠ

Ế

CH 5. Cây tìm ki m c s

:  Thao tac tim kiêm khoa X

ơ ố ế

 Xuât phat t

́ ̀ ́ ́

ừ ́ ́ ́ ̣ ̃ ́ ̉ ́

trai bit z-1 đên bit 0), găp nut 0 thi re nut gôc, duyêt day bit cua x t ừ ̉ ́ ́ ̣ ́ ̀ ̃

́ ừ sang phai ( t sang trai, găp nut 1 thi sang phai; ́ ̣ ́ ̀ ̉

̃ ừ ́ ̀ ̣

i môt nut rông, tim kiêm thât bai ớ ̣ ̣ ́ ̃ ̀ ́ ́ ̣

 Qua trinh se d ng lai khi:  Hoăc đi t  Nut ́ ở

la co gia tri trung nut x ́ ́ ́ ̣ ̀ ́

 Thao tac chen:

́ ̀

ự ̣ ́ ́ ́

ư ̀ ớ ̣ ̣ ́ ́ ̃ ̀

 Th c hiên cac thao tac nh tim kiêm, khi găp môt liên kêt null ( đi t i nut rông) thi tao nut m i va nôi vao theo liên kêt đo đê co đ

ớ ̣ ́ ̀ ́ ̀ ́ ́ ̉

ng đi tiêp. ́ ườ ́

ừ ̣ ́ ́ ̉ ̣

 Sau khi duyêt hêt cac bit cua x, d ng lai nut la cua cây va đ a gia tri cua x vao nut la đo.

̀ ư ́ ́ ̉ ́ ̣ ̉ ̀ ́

́ ́

 Thao tac xoa

5. Cây tìm ki m c s ơ ố ế

́ ́

̣ ̣ ́ ̀ ̀ ́

 Lăp lai qua trinh tim kiêm;  Đanh dâu đê biêt nut co 02 con cuôi ng

́ ́ ̉ ́ ́ ́ ́

nut đo chi co môt con đ ườ ừ ̀ ́ ́ ̉ ́ ̣

 Xoa toan bô cac nut cua đ

cung (t đôc đao đên nut la); ̣ ̣ ́ ́ ́

ng đôc đao. ườ ́ ̀ ̣ ́ ́ ̉ ̣ ̣

 Gia tri ch a trong cac nut canh la vô nghia nên

ứ

se co lang phi bô nh , ớ

́ ̣ ́ ́ ̀ ̀ ̃

̣ ơ

̃ ́ ̃ ́ ̣

́ ớ

́ ́ ̉ ̣ ́ ́ ̉

 Không nhât thiêt phai chon hê c sô 2, co thê chon c sô l n h n đê đây nhanh tôc đô tim ơ kiêm nh ng se tôn kem bô nh h n

ơ ư

ớ ơ

̣ ̉ ̉ ́ ̣ ̀

́ ̃ ́ ́ ̣

 Nhân xet va đanh gia

 Viêc xoa tât ca cac nut trên đ

ng đôc đao la

ườ

̣ ́ ̀ ́ ́

đê tiêt kiêm bô nh

ớ ,

̣ ́ ́ ̉ ́ ́ ̣ ̣ ̀

 Hinh dang cua cây chi phu thuôc vao cac gia tri

̉ ́ ̣ ̣

ứ

 Đô ph c tap trong moi tr

ng h p đêu la O(z),

ch a trong cây, ứ

̣ ườ

ợ

̀ ́ ̉ ̉ ̣ ̣ ̀ ́ ́ ̣

̣ ̣ ̀ ̀

 Chu y chung

 Hai bai toan săp xêp va tim kiêm rât đăc thu

́ ́

cua Tin hoc.

̀ ́ ́ ́ ̀ ̀ ́ ́ ̣ ̀

̉ ̣

́ ́ ́ ̣ ́ ́ ́

̃ ́ ̣ ́ ̀ ́ ̣ ́

 Không nên đanh gia cac thuât toan săp xêp cung nh cac thuât toan tim kiêm môt cach tông quat ma con tuy thuôc vao yêu câu cu thê, tinh chât d liêu cu thê,.. ́ ữ

̉ ́ ̀ ̀ ̀ ̣ ̀ ̀ ̣

̉ ́ ̣ ̣ ̉