CTDL 2005 chuong 11
Hàng ưu tiên
Chöông 11 – Haøng öu tieân
Chöông 11 – HAØNG ÖU TIEÂN
Caáu truùc döõ lieäu haøng ñôïi maø chuùng ta ñaõ xem xeùt trong chöông 3 laø theo ñuùng
nguyeân taéc FIFO. Tuy nhieân trong thöïc teá, coù nhöõng tröôøng hôïp caàn coù söï linh
ñoäng hôn. Chaúng haïn trong soá caùc coâng vieäc caàn xöû lyù, coù moät soá ít coâng vieäc voâ
cuøng quan troïng, chuùng caàn ñöôïc xöû lyù caøng sôùm caøng toát ngay khi coù theå. Hoaëc
trong tröôøng hôïp coù nhieàu taäp tin cuøng ñang chôø ñöôïc in, moät soá taäp tin chæ coù 1
trang trong khi moät vaøi taäp tin khaùc thì raát daøi. Neáu caùc taäp tin 1 trang ñöôïc in
tröôùc thì khoâng aûnh höôûng ñeán thôøi gian chôø ñôïi cuûa caùc taäp tin khaùc bao nhieâu.
Ngöôïc laïi, neáu cöù theo thöù töï FIFO, moät soá baûn in chæ coù 1 trang laïi phaûi chôø ñôïi
quaù laâu.
Haøng coù xeùt thöù töï öu tieân, hay goïi taét laø haøng öu tieân (priority queue), laø moät
caùch giaûi quyeát caùc tröôøng hôïp treân moät caùch thoûa ñaùng. Tuøy vaøo öùng duïng, tieâu
chí ñeå xeùt ñoä öu tieân do chuùng ta quyeát ñònh. Trong chöông naøy chuùng ta seõ ñaëc
taû vaø hieän thöïc CTDL cho haøng öu tieân naøy.
11.1. Ñònh nghóa haøng öu tieân
Haøng öu tieân coù caùc phöông thöùc gaàn gioáng nhö moät haøng ñôïi thoâng duïng, chæ
khaùc veà maët chieán löôïc:
Ñònh nghóa: Moät haøng öu tieân caùc phaàn töû kieåu T goàm caùc phaàn töû cuûa T, keøm
caùc taùc vuï sau:
1. Taïo môùi moät ñoái töôïng haøng roãng.
2. priority_append: Theâm moät phaàn töû môùi vaøo haøng, giaû söû haøng chöa ñaày
(tuøy vaøo ñoä öu tieân cuûa phaàn töû döõ lieäu môùi noù seõ ñöôïc ñöùng ôû moät vò trí thích
hôïp).
3. priority_serve: Loaïi moät phaàn töû ra khoûi haøng, giaû söû haøng chöa roãng
(phaàn töû bò loaïi laø phaàn töû ñeán löôït ñöôïc xem xeùt theo quy öôùc ñoä öu tieân ñaõ
ñònh).
4. priority_retrieve: Xem phaàn töû taïi ñaàu haøng (phaàn töû saép ñöôïc xem xeùt).
11.2. Caùc phöông aùn hieän thöïc haøng öu tieân
Giaû söû ñoä öu tieân laø söï keát hôïp bôûi ñoä öu tieân theo tieâu chí maø chuùng ta ñaõ
choïn cuøng vôùi thöù töï xuaát hieän cuûa coâng vieäc. Khi ñöa vaøo haøng, moãi coâng vieäc seõ
coù moät thoâng soá ñeå chöùa ñoä öu tieân naøy. Chuùng ta quy öôùc raèng ñoä öu tieân caøng
nhoû thöù töï öu tieân caøng cao.
Chuùng ta coù theå duøng DSLK ñôn ñeå hieän thöïc haøng öu tieân. Vieäc theâm vaøo
luoân thöïc hieän ôû ñaàu danh saùch, vieäc laáy ra seõ phaûi duyeät laàn löôït heát danh saùch
ñeå choïn phaàn töû coù ñoä öu tieân cao nhaát. Ngöôïc laïi, neáu khi theâm vaøo luoân giöõ
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 283
Chöông 11 – Haøng öu tieân
danh saùch ñuùng thöù töï taêng daàn cuûa ñoä öu tieân, khi laáy ra chæ caàn laáy phaàn töû ñaàu
danh saùch. Caû hai caùch ñeàu toán O(1) cho moät taùc vuï vaø O(N) cho taùc vuï coøn laïi.
Phöông aùn thöù hai coù theå hieän thöïc haøng öu tieân bôûi moät caây nhò phaân tìm
kieám (BST). Phöông aùn naøy caàn O(logN) cho moãi taùc vuï theâm hoaëc loaïi phaàn töû.
Taùc vuï priority_serve seõ luoân laáy ra phaàn töû cöïc traùi cuûa caây nhò phaân, ñieàu
naøy seõ laøm cho caây maát caân baèng vaø coù theå khaéc phuïc baèng caùch söû duïng caây AVL
thay cho caây BST bình thöôøng.
Tuy nhieân caùc phöông aùn söû duïng caây treân ñaây hôi bò thöøa. Vieäc quaûn lyù caây
quaù phöùc taïp so vôùi muïc ñích cuûa chuùng ta.
Caùch hieän thöïc ñôn giaûn vaø phoå bieán cho haøng öu tieân laø heap nhò phaân
(binary heap), coù khi coøn ñöôïc goïi taét laø heap. Vaø vì noù khaù phoå bieán neân nhieàu
luùc ngöôøi ta chæ goïi ñôn giaûn laø heap, chöù khoâng coøn goïi laø haøng öu tieân nöõa.
Ñònh nghóa heap nhò phaân ñaõ ñöôïc trình baøy trong chöông 8. Trong chöông naøy
chuùng ta söû duïng heap nhò phaân laø moät min-heap.
Phaàn hieän thöïc moät CTDL heap cuï theå ñöôïc xem nhö baøi taäp. Phaàn tieáp sau
ñaây trình baøy caùc thao taùc treân heap baèng maõ giaû, vaø ñeå deã daøng hình dung
chuùng ta cuõng vaãn duøng hình aûnh cuûa caây nhò phaân ñeå minh hoïa.
11.3. Hieän thöïc caùc taùc vuï cô baûn treân heap nhò phaân
11.3.1. Taùc vuï theâm phaàn töû
Ñeå theâm moät phaàn töû môùi vaøo heap, chuùng ta taïo moät choã troáng ngay sau
phaàn töû cuoái cuûa heap, ñieàu naøy baûo ñaûm heap vaãn coù caáu truùc caây nhò phaân ñaày
ñuû hoaëc gaàn nhö ñaày ñuû. Neáu phaàn töû môùi coù theå ñaët vaøo choã troáng naøy maø khoâng
vi phaïm ñieàu kieän thöù hai cuûa heap (baèng caùch so saùnh phaàn töû môùi vôùi nuùt cha
cuûa choã troáng naøy) thì giaûi thuaät keát thuùc. Ngöôïc laïi, chuùng ta laáy phaàn töû cha
cuûa choã troáng naøy ñeå laáp vaøo choã troáng, luùc ñoù seõ xuaát hieän choã troáng môùi. Coâng
vieäc laäp laïi töông töï cho ñeán khi tìm ñöôïc vò trí thích hôïp cho phaàn töû môùi.
Hình 11.1 minh hoïa vieäc theâm phaàn töû 14 vaøo moät heap.
Vieäc theâm phaàn töû môùi toán nhieàu nhaát laø O(logN).
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 284
Chöông 11 – Haøng öu tieân
13 13
16 16
21 21
68 68
19 19
31
24 24
26 26 31
65 32 65 32
13
13
16
14
16
68
19
21
24
68
19
21
24
26 31
65 32
26 31
65 32
Hình 11.1. Theâm phaàn töû 14 vaøo heap
ErrorCode Priority_Queue::priority_append(Entry item)
/*
pre: ñoái töôïng Priority_Queue coù thuoäc tính heap laø maûng lieân tuïc chöùa caùc phaàn töû.
post: item ñöôïc theâm vaøo haøng öu tieân sao cho tính chaát heap vaãn thoaû.
*/
{
1. if (full())
1. return overflow;
2. else
1. current_position = size()
2. loop ((toàn taïi parent laø cha cuûa phaàn töû taïi current_position) AND
(parent > item)
// Laàn löôït di chuyeån caùc nuùt cha xuoáng neáu cha lôùn hôn item ñeå laáp choã troáng
1. heap[current_position] = parent
2. Cho current_position laø vò trí cuûa parent
3. endloop
4. heap[current_position] = item
5. // Caäp nhaät laïi kích thöôùc cuûa heap.
6. return success
3. endif
}
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 285
Chöông 11 – Haøng öu tieân
11.3.2. Taùc vuï loaïi phaàn töû
Vieäc loaïi phaàn töû cuõng töông töï vieäc theâm vaøo. Phaàn töû laáy ra chính laø phaàn
töû taïi goác cuûa caây vì ñoù laø phaàn töû coù ñoä öu tieân cao nhaát. Vieäc coøn laïi laø giaûi
quyeát cho choã troáng naøy. Trong hình 11.2 chuùng ta seõ thaáy quaù trình di chuyeån
cuûa choã troáng. Moät trong hai phaàn töû con cuûa noù seõ di chuyeån laáp ñaày choã troáng.
Phaàn töû nhoû nhaát trong hai phaàn töû con ñöôïc choïn ñeå thoûa ñònh nghóa cuûa heap.
Cuoái cuøng, vôùi choã troáng khoâng coøn nuùt con thì ñöôïc laáp ñaày bôûi phaàn töû cuoái cuûa
heap vì chuùng ta luoân bieát raèng ñaây laø caây nhò phaân ñaày ñuû hoaëc gaàn nhö ñaày ñuû,
noù luoân chöùa caùc phaàn töû coù theå ñieàn vaøo moät maûng lieân tuïc töø traùi sang phaûi. Vaø
thöïc söï chuùng ta cuõng hieän thöïc heap trong moät maûng lieân tuïc chöù khoâng phaûi
caáu truùc caây coù con troû. Moïi thao taùc vôùi caùc chæ soá ñeå ñònh vò ñeán caùc phaàn töû
cha, con, ñeàu raát nhanh choùng. Chuùng ta coù theå chaéc chaén raèng ñieàu kieän thöù hai
trong ñònh nghóa cuûa heap cuõng khoâng bò vi phaïm khi dôøi phaàn töû cuoái baèng caùch
naøy. Chi phí trong vieäc loaïi phaàn töû laø O(logN).
13
16 16
14 14
68 68
19 19
21 21
19 19
26 31 26 31
65 32 65 32
14
14
16
19
16
68
19
21
68
19
21
19
26 31
65 32
26 31
65 32
14
14
16
19
16
19
68
19
21
26
68
19
21
26
31
65 32
31
65 32
Hình 11.2. Loaïi moät phaàn töû ra khoûi heap
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 286
Chöông 11 – Haøng öu tieân
ErrorCode Priority_Queue::priority_serve()
/*
pre: ñoái töôïng Priority_Queue coù thuoäc tính heap laø maûng lieân tuïc chöùa caùc phaàn töû.
post: phaàn töû nhoû nhaát trong haøng öu tieân ñöôïc laáy ñi.
*/
{
1. if (empty())
1. return underflow;
2. else
1. current_position = 0
2. loop (phaàn töû taïi current_position coù con)// Laàn löôït di chuyeån caùc nuùt
// con leân ñeå laáp choã troáng.
1. child laø phaàn töû nhoû nhaát trong hai con
2. child ñöôïc cheùp leân vò trí current_position
3. Cho current_position laø vò trí cuûa child vöøa ñöôïc cheùp
3. endloop
4. heap[current_position] = heap[size()-1]
5. // Caäp nhaät laïi kích thöôùc cuûa heap.
6. return success
3. endif
}
11.4. Caùc taùc vuï khaùc treân heap nhò phaân
11.4.1. Taùc vuï tìm phaàn töû lôùn nhaát
Taùc vuï priority_retrieve truy xuaát phaàn töû beù nhaát trong min-heap coù chi
phí O(1). Ñoái vôùi vieäc tìm ra phaàn töû lôùn nhaát trong min-heap khoù khaên hôn.
Tuy vaäy, chuùng ta cuõng khoâng phaûi duøng caùch tìm tuyeán tính treân toaøn boä heap,
vì caùc phaàn töû trong heap luoân coù moät traät töï nhaát ñònh theo ñònh nghóa. Chuùng
ta thaáy ngay raèng phaàn töû lôùn nhaát phaûi laø moät trong caùc nuùt laù, ñoù laø moät nöûa
beân phaûi cuûa maûng lieân tuïc chöùa caùc phaàn töû cuûa heap.
11.4.2. Taùc vuï taêng giaûm ñoä öu tieân
Taïi thôøi ñieåm khi maø caùc coâng vieäc ñöôïc ñöa vaøo haøng öu tieân, moãi coâng vieäc
ñeàu ñaõ ñöôïc xaùc ñònh ñoä öu tieân, vaø chæ soá naøy chính laø khoùa ñöôïc xöû lyù bôûi heap.
Tuy nhieân, giaû söû trong khi caùc coâng vieäc ñang naèm trong haøng öu tieân ñeå chôø
ñeán löôït ñöôïc cung caáp dòch vuï, ngöôøi ñieàu haønh muoán can thieäp vaøo thöù töï öu
tieân naøy vì moät soá lyù do. Chaúng haïn coù moät coâng vieäc ñang phaûi chôø quaù laâu vaø coù
moät yeâu caàu ñoät xuaát caàn thuùc ñaåy noù ñöôïc hoaøn thaønh sôùm hôn. Ngöôïc laïi ngöôøi
ñieàu haønh cuõng coù theå muoán ñieàu chænh giaûm ñoä öu tieân moät coâng vieäc naøo khaùc.
Nhöõng ñieàu naøy raát thöôøng xaûy ra neáu chuùng ta xeùt trong moät tình huoáng raèng,
trong cheá ñoä phuïc vuï coù phaân chia thôøi gian, khi heát khoaûng thôøi gian quy ñònh,
neáu coâng vieäc vaãn chöa thöïc hieän xong thì laïi phaûi quay laïi haøng ñôïi naèm chôø
tieáp. Moãi coâng vieäc thöôøng phaûi ñôïi, ñöôïc phuïc vuï, ñôïi, ñöôïc phuïc vuï,… vaøi laàn nhö
theá môùi keát thuùc. Nhö vaäy thì vieäc ngöôøi ñieàu haønh ñöôïc quyeàn can thieäp vaøo
haøng ñôïi tuøy vaøo nhöõng tình theá cuï theå laø raát coù lôïi. Nhöõng coâng vieäc ñoâi khi do
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 287
Chöông 11 – Haøng öu tieân
tính thieáu hieäu quaû, ñaõ söû duïng toång thôøi gian phuïc vuï quaù lôùn maø vaãn chöa keát
thuùc, thöôøng bò giaûm ñoä öu tieân nhö moät hình thöùc phaït.
Tröôùc heát chuùng ta caàn boå sung moät vaøi CTDL vaø moät vaøi haøm phuï trôï sao cho
khi moät coâng vieäc ñöôïc ñöa vaøo haøng öu tieân chuùng ta luoân naém ñöôïc vò trí cuûa noù
trong haøng öu tieân, keå caû khi noù bò dòch chuyeån do caùc thao taùc cuûa caùc taùc vuï
theâm, loaïi,…Taát nhieân nhöõng boå sung naøy seõ ñöôïc ñoùng kín trong CTDL
Priority_Heap cuûa chuùng ta. Sau ñoù, chuùng ta coù theå thieát keá hai taùc vuï
decrease_key(position, delta) vaø increase_key(position, delta) cho
pheùp giaûm hoaëc taêng khoùa cuûa phaàn töû taïi vò trí position trong heap moät löôïng
delta. Khi giaûm hoaëc taêng nhö vaäy, chuùng ta chæ caàn xöû lyù dòch chuyeån phaàn töû
naøy leân hoaëc xuoáng vò trí thích hôïp trong heap so vôùi giaù trò môùi cuûa khoùa, vieäc
naøy raát deã daøng vaø gaàn gioáng vôùi nhöõng gì chuùng ta ñaõ laøm trong hai taùc vuï
priority_append vaø priority_serve.
11.4.3. Taùc vuï loaïi moät phaàn töû khoâng ôû ñaàu haøng
Chuùng ta cuõng coù theå boå sung theâm taùc vuï loaïi haún moät coâng vieäc ñang ñôïi
trong haøng (khoâng phaûi laø phaàn töû ñang ôû ñaàu haøng vaø coù ñoä öu tieân cao nhaát)
nhaèm ñaùp öùng yeâu caàu cuûa moät ngöôøi söû duïng naøo ñoù muoán ngöng khoâng thöïc
hieän coâng vieäc nöõa. Taùc vuï delete(position) ñôn giaûn laø goïi
vôùi delta voâ cuøng lôùn roài goïi
decrease_key(position, delta)
priority_serve.
11.5. Moät soá phöông aùn khaùc cuûa heap
Ñaëc tính chính yeáu cuûa heap laø traät töï giöõa caùc phaàn töû cha – con. Ñieàu
naøy ñaùp öùng muïc ñích cuûa haøng öu tieân laø truy xuaát nhanh choùng phaàn töû nhoû
nhaát. Heap nhò phaân khai thaùc tính naêng cuûa maûng lieân tuïc taïo hieäu quaû nhaát
ñònh trong caùc thao taùc treân haøng öu tieân. Döôùi ñaây laø moät vaøi phöông aùn khaùc
cuûa heap, chuùng khai thaùc caùc öu ñieåm cuûa caùc caùch hieän thöïc khaùc nhau.
11.5.1. d-heaps
Heap nhò phaân luoân phoå bieán khi ngöôøi ta caàn duøng ñeán haøng öu tieân. d-
heaps hoaøn toaøn gioáng heap nhò phaân ngoaïi tröø moãi nuùt coù d chöù khoâng phaûi 2
con. d caøng lôùn caøng lôïi cho pheùp theâm vaøo, ngöôïc laïi, trong pheùp loaïi boû phaàn töû
beù nhaát, caàn phaûi chi phí trong vieäc so saùnh d phaàn töû con cuûa moät nuùt ñeå laáy
phaàn töû nhoû nhaát ñaåy leân. Do ñoù d-heap thích hôïp vôùi caùc öùng duïng maø pheùp
theâm vaøo ñöôïc thöïc hieän thöôøng xuyeân. Ngoaøi ra coøn phaûi tính ñeán chi phí trong
vieäc ñònh vò caùc nuùt cha, nuùt con trong maûng lieân tuïc. Neáu d laø luõy thöøa cuûa 2 thì
caùc pheùp nhaân, chia ñöôïc thöïc hieän bôûi pheùp dòch chuyeån bit raát tieän lôïi. Cuoái
cuøng, töông töï B-tree, khi döõ lieäu quaù lôùn khoâng chöùa ñuû trong boä nhôù thì
d-heap cuõng thích hôïp vôùi vieäc söû duïng theâm boä nhôù ngoaøi.
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 288
Chöông 11 – Haøng öu tieân
1
3 5
2
13 15 6 8 17 9
4 7 10
11 9
Hình 11.3 . d-heap
Nhöôïc ñieåm cuûa caùc heap treân ñaây laø vieäc tìm kieám moät phaàn töû baát kyø hay
vieäc troän hai heap vôùi nhau khoâng thích hôïp. Chuùng ta seõ xem xeùt moät soá caáu
truùc phöùc taïp hôn nhöng raát thích hôïp cho pheùp troän.
11.5.2. Heap leäch traùi (Leftist heap)
Vieäc söû duïng maûng lieân tuïc nhö heap nhò phaân thaät khoâng deã ñeå thöïc hieän
pheùp troän moät caùch hieäu quaû, vì noù luoân ñoøi hoûi vieäc di chuyeån caùc phaàn töû. Moïi
CTDL thích hôïp cho vieäc troän ñeàu duøng ñeán con troû. Nhöôïc ñieåm cuûa con troû laø
thôøi gian xaùc ñinh vò trí caùc phaàn töû laâu hôn so vôùi trong maûng lieân tuïc. Heap
leäch traùi seõ söû duïng caáu truùc lieân keát vôùi caùc con troû traùi vaø phaûi taïi moãi nuùt ñeå
chöùa ñòa chæ cuûa hai nuùt con, muïc ñích ñeå khai thaùc ñieåm maïnh cuûa pheùp troän.
Heap leäch traùi cuõng gioáng vôùi heap nhò phaân ôû caáu truùc nhò phaân vaø traät töï
giöõa caùc phaàn töû cha – con. Chuùng ta luoân nhôù raèng, traät töï giöõa caùc phaàn töû cha
– con laø tính chaát cô baûn nhaát cuûa moïi heap. Ñieåm khaùc ôû ñaây laø heap leäch traùi
khoâng coù söï caân baèng.
Chuùng ta ñònh nghóa chieàu daøi ñöôøng ñi ñeán NULL cuûa moät phaàn töû X (null
path length – Npl(X)) laø chieàu daøi cuûa ñöôøng ñi ngaén nhaát töø X ñeán moät nuùt laù.
Npl cuûa nuùt laù vaø nuùt baäc moät baèng 0, Npl(NULL) = -1. Npl cuûa baát kyø nuùt naøo
baèng Npl cuûa nuùt con coù Npl nhoû nhaát coäng theâm 1.
Heap leäch traùi coù tính chaát sau ñaây: taïi moïi nuùt, Npl cuûa nuùt con traùi
luoân lôùn hôn hoaëc baèng Npl cuûa nuùt con phaûi. Tính chaát naøy laøm cho heap
leäch traùi maát caân baèng. Chuùng ta goïi ñöôøng ñi traùi (hoaëc phaûi) taïi moãi nuùt laø
ñöôøng ñi ñeán nuùt döôùi cöïc traùi (cöïc phaûi) töông öùng cuûa nuùt ñoù. Moïi nuùt trong
heap leäch traùi luoân coù khuynh höôùng coù ñöôøng ñi traùi daøi hôn ñöôøng ñi phaûi, do
ñoù ñöôøng ñi phaûi taïi nuùt goác luoân laø ñöôøng ngaén nhaát trong caùc ñöôøng ñi töø goác
ñeán caùc nuùt laù.
Coù theå chöùng minh baèng suy dieãn raèng moät caây heap leäch traùi vôùi r nuùt treân
ñöôøng ñi phaûi seõ coù ít nhaát 2r-1 nuùt. Töø ñoù caây heap leäch traùi N nuùt seõ coù nhieàu
nhaát ⎣log(N+1)⎦ nuùt treân ñöôøng ñi phaûi. YÙ töôûng chính cuûa heap leäch traùi laø
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 289
Chöông 11 – Haøng öu tieân
moïi taùc vuï ñeàu ñöôïc thöïc hieän treân ñöôøng ñi phaûi ñeå luoân ñöôïc baûo ñaûm vôùi chi
phí log(N).
1
1
0
1*
0
1
1
0
0
0
0
0
0
(a) (b)
Hình11.4. Npl taïi moãi nuùt.
(a)- Thoaû ñieàu kieän heap leäch traùi.
(b)- Nuùt coù daáu * vi phaïm ñieàu kieän heap leäch traùi..
Caùc taùc vuï treân heap leäch traùi
Taùc vuï cô baûn nhaát cuûa heap leäch traùi laø taùc vuï troän. Chuùng ta seõ thaáy pheùp
theâm vaøo vaø pheùp loaïi boû ñöôïc thöïc hieän deã daøng nhôø goïi pheùp troän naøy.
Ngoaøi hai con troû traùi vaø phaûi, moãi nuùt trong heap leäch traùi coøn coù theâm thoâng
tin laø Npl cuûa noù.
Ñeå troän hai heap leäch traùi H1 vaø H2:
• Neáu moät trong hai heap roãng thì traû veà heap coøn laïi.
• Ngöôïc laïi, so saùnh döõ lieäu taïi hai nuùt goác, thöïc hieän troän heap coù goác lôùn
hôn vôùi caây con phaûi cuûa heap coù goác nhoû hôn. Ñieàu naøy baûo ñaûm goác cuûa
heap keát quaû luoân coù trò nhoû nhaát trong taát caû caùc nuùt, vì heap keát quaû coù
goác chính laø goác cuûa heap ban ñaàu coù goác nhoû hôn.
Ñaây chính laø quaù trình ñeä quy. Tröôùc khi keát thuùc moät laàn goïi ñeä quy, chuùng
ta chæ caàn kieåm tra nuùt goác naøy coù thoûa ñieàu kieän cuûa heap leäch traùi hay khoâng,
neáu caàn chuùng ta chæ caàn hoaùn vò hai con traùi vaø phaûi cuûa noù ñeå coù ñöôïc Npl cuûa
nuùt con traùi lôùn hôn hoaëc baèng Npl cuûa nuùt con phaûi. Npl cuûa nuùt goác ñöôïc caäp
nhaät baèng Npl cuûa nuùt con phaûi coäng theâm 1.
Hình 11.5 minh hoïa quaù trình troän hai heap leäch traùi H1 vaø H2.
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 290
Chöông 11 – Haøng öu tieân
6
3
7
12
8
10
37 18
24
18
17
14
21
33
26
23
H1 H2
(a)- Do 6>3, troän H2 vôùi caây con goác 8.
3
6
8
10
7
17 12
14
21
37 18
26 24
18
23
33
(b)- Do8>6, troän caây con goác 8 vôùi caây con goác 7.
3
6
8
10
7
12
14 17
21
37 18
18
26 24
23
33
(c)-Do 8>7, troän caây con goác 8 vôùi caây con goác 18.
3
6
10
12 7
14
21
37
23 24 8
18
18
17
33
26
(d)- Do 18>8, troän caây con goác 18 vôùi caây con phaûi cuûa 8 (NULL)
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 291
Chöông 11 – Haøng öu tieân
3
6
10
12 7
14
21
37
23 24 8
18
18
17
33
(e)- Taïi nuùt 18 vaø nuùt 8 khoâng vi phaïm heap leäch traùi. 26
3
6
10
12 7
14
21
37
23 24 8
18
18
17
33
26
(f)- Taïi nuùt 7 vi phaïm heap leäch traùi, hoaùn vò hai caây con.
3
6
10
12 7
14
21
37
23 8
24
18
18
17
33
26
(g)- Taïi nuùt 6 khoâng vi phaïm heap leäch traùi.
3
6 10
12 7 14
21
37 23
8
24
18
18
17
33
26
(h)- Taïi nuùt 3 vi phaïm heap leäch traùi, hoaùn vò hai caây con.
Hình 11.5- Troän hai heap leäch traùi H1 vaø H2
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 292
Chöông 11 – Haøng öu tieân
//Phaàn maõ giaû cho khai baùo vaø moät soá taùc vuï cho LeftistHeap.
struct LeftistHeap_Node
DataType data
LeftistHeap_Node* left
LeftistHeap_Node* right
int Npl
end struct
class Leftist_Heap
public:
void merge(ref Leftist_Heap H1, ref Leftist_Heap H2)
private:
LeftistHeap_Node* recursive_merge(ref LeftistHeap_Node* p1,
ref LeftistHeap_Node* p2)
LeftistHeap_Node* aux_merge(ref LeftistHeap_Node* p1,
ref LeftistHeap_Node* p2)
LeftistHeap_Node* root
end class
void Leftist_Heap::merge(ref Leftist_Heap H1, ref Leftist_Heap H2)
/*
post: H1 laø heap leäch traùi laø keát quaû troän hai heap H1 vaø H2, H2 roãng.
*/
{
1. recursive_merge(H1.root, H2.root);
}
LeftistHeap_Node* Leftist_Heap::recursive_merge(ref LeftistHeap_Node* p1,
ref LeftistHeap_Node* p2)
/*
pre: p1 vaø p2 laø ñóa chæ nuùt goác cuûa hai heap leäch traùi.
post: Traû veà ñòa chæ nuùt goác cuûa heap leäch traùi laø keát quaû troän hai heap ban ñaàu, p1 vaø p2 laø
NULL.
uses: Söû duïng haøm aux_merge.
*/
{
LeftistHeap_Node* p;
1. if (p1 == NULL)
1. p = p2;
2. if (p2 = NULL)
1. p = p1;
3. if (p1->data < p2->data)
1. p = aux_merge(p1, p2);
4. else
1. p = aux_merge(p2, p1);
5. p1 = NULL;
6. p2 = NULL;
7. return p;
}
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 293
Chöông 11 – Haøng öu tieân
LeftistHeap_Node* Leftist_Heap::aux_merge(ref LeftistHeap_Node* p1,
ref LeftistHeap_Node* p2)
/*
pre: p1 vaø p2 laø ñòa chæ nuùt goác cuûa hai heap leäch traùi.
post: Heap p2 ñöôïc troän vôùi caây con phaûi cuûa heap p1, p2 gaùn veà NULL.
uses: Söû duïng haøm SwapChildren vaø recursive_merge.
*/
{
1. if (p1->left == NULL) // Tröôøng hôïp naøy p1_>right ñaõ laø NULL do ñieàu kieän
// cuûa heap leäch traùi.
1. p1->left = p2;
2. else
1. p1->right = recursive_merge(p1->right, p2);
2. if(p1->left->Npl < p1->right->Npl)
1. SwapChildren(p1); // Traùo 2 caây con cuûa p1.
3. p1->Npl = p1->right->Npl + 1;
3. return p1; // p2 ñaõ ñöôïc gaùn NULL trong recursive_merge.
}
Thôøi gian troän hai heap leäch traùi tæ leä vôùi chieàu daøi cuûa ñöôøng ñi phaûi, vaø ñoù
laø O(logN). Giaûi thuaät ñeä quy treân coù theå ñöôïc khöû ñeä quy nhö sau. Böôùc thöù
nhaát thöïc hieän troän ñöôøng ñi phaûi cuûa hai heap, ñöôøng ñi phaûi cuûa heap keát quaû
chính laø thöù töï taêng daàn cuûa caùc nuùt treân ñöôøng ñi phaûi cuûa hai heap ban ñaàu (3,
6, 7, 8, 18). Keát quaû cho thaáy ôû hình 11.6. Böôùc thöù hai ñi laàn ngöôïc treân ñöôøng ñi
phaûi cuûa caây keát quaû ñeå hoaùn vò caùc con traùi vaø con phaûi khi caàn thieát. Tröôøng
hôïp chuùng ta vieäc hoaùn vò caàn thöïc hieän taïi nuùt 7 vaø nuùt 3.
3
6
10
12 7
14
21
37
23 24 8
18
18
17
33
26
Hình 11.6. Keát quaû sau böôùc thöù nhaát cuûa giaûi thuaät troän khoâng ñeä quy.
Pheùp theâm moät phaàn töû môùi chính laø pheùp troän heap leäch traùi ñaõ coù vôùi moät
heap leäch traùi chæ coù duy nhaát nuùt caàn theâm vaøo. Pheùp loaïi phaàn töû nhoû nhaát cuûa
heap leäch traùi laø pheùp laáy ñi phaàn töû taïi goác vaø troän hai caây con cuûa noù vôùi nhau.
Nhö vaäy taát caû caùc taùc vuï treân heap leäch traùi ñeàu coù chi phí O(logN).
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 294
Chöông 11 – Haøng öu tieân
11.5.3. Skew heap
Skew heap gioáng nhö heap leäch traùi nhöng khoâng chöùa thoâng tin veà Npl vaø
khoâng coù raøng buoäc gì veà chieàu daøi ñöôøng ñi phaûi. Nhö vaäy trong tröôøng hôïp xaáu
nhaát caùc taùc vuï chi phí ñeán O(N), khi caây nhò phaân suy bieán thaønh chuoãi maéc
xích N nuùt veà beân phaûi.
Taùc vuï chính cuûa skew heap cuõng laø pheùp troän, trong ñoù vieäc hoaùn vò hai
nhaùnh con luoân ñöôïc laøm. Taùc vuï naøy coù theå ñöôïc hieän thöïc ñeä quy hoaëc khoâng ñeä
quy. Keát quaû vieäc hoaùn vò taïi taát caû caùc nuùt seõ laø ñöôøng ñi traùi cuûa heap cuoái cuøng
seõ chöùa taát caû caùc nuùt treân hai ñöôøng ñi phaûi cuûa hai heap ban ñaàu theo ñuùng thöù
töï taêng daàn giuõa chuùng.
3
6 10
12
7 14
21
37 23
8 24
18
18 17 33
26
Hình 11.7. Keát quaû troän H1 vaø H2 theo caùch cuûa skew heap, hoaùn vò hai con traùi vaø phaûi taïi
moïi nuùt
Nhö vaäy tuy tröôøng hôïp xaáu nhaát cuûa skew heap laø O(log N), nhöng skew
heap coù öu ñieåm laø khoâng phaûi chi phí ñeå quaûn lyù Npl taïi moãi nuùt vaø cuõng khoâng
phaûi so saùnh Npl ñeå qyeát ñònh coù hoaùn vò hai nuùt con taïi moãi nuùt hay khoâng.
11.5.4. Haøng nhò thöùc (Binomial Queue)
Haøng nhò thöùc laø moät phöông aùn hieän thöïc cuûa haøng öu tieân. Heap leäch traùi vaø
skew heap thöïc hieän O(log N) moãi taùc vuï ñoái vôùi vieäc troän, theâm vaø loaïi phaàn
töû nhoû nhaát. Heap nhò phaân thöïc hieän moãi taùc vuï theâm vaøo vôùi thôøi gian trung
bình laø haèng soá. Haøng nhò thöùc trong tröôøng hôïp xaáu nhaát thöïc hieän O(logN)
cho moãi taùc vuï, nhöng vieäc theâm vaøo cuõng coù thôøi gian trung bình laø haèng soá.
Khaùc vôùi moïi hieän thöïc cuûa haøng öu tieân maø chuùng ta ñaõ xem xeùt, haøng nhò
thöùc khoâng phaûi laø moät caây coù traät töï cuûa heap, maø laø moät röøng caùc caây coù traät töï
cuûa heap, trong ñoù khoâng ñöôïc pheùp coù hai caây coù cuøng chieàu cao. Theo quy öôùc,
caây coù chieàu cao 0 laø caây coù 1 nuùt; caây coù chieàu cao k coù ñöôïc baèng caùch noái moät
caây chieàu cao k-1 vaøo nuùt goác cuûa moät caây chieàu cao k-1 khaùc. Hình 11.8 bieåu dieãn
caùc caây coù chieàu cao laàn löôït laø 0, 1, 2, 3, 4. Töø hình veõ chuùng ta thaáy, caây Bk bao
goàm moät nuùt goác vaø caùc caây con B0, B1,…, Bk-1. Caây Bk coù chính xaùc laø 2k nuùt, do ñoù
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 295
Chöông 11 – Haøng öu tieân
töø ñaây chuùng ta seõ goïi caùc caây naøy laø caây nhò thöùc. Soá nuùt ôû möùc d trong caây nhò
thöùc laø Cdk. Neáu moïi caây nhò thöùc trong haøng nhò thöùc ñeàu coù traät töï cuûa heap vaø
khoâng cho pheùp coù nhieàu hôn moät caây nhò thöùc coù cuøng chieàu cao thì haøng öu tieân
vôùi kích thöôùc baát kyø ñeàu coù theå ñöôïc bieåu dieãn bôûi moät haøng nhò thöùc nhö theá
naøy. Chaúng haïn haøng öu tieân coù 13 nuùt seõ goàm caùc caây nhò thöùc B3, B2, vaø B0.
Bieåu dieãn nhò phaân cuûa 13 chính laø 1101, ñieàu naøy hoaøn toaøn töông öùng vôùi söï coù
maët cuûa B3, B2, vaø B0, maø khoâng coù maët cuûa B1.
B0 B1 B2 B3
B4
Hình 11.8- Hình daïng caùc caây nhò thöùc vôùi caùc chieàu cao 0, 1, 2, 3, vaø 4 ñöôïc quy ñònh trong
haøng nhò thöùc.
Hình 11.9 bieåu dieãn moät haøng nhò thöùc coù 6 nuùt.
16 12
18 21 24
65
Hình 11.9- Haøng nhò thöùc coù 6 nuùt.
Phaàn töû nhoû nhaát trong haøng nhò thöùc chính laø moät trong caùc nuùt goác cuûa caùc
caây nhò thöùc coù trong haøng. Do haøng nhò thöùc coù nhieàu nhaát laø log N caây nhò thöùc
khaùc nhau, vieäc tìm kieám chi phí O(log N). Neáu chuùng ta ñaùnh daáu phaàn töû nhoû
nhaát moãi khi coù söï thay ñoåi bôûi moät taùc vuï naøo thì chi phí naøy laø O(1).
Pheùp troän trong haøng nhò thöùc raát deã daøng. Giaû söû chuùng ta caàn troän hai haøng
nhò thöùc H1 vaø H2 trong hình 11.10. H3 laø haøng nhò thöùc keát quaû. Trong H1 vaø H2
chæ coù moät caây nhò thöùc B0, vaäy B0 seõ laø moät thaønh phaàn cuûa H3. Chuùng ta keát
hôïp hai caây nhò thöùc B1 trong H1 vaø H2 baèng caùch cho caây nhò thöùc coù goác lôùn hôn
laøm caây con cuûa caây nhò thöùc coøn laïi. Vôùi caây nhò thöùc B2 vöøa coù ñöôïc vaø hai caây
nhò thöùc B2 ban ñaàu trong H1 vaø H2, chuùng ta ñeå laïi moät caây trong H3, vaø keát hôïp
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 296
Chöông 11 – Haøng öu tieân
hai caây B2 coøn laïi thaønh moät caây B3. Vì H3 chöa coù caây nhò thöùc B3 neân B3 cuoái
cuøng naøy seõ laø thaønh phaàn cuûa H3.
14 23
16 12 13
26 51 24
18 21 24
65
65
H1 H2
Hình 11.10- Hai haøng nhò thöùc H1 vaø H2.
14
26 16
18
Hình 11.11 - Keát hôïp hai caây nhò thöùc B1 trong H1 vaø H2.
12
23
13
14
21 24
51 24
26 16
65
65
18
Hình 11.12- Keát quaû troän H1 vaø H2 thaønh H3.
Vieäc keát hôïp hai caây nhò thöùc toán O(1), vôùi O(log N) caây nhò thöùc trong moãi
haøng nhò thöùc, vieäc troän hai haøng nhò thöùc cuõng toán O(log N) trong tröôøng hôïp
xaáu nhaát. Ñeå taêng tính hieäu quaû, chuùng ta löu caùc caây nhò thöùc trong moãi haøng
nhò thöùc theo thöù töï taêng daàn cuûa chieàu cao caùc caây.
Vieäc theâm moät phaàn töû môùi vaøo haøng nhò thöùc töông töï nhö ñoái vôùi heap leäch
traùi: troän haøng nhò thöùc coù duy nhaát phaàn töû caàn theâm vôùi haøng nhò thöùc ñaõ coù.
Vieäc loaïi phaàn töû nhoû nhaát cuõng ñôn giaûn: tìm phaàn töû nhoû nhaát trong soá caùc
nuùt goác cuûa caùc caây nhò thöùc. Giaû söû ñoù laø caây Bk. Sau khi loaïi boû nuùt goác cuûa caây
Bk, chuùng ta coøn laïi caùc caây con cuûa noù: B0, B1,… Bk-1. Goïi röøng goàm caùc caây con
naøy laø H’, vaø H’’ laø haøng nhò thöùc ban ñaàu khoâng keå BK. Vieäc cuoái cuøng caàn laøm laø
troän H’ vaø H’’. Chuùng ta coù theå töï kieåm tra raèng caùc pheùp theâm vaø loaïi naøy ñeàu
toán O(log N) trong tröôøng hôïp xaáu nhaát.
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 297
Chöông 11 – Haøng öu tieân
1
1
1 2
2
1
1 3 3
2
2
1 1
3 1
4 3
2 3
2 2
4
4
1
1 5 5
2 3
2 3
4
4
1
1 6 5
5
2 3
2 3 6
4
4
1 1
5 5
7 7
2 3 2 3
6 6
4 4
Hình 11.13- Quaù trình theâm caùc phaàn töû 1, 2,…, 7 vaøo haøng nhò thöùc.
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 298
Chöông 11 – Haøng öu tieân
12
23
13
14
21 24
51 24
26 16
65
65
18
H
23 14
21 24
13
51 24 26 16
65
65 18
H’’ H’
13
23
14
21 24
51 24
26 16
65
65
18
Hình 11.14- Quaù trình loaïi phaàn töû nhoû nhaát trong haøng nhò thöùc H.
Hieän thöïc cuûa haøng nhò thöùc
Vieäc tìm phaàn töû nhoû nhaát caàn duyeät qua caùc goác cuûa caùc caây nhò thöùc trong
haøng nhò thöùc (12, 23 vaø 13 trong hình 11.14). Chuùng ta coù theå duøng danh saùch
lieân keát ñeå chöùa caùc nuùt goác naøy. Danh saùch seõ coù thöù töï theo chieàu cao cuûa caùc
caây nhò thöùc ñeå phuïc vuï cho pheùp troän hai haøng nhò thöùc ñöôïc deã daøng.
Töông töï, caùc nuùt con cuûa nuùt goác cuûa moät caây nhò thöùc cuõng ñöôïc chöùa trong
moät danh saùch lieân keát (14, 24 vaø 21 trong hình 11.14), ñeå khi loaïi boû nuùt goác
(nuùt 12) thì phaàn coøn laïi cuõng coù caáu truùc töông töï nhö moät haøng nhò thöùc môùi,
raát thuaän lôïi trong pheùp loaïi phaàn töû nhoû nhaát trong haøng nhò thöùc.
12
23
13
14
21 24
51 24
26 16
65
65
18
Hình 11.15- Haøng nhò thöùc H
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 299
Chöông 11 – Haøng öu tieân
12 23 13
14 24 51
21 24
65
16 26 65
18
Hình 11.16- Hieän thöïc lieân keát cuûa haøng nhò thöùc H.
Trong hình veõ treân chuùng ta thaáy hình elipse neùt rôøi bieåu dieãn caùc danh saùch
lieân keát caùc nuùt maø chuùng ta thöôøng phaûi duyeät qua. Hình elipse neùt rôøi lôùn chöùa
caùc goác cuûa caùc caây nhò thöùc trong haøng nhò thöùc, khi caàn tìm phaàn töû nhoû nhaát
trong haøng nhò thöùc chuùng ta tìm trong danh saùch naøy. Hình elipse neùt rôøi nhoû
chöùa caùc nuùt con cuûa nuùt goác trong moät caây nhò thöùc.
Trong quaù trình hình thaønh haøng nhò thöùc trong moät soá thao taùc döõ lieäu, khi
keát hôïp hai caây nhò thöùc coù cuøng chieàu cao (hình 11.18), chuùng ta caàn noái moät
trong hai caây thaønh caây con cuûa caây coøn laïi, maø caây con môùi naøy cuõng chính laø
caây con coù chieàu cao lôùn nhaát so vôùi caùc caây con ñaõ coù. Vieäc cheøn caây con môùi vaøo
ñaàu cuûa danh saùch lieân keát seõ thuaän tieän hôn, vì vaäy chuùng ta cho danh saùch naøy
coù thöù töï giaûm daàn theo chieàu cao cuûa caùc caây con (hình 11.18).
Ngoaøi ra, moãi nuùt trong caây nhò thöùc seõ coù moät con troû cho pheùp truy xuaát ñeán
danh saùch caùc con cuûa noù. Toùm laïi, hieän thöïc ñôn giaûn vaø hieäu quaû cho haøng nhò
thöùc thaät ñôn giaûn nhö hình 11.18, ñoù laø caáu truùc cuûa moät caây nhò phaân, moãi nuùt
coù con troû traùi chæ ñeán nuùt con ñaàu tieân cuûa noù vaø con troû phaûi chæ ñeán nuùt anh
em cuûa noù.
12 23 13
14 24 51
21 24
65
16 26 65
18
Hình 11.17- Goác caùc caây nhò thöùc ñöôïc chöùa trong maûng lieân tuïc.
Hình 11.17 laø moät phöông aùn thay danh saùch lieân keát treân cuøng bôûi maûng lieân
tuïc. Chuùng ta coù theå duøng maûng lieân tuïc caáp phaùt ñoäng ñeå khaéc phuïc nhöôïc ñieåm
do khoâng bieát tröôùc chieàu cao cuûa caây nhò thöùc cao nhaát trong haøng nhò thöùc. Vieäc
duøng maûng lieân tuïc cho pheùp tìm nhò phaân phaàn töû nhoû nhaát, tuy nhieân seõ laø
laõng phí lôùn khi haøng nhò thöùc goàm quaù ít caây nhò thöùc vôùi nhieàu chieàu cao khaùc
nhau.
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 300
Chöông 11 – Haøng öu tieân
12 12
14 14
24 21 24 21
65 16 26 16 26 65
18 18
Hình 11.18- Keát hôïp hai caây nhò thöùc B2 thaønh moät caây nhò thöùc B3.
Döôùi ñaây laø phaàn maõ giaû cho caùc khai baùo caáu truùc cuûa caây nhò thöùc vaø haøng
nhò thöùc. Caùc taùc vuï keát hôïp hai caây nhò thöùc, troän hai haøng nhò thöùc, vaø loaïi
phaàn töû nhoû nhaát trong haøng nhò thöùc cuõng ñöôïc trình baøy baèng maõ giaû.
//Phaàn maõ giaû cho khai baùo vaø moät soá taùc vuï cho haøng nhò thöùc.
struct Binomial_Node
DataType data
Binomial_Node* leftChild
Binomial_Node* nextSibling
end struct
struct Binomial_Tree
Binomial_Tree combineTrees(ref Binomial_Tree T1, ref Binomial_Tree T2)
Binomial_Node* root
int notEmpty() // Traû veà 1 neáu caây khoâng roãng, ngöôïc laïi traû veà 0.
end struct
class Binomial_Queue
public:
Binomial_Queue(Binomial_Node* p, int k)// k laø soá nuùt trong haøng nhò thöùc.
int empty
Binomial_Queue merge(ref Binomial_Queue H1, ref Binomial_Queue H2)
protected:
int count // Toång soá nuùt trong taát caû caùc caây nhò thöùc.
Binomial_Tree Trees[MAX]
end class
Binomial_Tree Binomial_Tree::CombineTrees(ref Binomial_Tree T1,
ref Binomial_Tree T2);
/*
pre: T1 vaø T2 khaùc roãng.
post: T1 chöùa keát quaû keát hôïp hai caây T1 vaø T2, T2 roãng. Traû veà caây T1.
*/
{
1. if (T1.root->data > T2.root->data)
1. Traùo T1 vaø T2 cho nhau
2. T2.root->nextSibling = T1.root->leftChild // Cheøn caây T2 vaøo ñaàu danh
// saùch caùc caây con cuûa goác cuûa T1
3. T1.root->leftChild = T2.root // Caäp nhaät nuùt con traùi cho nuùt goác cuûa T1
4. T2.root = NULL
5. return T1
}
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 301
Chöông 11 – Haøng öu tieân
•
Binomial_Queue Binomial_Queue::merge(ref Binomial_Queue H1,
• ref Binomial_Queue H2)
/*
•
post: H1 chöùa keát quaû troän hai haøng nhò thöùc H1 vaø H2, H2 roãng. Traû veà haøng H1.
•
uses: haøm Binomial_Tree::notEmpty() traû veà 1 neáu caây khoâng roãng, ngöôïc laïi traû veà 0.
*/•
{•
Binomial_Tree T1, T2, carry
• int i = 0
• 1. H1.count = H1.count + H2.count
• 2. loop (H2 chöa roãng hoaëc carry khoâng roãng)
1. T1 = H1.Trees[i]
• 2. T2 = H2.Trees[i]
• 3. case (T1.notEmpty() + 2*T2.notEmpty() + 4*carry.notEmpty())
1. case 0: // Khoâng coù caây naøo
•
2. case 1: // Chæ coù caây T1
• 1. break
• 3. case 2: // Chæ coù caây T2
• 1. H1.Trees[i] = T2
2. H2.Trees[i].root = NULL
• 3. break
• 4. case 4: // Chæ coù caây carry
• 1. H1.Trees[i] = carry
2. carry.root = NULL
• 3. break
• 5. case 3: // Coù caây T1 vaø T2
• 1. carry = combineTrees(T1, T2)
2. H1.Trees[i].root = NULL
• 3. H2.Trees[i].root = NULL
• 4. break
6. case 5: // Coù caây T1 vaø carry
•
1. carry = combineTrees(T1, carry)
• 2. H1.Trees[i].root = NULL
• 3. break
7. case 6:// Coù caây T2 vaø carry
•
1. carry = combineTrees(T2, carry)
• 2. H2.Trees[i].root = NULL
• 3. break
8. case 7:// Coù caû 3 caây T1, T2, vaø carry
• 1. H1.Trees[i] = carry
• 2. carry = combineTrees(T1, T2)
• 3. H2.Trees[i].root = NULL
4. break
• 4. endcase
• 5. i = i + 1
3. endloop
4. return H1
}
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 302
