Chương 2

Chiến lược chia-để-trị (Divide-and-conquer)

1

Nội dung

2

1. Chiến lược chia để trị 2. Quicksort 3. Xếp thứ tự bằng phương pháp trộn 4. Xếp thứ tự ngoại 5. Cây tìm kiếm nhị phân

Chiến lược chia-để-trị

 Là chiến lược thiết kế giải thuật nổi tiếng nhất.  Các giải thuật chia-để-trị thường tiến hành theo các bước sau:  Thể hiện của bài toán được chia làm những thể hiện nhỏ

hơn.

 Những thể hiện nhỏ hơn này được giải quyết (thường là đệ

quy, mặc dù đôi khi không cần đệ quy).

 Những lời giải đạt được từ những thể hiện nhỏ hơn phối

hợp lại làm thành lời giải của bài toán ban đầu.

 Tìm kiếm bằng p.p. chia đôi (binary search) là một thí dụ của

chiến lược chia-để-trị.

 Sơ đồ sau mô tả một chiến lược chia-để-trị mà trong đó chia bài toán thành hai bài toán nhỏ hơn. Đây là trường hợp phổ biến nhất của chiến lược này.

3

Chiến lược chia-để-trị

bài toán kích thước n

bài toán con 2 kích thước n/2

bài toán con 1 kích thước n/2

lời giải cho bài toán con 1

lời giải cho bài toán con 2

lời giải cho bài toán ban đầu

4

2. Giải thuật Quick sort

ả ậ ượ ả ủ i thu t căn b n c a Quick sort đ c phát minh năm

ở Gi 1960 b i C. A. R. Hoare.

ố ầ ế ế ả t k  gi ậ i thu t theo l i

ể ệ ượ ư ộ c  a chu ng vì nó không quá khó đ  hi n

ự

ỉ ừ NlgN thao tác căn

ứ ự ả ể ệ Quicksort th  hi n tinh th n thi “Chia đ  trể ị” (divide­and­conquer). Quicksort đ th c hóa.  Quicksort ch  đòi h i kho ng ch ng  ể ắ b n đ  s p th  t ỏ  N ph n t ả ầ ử .

ượ c đi m c a Quick sort g m:

ả ườ ợ ồ ậ ệ i thu t đ  quy  2 thao tác căn b n  trong tr ng h p

5

ậ ủ ể Nh ộ ả    ­ Nó là m t gi ả ầ    ­ Nó c n kho ng N ấ ấ x u nh t  ễ ị ỗ    ­ Nó d  b  l i khi l p trình (fragile).

Giải thuật căn bản của Quicksort

ế ộ ể ng pháp x p th  t

ệ ằ ứ ự  theo ki u  phân ho chạ  m t ộ

ắ ứ ự ỗ ộ ầ  m i ph n m t

ư ậ ả ươ Quicksort là m t ph ự ể ị “chia đ  tr ”. Nó th c hi n b ng cách  ầ ậ t p tin thành hai ph n và s p th  t ộ ậ ớ cách đ c l p v i nhau. ấ Gi i thu t có c u trúc nh  sau:

procedure quicksort1(left,right:integer); var i: integer; begin

if right > left then  begin

i:= partition(left,right); quicksort(left,i­1); quicksort(i+1,right);

6

end; end;

Phân hoạch

ủ ụ ạ Ph n then ch t c a Quicksort là th  t c phân ho ch

ắ ế ạ ỏ ả i m ng sao cho th a mãn 3

ượ ư ề ị ắ ủ ớ c đ a v  v  trí đúng đ n c a nó, v i

trong nhóm a[left], ..., a[i­1] thì ii) t

nh  h n hay b ng

ầ ử trong nhóm a[i+1], ..., a[right] thì iii) t

ố ủ ầ (partition), mà s p x p l ệ ề đi u ki n sau: ầ ử a[i] đ   i) ph n t   ộ ị i nào đó,  m t giá tr   ầ ử ấ ả ữ t c  nh ng ph n t ằ a[i] ỏ ơ ấ ả ữ t c  nh ng ph n t ằ a[i] ớ ơ l n h n hay b ng

Example:

7

53    59   56 52   51    53 52 56 55 55 58 58 51 59 57 57 54 54

Thí dụ về phân hoạch

ọ ả ử ầ ử ậ

ủ ư ầ ử  này đ ầ ử ứ ấ  s  đ c g i là th  nh t hay ph n t  t n  ầ ử ẽ ượ ư ề ị c đ a v  v  trí  ầ ử ố  ­  ượ ọ  ch t ph n t

s  chúng ta ch n ph n t Gi cùng trái (leftmost ) nh  là ph n t đúng c a nó ( Ph n t pivot).

40 15 30 25 60 10 75 45 65 35 50 20 70 55

40 15 30 25 20 10 75 45 65 35 50 60 70 55

40 15 30 25 20 10 35 45 65 75 50 60 70 55

35 15 30 25 20 10 40 45 65 75 50 60 70 55

nhỏ hơn 40 sorted lớn hơn 40

8

Giải thuật Quicksort procedure quicksort2(left, right: integer); var j, k: integer; begin

if right > left then begin      j:=left; k:=right+1;                   //start partitioning

repeat

repeat j:=j+1 until a[j] >= a[left]; repeat k:=k­1 until a[k]<= a[left]; if j< k then swap(a[j],a[k])

until j>k;     swap(a[left],a[k]);  //finish partitioning     quicksort2(left,k­1);     quicksort2(k+1,right) end;

end;

9

Phân tích độ phức tạp: trường hợp tốt nhất

ườ ấ ả ợ ố ỗ ầ ớ ng h p t

ạ t nh t x y ra v i Quicksort là khi m i l n  ầ ằ

ậ ố ầ ủ ỏ

ề ệ ứ Tr phân ho ch chia t p tin ra làm hai ph n b ng nhau. đi u này làm cho s  l n so sánh c a Quicksort th a mãn  ồ : h  th c truy h i

CN = 2CN/2 + N.

ủ ố ạ ử ậ

ệ ủ ệ ắ ừ ứ ự ầ ử hai n a t p   khi phân

ầ

ả ệ ứ ệ ư ế ng 1, vi c gi ồ i h  th c truy h i này đã đ a đ n

10

N lgN. S  h nh 2C N/2 là chi phí c a vi c s p th  t tin và N là chi phí c a vi c xét t ng ph n t ầ ạ ho ch l n đ u.  ừ ươ T  ch ờ ả i:  i gi l CN (cid:0)

Phân tích độ phức tạp: trường hợp xấu nhất

ộ ườ ợ ấ ấ ủ ậ đã

M t tr có th  t ng h p x u nh t c a Quicksort là khi t p tin  ứ ự ồ .   r i

ầ ử ứ ấ ẽ ể ậ th  nh t s  đòi h i

ị ơ ữ ứ ấ

ỗ ớ ầ ế ạ

ả ồ ầ ử ứ ở ậ . Do đó v i l n phân ho ch k , ph n t ỏ n­1 so sánh đ  nh n ra r ng nó nên th  hai  ị  đúng v

ể ứ ế ụ ỏ n so sánh đ  nh n ra  Khi đó, ph n t ở ằ  đúng v  trí th  nh t. H n n a, sau đó phân  r ng nó nên  ạ ạ đo n bên trái là r ng và và phân đo n bên ph i g m n – 1  ầ ử ph n t ằ ẽ s  đòi h i  ư ế ứ trí th  hai. Và c  ti p t c nh  th .

ư ậ ổ ẽ

ố ầ Nh  v y t ng s  l n so sánh s  là:    n + (n­1) + … + 2 + 1 = n(n+1)/2 =                                    (n2 + n)/2 = O(n2).

ườ ợ ấ ấ ủ ng h p x u nh t c a Quicksort là

11

ộ ứ ạ Đ  ph c t p tr O(n2).

Độ phức tạp trường hợp trung bình của Quicksort

ồ ứ

ầ ể ắ ứ ự ầ ử ượ ộ ổ  đ N ph n t ố c hình thành m t

(Ck­1 + CN­k)

Công th c truy h i chính xác cho t ng s  so sánh mà Quick  sort c n đ  s p th  t ẫ cách ng u nhiên:                                                      N CN = (N+1) +   (1/N) (cid:0)                                                      1

(cid:0) v i N ớ 2 và C1 = C0 = 0

ồ ố ầ ch t v i

ạ

ể ượ ấ ầ ự ệ c làm

12

ầ ử ố ớ ố ạ S  h ng (N+1) bao g m s  l n so sánh ph n t ể ầ ử ừ  khác, thêm hai l n so sánh đ  hai pointer  t ng ph n t ỗ ầ ử ở ị ầ  v  trí    giao nhau. Ph n còn l i là do s  ki n m i ph n t ầ ử ố  mà sau  k có cùng xác xu t 1/N đ  đ  ch t ph n t ạ ớ ố ầ ử ầ ượ k­ t là   l n l đó chúng ta có hai phân đo n v i s  ph n t 1 và N­k.

0 + C1 + … + CN­1 thì gi ng h t

ố ệ ằ Chú ý r ng, C

2Ck­1

CN­1 + CN­2  +… + C0, nên ta có                                                    N CN = (N+1) +  (1/N) (cid:0)                                                    1

ể ạ ừ ạ ượ ổ ả ng tính t ng b ng cách nhân c

ế ớ ằ ứ ớ Ta có th  lo i tr  đ i l ồ ừ hai v  v i N và r i tr  cho cùng công th c nhân v i N­1:

NCN – (N­1) CN­1  = N(N+1) – (N­1)N +  2CN­1

ừ T  đó ta đ ượ c

13

NCN = (N+1)CN­1 + 2N

ả ượ ệ ứ ồ ế ớ Chia c  hai v  v i N(N+1) ta đ c h  th c truy h i:

CN/(N+1) =  CN­1/N +  2/(N+1)

.

.

= CN­2 /(N­1) + 2/N   +  2/(N+1)

2/(k+1)

N                 =  C2 /3  + (cid:0)                                                 3                                    N                      N CN/(N+1) (cid:0)

1                     1

1/k (cid:0) 2 (cid:0) 2 (cid:0) 1/x dx = 2lnN

Suy ra:

CN

14

(cid:0) 2NlnN

Độ phức tạp trường hợp trung bình của Quicksort (tt.)

Vì ta có:

lnN = (log2N).(loge2) =0.69 lgN

1.38 NlgN.

ố

ả

ổ ừ

ợ ố

ơ

2NlnN (cid:0) (cid:0) T ng s  so sánh trung bình c a Quicksort ch  kho ng  ch ng 38% cao h n trong tr

ủ ườ ng h p t

ỉ ấ t nh t.

ả ề. Quicksort  c n kho ng 2NlnN so sánh trong  ợ

ệ M nh đ ườ tr

ng h p trung bình

ầ .

15

3. Sắp thứ tự bằng cách trộn (mergesort)

ướ

ượ ọ

ộ ố ợ

ứ ự ớ

ộ ậ

ứ ự

c g i là  Tr tr nộ  (merging), thao tác ph i h p hai t p tin đã có  th  t

c tiên, chúng ta xét m t quá trình đ ậ ơ    l n h n.

thành m t t p tin có th  t

Tr nộ

ụ

khá l n. Các ph n t

ượ

ớ

ả ử ề ứ Trong nhi u  ng d ng x  lý d  li u, ta ph i duy trì  ộ ậ ữ ệ ầ ử ớ ứ ự  m i  m t t p d  li u có th  t ườ ng xuyên đ th

ữ ệ ớ ậ c thêm vào t p tin l n.

đ

c đính vào đuôi c a t p tin  ượ ắ

ầ ử ượ Nhóm các ph n t ộ ậ ớ l n và toàn b  t p tin đ

ủ ậ ứ ự ở ạ  tr  l

c s p th  t

i.

ợ

ố

ấ

Tình hu ng đó r t thích h p cho thao tác

tr nộ .

16

Trộn

ố ả ử s  ta có hai m ng s  nguyên có th  t

ố ứ ả ộ

ứ ự  a[1..M] và  Gi ả ộ b[1..N]. Ta mu n tr n chúng thành m t m ng th  ba  c[1..M+N]. i:= 1; j  :=1; for k:= 1 to M+N do    if a[i] < b[j] then            begin c [k] := a[i]; i:= i+1 end  else  begin c[k] := b[j]; j := j+1 end;

ậ ể

ị ớ ơ ứ

ọ ị ạ ặ ả

17

ộ ạ ủ ầ ạ ầ ả Ghi chú:  Gi i thu t dùng a[M+1] và b[N+1] đ  làm ph n  ầ  ử c m canh  ch a hai giá tr  l n h n m i tr  khóa khác.  t ờ Nh  chúng, khi m t trong hai m ng đã c n thì vòng l p  ả ẽ ư i c a m ng còn l s  đ a ph n còn l i vào m ng ả c.

Sắp thứ tự bằng phương pháp trộn

Một khi ta đã có thủ tục trộn, ta dùng nó làm cơ sở để xây dựng một thủ tục sắp thứ tự đệ quy.

Để sắp thứ tự một tập tin nào đó, ta chia thành hai đoạn bằng nhau, sắp thứ tự hai đoạn này một cách đệ quy và rồi trộn hai đoạn lại với nhau.

Mergesort thể hiện chiến lược thiết kế giải thuật theo lối “Chia để trị” (divide-and-conquer).

18

Giải thuật sau sắp thứ tự mảng a[1..r], dùng mảng b[1..r] làm trung gian,

procedure mergesort(1,r: integer); var i, j, k, m : integer; begin       if r­1>0 then           begin

m:=(r+1)/2; mergesort(1,m); mergesort(m+1,r); for i := m downto 1 do b[i] := a[j]; for j :=m+1 to r do b[r+m+1­j] := a[j]; for k :=1 to r do      if b[i] < b[j] then

begin a[k] := b[i] ; i := i+1 end

else begin a[k] := b[j]; j:= j­1 end;

19

end; end;

A S O R T I N G E X A M P L E

A S

ứ ự   ữ ồ

O R

ụ ắ Thí d : S p th  t ả ộ m t m ng g m nh ng   chự ữ ký t

A O R S

I T

G N

G I N T

A G I N O R S T

E X

A M

A E M X

L P

E L P

A E E L M P X

A A E E G I L M N O P R S T X

20

Độ phức tạp của giải thuật Mergesort

ấ

ắ

ng pháp tr n c n

S p th  t

ộ ầ ầ ử

ươ ứ ự ằ  b ng ph Tính ch t 4.1: ể ắ ấ ỳ ậ ả kho ng NlgN so sánh đ  s p b t k  t p tin N ph n t nào.

ậ

ệ ứ

ả ằ

ệ i thu t mergesort đ  quy, s  l n so sánh  ồ  b ng h  th c truy h i: C

ố ầ N = 2CN/2 + N, v i  ớ

ố ớ ả  Đ i v i gi ượ c mô t đ C1 = 0.

N lg N

ứ ự ằ

ươ

ộ ầ

ng pháp tr n c n

: S p th  t

Suy ra:  CN (cid:0) Tính ch t 4.2ấ ắ ỗ ộ ớ dùng ch  b  nh  thêm t  l

b ng ph ỉ ệ ớ .   v i N

21

4. Sắp thứ tự ngoại

ộ ớ ụ ượ ớ ư ữ c

ậ  các t p tin l n l u tr  trên b  nh  ph  đ ứ ự  ngo i

ạ  (external sorting). ọ ệ ả ị ơ  ngo i r t quan tr ng trong các h  qu n tr  c

ứ ự ắ S p th  t ắ g i là ọ s p th  t ạ ấ ứ ự ắ S p th  t ở ữ ệ s  d  li u (DBMSs).

ố ố ạ  Kh i (block) và truy đ t kh i (Block Access)

ố c b ng nhau. Kích th

ướ ằ ệ ề ư ả ữ kh i ố có  ổ c c a kh i thay đ i tùy  ế  kho ng 512 đ n 4096 ộ ớ ụ ướ ủ ườ ở ng

ệ ề H  đi u hành phân chia b  nh  ph  thành nh ng  kích th theo h  đi u hành, nh ng th byte.

ụ ậ ả Các tác v  căn b n trên các t p tin là

ộ ệ ở ộ ớ ố ộ ­     mang m t kh i ra b  đ m b  nh  chính ( read)

22

ố ừ ộ ớ ộ ­     mang m t kh i t b  nh  chính v  b  nh  ph  ( ề ộ ớ ụ write).

Sắp thứ tự ngoại

ủ ướ ượ c l ng th i gian tính toán c a các gi ậ i thu t mà

ệ ả

ả ố ầ ộ ộ ớ ố ế

ờ Khi  ậ làm vi c trên các t p tin, chúng ta ph i xét s  l n mà chúng  ố ề ộ ộ ọ t m t kh i v  b   ta đ c m t kh i ra b  nh  chính hay vi ớ ụ nh  ph .

ộ ụ ư ậ ượ ọ ạ c g i là m t ộ truy đ t kh i ố  (block

ạ M t tác v  nh  v y đ access) hay m t ộ truy đ t đĩa (disk access).

23

ố kh i = trang (page)

Xếp thứ tự ngoại bằng p.p. trộn (External Sort- merge)

ỹ ứ ự ả i

ứ ự ươ ạ  ngo i là gi ộ external ụ ấ ể ắ ạ ằ  ngo i b ng ph ng pháp tr n (

ậ K  thu t thông d ng nh t đ  s p th  t ậ ắ thu t s p th  t sort­merge algorithm) .

ươ ứ ự ắ ồ ạ ướ Ph ng pháp s p th  t ngo i này g m 2 b c:

ạ ­  t o các run

­  tr n run ộ

ươ ng pháp s p th  t ng pháp tr n

ắ ỹ ụ ứ ự Ph ậ cũng áp d ng k  thu t thi ạ ằ  ngo i b ng ph ế ế ả t k  gi ộ ươ ậ chia­đ ­trể ị. i thu t

ộ ớ

24

M: s  ố trang (page) c a ủ b  đ mộ ệ  trong b  nh  chính  (memory­buffer) .

Xếp thứ tự ngoại bằng p.p. trộn (tt.)

ướ ộ ố c đ b ng ằ ứ ự ượ t o raạ c 1, m t s  run có th  t

1. Trong b cách sau:  i = 0;  repeat       read M blocks of the file, or the rest of the file, whichever is       smaller;       sort the in­memory part of the file;       write the sorted data to the run file Ri;       i = i+1;   until the end of the file.

25

ướ 2. Trong b c 2, các run đ ượ tr nộ  l c i. ạ

Trộn run (trường hợp tổng quát)

ượ

ằ ươ ườ   ng ứ ự ộ  n i  ượ ọ c g i

ng

ủ ộ tr n hai đ ở ả ậ ắ c dùng b i gi i thu t s p th  t ộ ộ ng pháp tr n. Nó tr n N run, do đó nó đ ề ườ  (n­way merge). ợ ổ ườ ng h p t ng quát:

ứ ủ ộ ệ ớ ơ ứ ế ậ ự ụ ộ Tác v  tr n là s  khái quát hóa c a phép  (two­way merge) đ b ng ph ộ là  tr n nhi u đ  (cid:0)  Tr ề ổ V  t ng quát, n u t p tin l n h n s c ch a c a b  đ m

N > M

ể ộ ệ ộ

ườ ướ ợ ự ộ ng h p này, s  tr n ph i tr i

ỗ  thì không th  dành m t trang trong b  đ m cho m i run  ả ả ộ trong b c tr n. Trong tr qua nhi u ề chuy nế  (passes).

ỉ ủ ộ ệ ầ

26

ộ ầ ự Vì ch  có M­1 trang c a b  đ m dành cho các đ u vào, s   ể ế tr n có th  ti p nh n ư ậ M­1 runs nh  là các đ u vào.

Trộn run [trường hợp tổng quát] (tt.)

ế ư

ượ ộ ầ ầ ộ c tr n l

ế ế ệ ộ ạ ẽ ượ i thành m t run cho chuy n  c tr n theo cách t

ươ ề ượ

ể ả ộ ầ t c  các run đ u tiên đ u đ ượ c gi m đi m t ế ự ng t   ả i  c gi ừ ố ộ th a s

Chuy n tr n đ u tiên làm vi c nh  sau:      M­1 run đ u tiên đ ồ k  ti p. R i thì M­1 runs s  đ ấ ả ứ ế ế và c  th  cho đ n khi t ố ổ ạ ế quy t. T i đi m này, t ng s  run đ M­1.

(cid:0) ượ ả ẫ

ự ở ượ ạ c gi m đi này v n còn  ớ c th c thi v i các run đ M, m t ộ c t o ra b i

ế ố ế ữ ẽ ượ ế ầ ầ N u s  run đã đ chuy n n a s  đ chuy n đ u tiên làm đ u vào.

ả ổ ỗ

ế ế ứ ặ ạ ừ ố ế ổ

ế ẽ ạ ỏ ơ ề ế ế ả

27

ộ ố   M i chuy n làm gi m t ng s  run m t th a s  M – 1. Các  ố ư ầ t cho đ n khi t ng s   i nhi u nh  c n thi chuy n c  l p l ộ ố run nh  h n M; chuy n cu i cùng s  t o ra k t qu  là m t  ậ t p tin có th  t ứ ự   .

Một thí dụ của thứ tự ngoại bằng p.p. trộn

ả ử

ừ

ộ

ộ

ố

ế

ẩ

Gi

s :    i) m t m u tin chi m v a m t kh i

ộ ệ

ế

ii) b  đ m chi m 3 trang.

ạ

ầ

c dùng làm đ u

ộ Trong giai đo n tr n, hai trang đ ượ ộ vào và m t trang đ

ượ ả ể ứ ế c dùng đ  ch a k t qu .

ỏ

ộ

ế

ạ

Giai đo n tr n đòi h i hai chuy n.

28

a  19 d  31 g  24

b  14 c  33 e  16

a  19 b  14 c  33 d  31 e  16 g  24

g  24 a  19 d  31 c  33 b  14 e  16 r  16 d  31 d  21 m  3 m 3 r  16 p  2 d  7 a  14

a  14 d  7 d  21 m 3  p  2 r  16

a  14 a  19 b  14 c  33 d  7 d  21 d  31 e  16 g  24 m 3 p  2 r  16

a  14 d  17 p  2

Tạo run trộn pass-1 trộn pass-2

29

Độ phức tạp của xếp thứ tự ngoại

ủ ả ậ i thu t

ươ ộ ạ ố Hãy tính s  truy đ t kh i ( ạ ằ ứ ự ắ  ngo i b ng ph s p th  t ố block accesses) c a gi ng pháp tr n.

ố ố ủ ậ ổ br  : t ng s  kh i c a t p tin.

c đ c và ghi, đem

ố ượ ọ ố ộ ạ ạ ạ Trong giai đo n t o run, m t kh i đ ố r, truy đ t kh i.  ạ ộ ổ l i m t t ng s  2b

ố ổ ầ T ng s  run ban đ u là

ố ổ ộ ế T ng s  chuy n tr n: br/M.      (cid:0) log M­1(br/M)(cid:0)

ỗ ố ủ ậ ế ượ ọ c đ c

30

ộ ầ ộ ầ ộ ừ Trong m i chuy n tr n, t ng kh i c a t p tin đ m t l n và ghi m t l n.

Độ phức tạp của xếp thứ tự ngoại(tt)

ố ậ ắ ứ ự ả i thu t s p th  t ạ ằ  ngo i b ng

ạ ộ

ổ T ng s  truy đ t đĩa cho gi ươ ng pháp tr n là: ph  2br + 2br (cid:0) logM­1(br/M)(cid:0)    =     2br( (cid:0) logM­1 (br/M)(cid:0)  +1)

ạ t o run

31

các chuy n ế tr nộ

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

Nhiều bài toán liên quan đến cây tìm kiếm nhị phân có thể được giải bằng cách áp dụng chiến lược chia-để-trị

Trong một cây tìm kiếm nhị phân (binary search tree), tất cả các mẩu tin với khóa nhỏ hơn khóa tại nút đang xét thì ở cây con bên trái của nút và các mẩu tin với khóa lớn hơn hay bằng khóa tại nút đang xét thì ở cây con bên phải của nút.

32

Khởi tạo cây nhị phân

type link = (cid:0) node; node = record key, info: integer; l, r: link end; var t, head, z: link;

Một cây rỗng được biểu diễn bằng cây có con trỏ bên phải chỉ đến nút giả z.

33

procedure tree_init; begin new(z); z(cid:0) .1: = z; z(cid:0) .r: = z; new(head); head(cid:0) .key: = 0; head(cid:0) .r: = z; end;

Tác vụ thêm vào

Thêm một nút vào trong cây, ta thực hiện một sự tìm kiếm (không thành công) nút ấy trên cây, rồi gắn nút ấy vào vị trí ứng với nút giả z tại điểm mà quá trình tìm kiếm kết thúc.

Hình vẽ minh họa việc thêm nút P vào cây nhị phân.

34

Tác vụ thêm vào (tt.)

procedure tree_insert (v: integer; x: link): link; var p: link; begin repeat p: = x; if v < x(cid:0) .key then x: = x(cid:0) .1 else x: = x(cid:0) .r until x = z; new(x); x(cid:0) .key: = v; x(cid:0) .1: = z; x(cid:0) .r: = z; /* create a new node */ if v < p(cid:0) . key then p(cid:0) .1: = x /* p denotes the parent of the new node */ else p(cid:0) .r: = x; tree_insert: = x end

35

Tác vụ tìm kiếm

type link = (cid:0) node; node = record key, info: integer; l, r: link end; var t, head, z: link;

function treesearch (v: integer, x: link): link; /* search the node with the key v in the binary search tree x */ begin while v <> x(cid:0) . key and x <> z do begin if v < x(cid:0) .key then x: = x(cid:0) .1 else x: = x(cid:0) .r end; treesearch: = x end;

36

Tính chất của sự tìm kiếm trên cây nhị phân

Tính chất: Một tác vụ thêm vào hay tìm kiếm trên một cây nhị phân đòi hỏi chừng 2lnN so sánh trên một cây được tạo ra từ N trị khóa ngẫu nhiên.

Chứng minh: Chiều dài lối đi của 1 nút: là số cạnh cần duyệt qua để từ nút ấy về nút rễ +1.

Đối với mỗi nút trên cây nhị phân, số so sánh được dùng cho một sự tìm kiếm nút ấy thành công chính là chiều dài lối đi của nút ấy.

Tổng tất cả chiều dài lối đi của mọi nút trên cây nhị phân được gọi là chiều dài lối đi của cây nhị phân.

37

Chứng minh (tt.)

 Khi chia chiều dài lối đi toàn cây với N, ta sẽ được số so sánh trung bình đối với một sự tìm kiếm thành công trên cây.

 Nhưng nếu CN biểu thị chiều dài lối đi trung bình của toàn

cây, ta có một hệ thức truy hồi sau đây, với C1 = 1 (cid:0) N

(Ck­1 + CN­k)

CN = N +

1

Số hạng N là do sự kiện nút rễ đóng góp 1 vào chiều dài lối đi của mỗi nút. Số hạng thứ hai là do sự kiện khóa tại nút rễ có xác xuất bằng nhau để trở thành phần tử lớn thứ k trong cây, với hai cây con lần lượt chứa k-1 nút và N-k.

38

Chứng minh (tt.)

2N lnN.

Một tác vụ tìm kiếm hay thêm vào đòi hỏi trung bình 2lnN so

Hệ thức truy hồi này rất giống hệ thức truy hồi khi phân tích Quicksort, và nó đã được giải cùng một cách để đưa lại cùng một kết quả. Do đó chiều dài trung bình của cây N nút là CN (cid:0) Suy ra chiều dài trung bình của một nút trong cây là 2lnN. (cid:0) sánh trên một cây gồm N nút.

39

Độ phức tạp trong trưòng hợp xấu nhất

 Tính chất: Trong trường hợp xấu nhất, một tác vụ

 Trường hợp xấu nhất xảy ra khi cây nhị phân bị suy

tìm kiếm trên cây tìm kiếm nhị phân gồm N khóa có thể cần N so sánh.

40

biến thành một danh sách liên kết.