Giáo trình Cấu trúc dữ liệu và giải thuật - Phần 2: Các cấu trúc dữ liệu - Chương 9: Cây nhị phân
Chöông 9 – Caây nhò phaân
Chöông 9 – CAÂY NHÒ PHAÂN
So vôùi hieän thöïc lieân tuïc cuûa caùc caáu truùc döõ lieäu, caùc danh saùch lieân keát coù
nhöõng öu ñieåm lôùn veà tính meàm deûo. Nhöng chuùng cuõng coù moät ñieåm yeáu, ñoù laø söï
tuaàn töï, chuùng ñöôïc toå chöùc theo caùch maø vieäc di chuyeån treân chuùng chæ coù theå
qua töøng phaàn töû moät. Trong chöông naøy chuùng ta khaéc phuïc nhöôïc ñieåm naøy
baèng caùch söû duïng caùc caáu truùc döõ lieäu caây chöùa con troû. Caây ñöôïc duøng trong raát
nhieàu öùng duïng, ñaëc bieät trong vieäc truy xuaát döõ lieäu.
9.1. Caùc khaùi nieäm cô baûn veà caây
Moät caây (tree) - hình 9.1- goàm moät taäp höõu haïn caùc nuùt (node) vaø moät taäp höõu
haïn caùc caønh (branch) noái giöõa caùc nuùt. Caønh ñi vaøo nuùt goïi laø caønh vaøo
(indegree), caønh ñi ra khoûi nuùt goïi laø caønh ra (outdegree). Soá caønh ra töø moät nuùt
goïi laø baäc (degree) cuûa nuùt ñoù. Neáu caây khoâng roãng thì phaûi coù moät nuùt goïi laø nuùt
goác (root), nuùt naøy khoâng coù caønh vaøo. Caây trong hình 9.1 coù M laø nuùt goác.
Caùc nuùt coøn laïi, moãi nuùt phaûi coù chính xaùc moät caønh vaøo. Taát caû caùc nuùt ñeàu coù
theå coù 0, 1, hoaëc nhieàu hôn soá caønh ra.
M
A
O
D
C
N
Y
S
E
L
B
T
X
(a)
M
-
-
-
-
A
-
-
N
C
-
-
B
M ( A ( N C ( B ) ) D O ( Y ( T X ) E L S ) )
(c)
-
D
-
-
-
-
-
-
-
O
-
-
-
-
-
-
(b)
Y
-
-
E
L
S
T
X
Hình 9.1 – Caùc caùch bieåu dieãn cuûa caây
Giaùo trình Caáu truùc Döõ lieäu vaø Giaûi thuaät
183
Chöông 9 – Caây nhò phaân
Nuùt laù (leaf) ñöôïc ñònh nghóa nhö laø nuùt cuûa caây maø soá caønh ra baèng 0. Caùc
nuùt khoâng phaûi nuùt goác hoaëc nuùt laù thì ñöôïc goïi laø nuùt trung gian hay nuùt
trong (internal node). Nuùt coù soá caønh ra khaùc 0 coù theå goïi laø nuùt cha (parent)
cuûa caùc nuùt maø caønh ra cuûa noù ñi vaøo, caùc nuùt naøy cuõng ñöôïc goïi laø caùc nuùt con
(child) cuûa noù. Caùc nuùt cuøng cha ñöôïc goïi laø caùc nuùt anh em (sibling) vôùi nhau.
Nuùt treân nuùt cha coù theå goïi laø nuùt oâng (grandparent, trong moät soá baøi toaùn
chuùng ta cuõng caàn goïi teân nhö vaäy ñeå trình baøy giaûi thuaät).
Theo hình 9.1, caùc nuùt laù goàm: N, B, D, T, X, E, L, S; caùc nuùt trung gian goàm:
A, C, O, Y. Nuùt Y laø cha cuûa hai nuùt T vaø X. T vaø X laø con cuûa Y, vaø laø nuùt anh
em vôùi nhau.
Ñöôøng ñi (path) töø nuùt n1 ñeán nuùt nk ñöôïc ñònh nghóa laø moät daõy caùc nuùt n1,
n2, …, nk sao cho ni laø nuùt cha cuûa nuùt ni+1 vôùi 1≤ i< k. Chieàu daøi (length) ñöôøng
ñi naøy laø soá caønh treân noù, ñoù laø k-1. Moãi nuùt coù ñöôøng ñi chieàu daøi baèng 0 ñeán
chính noù. Trong moät caây, töø nuùt goác ñeán moãi nuùt coøn laïi chæ coù duy nhaát moät
ñöôøng ñi.
Ñoái vôùi moãi nuùt ni, ñoä saâu (depth) hay coøn goïi laø möùc (level) cuûa noù chính laø
chieàu daøi ñöôøng ñi duy nhaát töø nuùt goác ñeán noù coäng 1. Nuùt goác coù möùc baèng 1.
Chieàu cao (height) cuûa nuùt ni laø chieàu daøi cuûa ñöôøng ñi daøi nhaát töø noù ñeán moät
nuùt laù. Moïi nuùt laù coù chieàu cao baèng 1. Chieàu cao cuûa caây baèng chieàu cao cuûa
nuùt goác. Ñoä saâu cuûa caây baèng ñoä saâu cuûa nuùt laù saâu nhaát, noù luoân baèng chieàu cao
cuûa caây.
Neáu giöõa nuùt n1 vaø nuùt n2 coù moät ñöôøng ñi, thì n1 ñöôc goïi laø nuùt tröôùc
(ancestor) cuûa n2 vaø n2 laø nuùt sau (descendant) cuûa n1.
M laø nuùt tröôùc cuûa nuùt B. M laø nuùt goác, coù möùc laø 1. Ñöôøng ñi töø M ñeán B laø:
M, A, C, B, coù chieàu daøi laø 3. B coù möùc laø 4.
B laø nuùt laù, coù chieàu cao laø 1. Chieàu cao cuûa C laø 2, cuûa A laø 3, vaø cuûa M laø 4
chính baèng chieàu cao cuûa caây.
Moät caây coù theå ñöôïc chia thaønh nhieàu caây con (subtree). Moät caây con laø baát kyø
moät caáu truùc caây beân döôùi cuûa nuùt goác. Nuùt ñaàu tieân cuûa caây con laø nuùt goác cuûa noù
vaø ñoâi khi ngöôøi ta duøng teân cuûa nuùt naøy ñeå goïi cho caây con. Caây con goác A (hay
goïi taét laø caây con A) goàm caùc nuùt A, N, C, B. Moät caây con cuõng coù theå chia thaønh
nhieàu caây con khaùc. Khaùi nieäm caây con daãn ñeán ñònh nghóa ñeä quy cho caây nhö
sau:
Giaùo trình Caáu truùc Döõ lieäu vaø Giaûi thuaät
184
Chöông 9 – Caây nhò phaân
Ñònh nghóa: Moät caây laø taäp caùc nuùt maø
- laø taäp roãng, hoaëc
- coù moät nuùt goïi laø nuùt goác coù khoâng hoaëc nhieàu caây con, caùc caây con cuõng laø caây
Caùc caùch bieåu dieãn caây
Thoâng thöôøng coù 3 caùch bieåu dieãn caây: bieåu dieãn baèng ñoà thò – hình 9.1a, bieåu
dieãn baèng caùch canh leà – hình 9.1b, vaø bieåu dieãn baèng bieåu thöùc coù daáu ngoaëc –
hình 9.1c.
9.2. Caây nhò phaân
9.2.1.Caùc ñònh nghóa
Ñònh nghóa: Moät caây nhò phaân hoaëc laø moät caây roãng, hoaëc bao goàm moät nuùt goïi laø
nuùt goác (root) vaø hai caây nhò phaân ñöôïc goïi laø caây con beân traùi vaø caây con beân
phaûi cuûa nuùt goác.
Löu yù raèng ñònh nghóa naøy laø ñònh nghóa toaùn hoïc cho moät caáu truùc caây. Ñeå
ñaëc taû caây nhò phaân nhö moät kieåu döõ lieäu tröøu töôïng, chuùng ta caàn chæ ra caùc taùc
vuï coù theå thöïc hieän treân caây nhò phaân. Caùc phöông thöùc cô baûn cuûa moät caây nhò
phaân toång quaùt chuùng ta baøn ñeán coù theå laø taïo caây, giaûi phoùng caây, kieåm tra caây
roãng, duyeät caây,…
Ñònh nghóa naøy khoâng quan taâm ñeán caùch hieän thöïc cuûa caây nhò phaân trong boä
nhôù. Chuùng ta seõ thaáy ngay raèng moät bieåu dieãn lieân keát laø töï nhieân vaø deã söû
duïng, nhöng caùc hieän thöïc khaùc nhö maûng lieân tuïc cuõng coù theå thích hôïp. Ñònh
nghóa naøy cuõng khoâng quan taâm ñeán caùc khoùa hoaëc caùch maø chuùng ñöôïc saép thöù
töï. Caây nhò phaân ñöôïc duøng cho nhieàu muïc ñích khaùc hôn laø chæ coù tìm kieám truy
xuaát, do ñoù chuùng ta caàn giöõ moät ñònh nghóa toång quaùt.
Tröôùc khi xem xeùt xa hôn veà caùc ñaëc tính chung cuûa caây nhò phaân, chuùng ta
haõy quay veà ñònh nghóa toång quaùt vaø nhìn xem baûn chaát ñeä quy cuûa noù theå hieän
nhö theá naøo trong caáu truùc cuûa moät caây nhò phaân nhoû.
Tröôøng hôïp thöù nhaát, moät tröôøng hôïp cô baûn khoâng lieân quan ñeán ñeä quy, ñoù
laø moät caây nhò phaân roãng.
Caùch duy nhaát ñeå xaây döïng moät caây nhò phaân coù moät nuùt laø cho nuùt ñoù laø goác
vaø cho hai caây con traùi vaø phaûi laø hai caây roãng.
Vôùi caây coù hai nuùt, moät trong hai seõ laø goác vaø nuùt coøn laïi seõ thuoäc caây con.
Hoaëc caây con traùi hoaëc caây con phaûi laø caây roãng, vaø caây coøn laïi chöùa chính xaùc chæ
Giaùo trình Caáu truùc Döõ lieäu vaø Giaûi thuaät
185
Chöông 9 – Caây nhò phaân
moät nuùt. Nhö vaäy coù hai caây nhò phaân khaùc nhau coù hai nuùt. Hai caây nhò phaân coù
hai nuùt coù theå ñöôïc veõ nhö sau:
vaø
vaø ñaây laø hai caây khaùc nhau. Chuùng ta seõ khoâng bao giôø veõ baát kyø moät phaàn naøo
cuûa moät caây nhò phaân nhö sau:
do chuùng ta seõ khoâng theå noùi ñöôïc nuùt beân döôùi laø con traùi hay con phaûi cuûa nuùt
treân.
Ñoái vôùi tröôøng hôïp caây nhò phaân coù ba nuùt, moät trong chuùng seõ laø goác, vaø hai
nuùt coøn laïi coù theå ñöôïc chia giöõa caây con traùi vaø caây con phaûi theo moät trong caùc
caùch sau:
2 + 0
1 + 1
0 + 2
Do coù theå coù hai caây nhò phaân coù hai nuùt vaø chæ coù moät caây roãng, tröôøng hôïp
thöù nhaát treân cho ra hai caây nhò phaân. Tröôøng hôïp thöù ba, töông töï, cho theâm hai
caây khaùc. Tröôøng hôïp giöõa, caây con traùi vaø caây con phaûi moãi caây chæ coù moät nuùt,
vaø chæ coù duy nhaát moät caây nhò phaân coù moät nuùt neân tröôøng hôïp naøy chæ coù moät
caây nhò phaân. Taát caû chuùng ta coù naêm caây nhò phaân coù ba nuùt:
Hình 9.2- Caùc caây nhò phaân coù ba nuùt
Caùc böôùc ñeå xaây döïng caây naøy laø moät ñieån hình cho caùc tröôøng hôïp lôùn hôn.
Chuùng ta baét ñaàu töø goác cuûa caây vaø xem caùc nuùt coøn laïi nhö laø caùc caùch phaân chia
giöõa caây con traùi vaø caây con phaûi. Caây con traùi vaø caây con phaûi luùc naøy seõ laø caùc
tröôøng hôïp nhoû hôn maø chuùng ta ñaõ bieát.
Giaùo trình Caáu truùc Döõ lieäu vaø Giaûi thuaät
186
Chöông 9 – Caây nhò phaân
Goïi N laø soá nuùt cuûa caây nhò phaân, H laø chieàu cao cuûa caây thì,
Hmax = N, Hmin = ⎣log2N⎦ +1
Nmin = H, Nmax = 2H-1
Khoaûng caùch töø moät nuùt ñeán nuùt goác xaùc ñònh chi phí caàn ñeå ñònh vò noù.
Chaúng haïn moät nuùt coù ñoä saâu laø 5 thì chuùng ta phaûi ñi töø nuùt goác vaø qua 5 caønh
treân ñöôøng ñi töø goác ñeán noù ñeå tìm ñeán noù. Do ñoù, neáu caây caøng thaáp thì vieäc tìm
ñeán caùc nuùt seõ caøng nhanh. Ñieàu naøy daãn ñeán tính chaát caân baèng cuûa caây nhò
phaân. Heä soá caân baèng cuûa caây (balance factor) laø söï cheânh leäch giöõa chieàu cao cuûa
hai caây con traùi vaø phaûi cuûa noù:
B = HL-HR
Moät caây caân baèng khi heä soá naøy baèng 0 vaø caùc caây con cuûa noù cuõng caân baèng.
Moät caây nhò phaân caân baèng vôùi chieàu cao cho tröôùc seõ coù soá nuùt laø lôùn nhaát coù
theå. Ngöôïc laïi, vôùi soá nuùt cho tröôùc caây nhò phaân caân baèng coù chieàu cao nhoû nhaát.
Thoâng thöôøng ñieàu naøy raát khoù xaûy ra neân ñònh nghóa coù theå nôùi loûng hôn vôùi caùc
trò B = –1, 0, hoaëc 1 thay vì chæ laø 0. Chuùng ta seõ hoïc kyõ hôn veà caây caân baèng
AVL trong phaàn sau.
Moät caây nhò phaân ñaày ñuû (complete tree) laø caây coù ñöôïc soá nuùt toái ña vôùi
chieàu cao cuûa noù. Ñoù cuõng chính laø caây coù B=0 vôùi moïi nuùt. Thuaät ngöõ caây nhò
phaân gaàn nhö ñaày ñuû cuõng ñöôïc duøng cho tröôøng hôïp caây coù ñöôïc chieàu cao toái
thieåu cuûa noù vaø moïi nuùt ôû möùc lôùn nhaát doàn heát veà beân traùi.
Hình 9.3 bieåu dieãn caây nhò phaân ñaày ñuû coù 31 nuùt. Giaû söû loaïi ñi caùc nuùt 19, 21,
23, 25, 27, 29, 31 ta coù moät caây nhò phaân gaàn nhö ñaày ñuû.
Hình 9.3 – Caây nhò phaân ñaày ñuû vôùi 31 nuùt.
9.2.2.Duyeät caây nhò phaân
Moät trong caùc taùc vuï quan troïng nhaát ñöôïc thöïc hieän treân caây nhò phaân laø
duyeät caây (traversal). Moät pheùp duyeät caây laø moät söï di chuyeån qua khaép
caùc nuùt cuûa caây theo moät thöù töï ñònh tröôùc, moãi nuùt chæ ñöôïc xöû lyù moät
Giaùo trình Caáu truùc Döõ lieäu vaø Giaûi thuaät
187
Chöông 9 – Caây nhò phaân
laàn duy nhaát. Cuõng nhö pheùp duyeät treân caùc caáu truùc döõ lieäu khaùc, haønh ñoäng
maø chuùng ta caàn laøm khi gheù qua moät nuùt seõ phuï thuoäc vaøo öùng duïng.
Ñoái vôùi caùc danh saùch, caùc nuùt naèm theo moät thöù töï töï nhieân töø nuùt ñaàu ñeán
nuùt cuoái, vaø pheùp duyeät cuõng theo thöù töï naøy. Tuy nhieân, ñoái vôùi caùc caây, coù raát
nhieàu thöù töï khaùc nhau ñeå duyeät qua caùc nuùt.
Coù 2 caùch tieáp caän chính khi duyeät caây: duyeät theo chieàu saâu vaø duyeät theo
chieàu roäng.
Duyeät theo chieàu saâu (defth-first traversal): moïi nuùt sau cuûa moät nuùt con ñöôïc
duyeät tröôùc khi sang moät nuùt con khaùc.
Duyeät theo chieàu roäng (breadth-first traversal): moïi nuùt trong cuøng moät möùc ñöôïc
duyeät tröôùc khi sang möùc khaùc.
9.2.2.1. Duyeät theo chieàu saâu
Taïi moät nuùt cho tröôùc, coù ba vieäc maø chuùng ta muoán laøm: gheù nuùt naøy, duyeät
caây con beân traùi, duyeät caây con beân phaûi. Söï khaùc nhau giöõa caùc phöông aùn duyeät
laø chuùng ta quyeát ñònh gheù nuùt ñoù tröôùc hoaëc sau khi duyeät hai caây con, hoaëc giöõa
khi duyeät hai caây con.
Neáu chuùng ta goïi coâng vieäc gheù moät nuùt laø V, duyeät caây con traùi laø L, duyeät
caây con phaûi laø R, thì coù ñeán saùu caùch keát hôïp giöõa chuùng:
VLR LVR LRV VRL RVL RLV.
Caùc thöù töï duyeät caây chuaån
Theo quy öôùc chuaån, saùu caùch duyeät treân giaûm xuoáng chæ coøn ba bôûi chuùng ta
chæ xem xeùt caùc caùch maø trong ñoù caây con traùi ñöôïc duyeät tröôùc caây con phaûi. Ba
caùch coøn laïi roõ raøng laø töông töï vì chuùng chính laø nhöõng thöù töï ngöôïc cuûa ba caùch
chuaån. Caùc caùch chuaån naøy ñöôïc ñaëït teân nhö sau:
VLR
LVR
LRV
preorder
inorder
postorder
Caùc teân naøy ñöôïc choïn töông öùng vôùi böôùc maø nuùt ñaõ cho ñöôïc gheù ñeán. Trong
pheùp duyeät preorder, nuùt ñöôïc gheù tröôùc caùc caây con; trong pheùp duyeät inorder, noù
ñöôïc gheù ñeán giöõa khi duyeät hai caây con; vaø trong pheùp duyeät postorder, goác cuûa
caây ñöôïc gheù sau hai caây con cuûa noù.
Giaùo trình Caáu truùc Döõ lieäu vaø Giaûi thuaät
188
Chöông 9 – Caây nhò phaân
Pheùp duyeät inorder ñoâi khi coøn ñöôïc goïi laø pheùp duyeät ñoái xöùng (symmetric
order), vaø postorder ñöôïc goïi laø endorder.
Caùc ví duï ñôn giaûn
Trong ví duï thöù nhaát, chuùng ta haõy xeùt caây nhò phaân sau:
1
2
3
Vôùi pheùp duyeät preorder, goác caây mang nhaõn 1 ñöôïc gheù ñaàu tieân, sau ñoù pheùp
duyeät di chuyeån sang caây con traùi. Caây con traùi chæ chöùa moät nuùt coù nhaõn laø 2,
nuùt naøy ñöôïc duyeät thöù hai. Sau ñoù pheùp duyeät chuyeån sang caây con phaûi cuûa nuùt
goác, cuoái cuøng laø nuùt mang nhaõn 3 ñöôïc gheù. Vaäy pheùp duyeät preorder seõ gheù caùc
nuùt theo thöù töï 1, 2, 3.
Tröôùc khi goác cuûa caây ñöôïc gheù theo thöù töï inorder, chuùng ta phaûi duyeät caây
con traùi cuûa noù tröôùc. Do ñoù nuùt mang nhaõn 2 ñöôïc gheù ñaàu tieân. Ñoù laø nuùt duy
nhaát trong caây con traùi. Sau ñoù pheùp duyeät chuyeån ñeán nuùt goác mang nhaõn 1, vaø
cuoái cuøng duyeät qua caây con phaûi. Vaäy pheùp duyeät inorder seõ gheù caùc nuùt theo thöù
töï 2, 1, 3.
Vôùi pheùp duyeät postorder, chuùng ta phaûi duyeät caùc hai caây con traùi vaø phaûi
tröôùc khi gheù nuùt goác. Tröôùc tieân chuùng ta ñi ñeán caây con beân traùi chæ coù moät nuùt
mang nhaõn 2, vaø noù ñöôïc gheù ñaàu tieân. Tieáp theo, chuùng ta duyeät qua caây con
phaûi, gheù nuùt 3, vaø cuoái cuøng chuùng ta gheù nuùt 1. Pheùp duyeät postorder duyeät caùc
nuùt theo thöù töï 2, 3, 1.
Ví duï thöù hai phöùc taïp hôn, chuùng ta haõy xem xeùt caây nhò phaân döôùi ñaây:
1
2
3
5
4
Giaùo trình Caáu truùc Döõ lieäu vaø Giaûi thuaät
189
Chöông 9 – Caây nhò phaân
Töông töï caùch laøm treân chuùng ta coù pheùp duyeät preorder seõ gheù caùc nuùt theo
thöù töï 1, 2, 3, 4, 5. Pheùp duyeät inorder seõ gheù caùc nuùt theo thöù töï 1, 4, 3, 5, 2.
Pheùp duyeät postorder seõ gheù caùc nuùt theo thöù töï 4, 5, 3, 2, 1.
Caây bieåu thöùc
Caùch choïn caùc teân preorder, inorder, vaø postorder cho ba pheùp duyeät caây treân
khoâng phaûi laø tình côø, noù lieân quan chaët cheõ ñeán moät trong nhöõng öùng duïng, ñoù
laø caùc caây bieåu thöùc.
Moät caây bieåu thöùc (expression tree) ñöôïc taïo neân töø caùc toaùn haïng ñôn giaûn vaø
caùc toaùn töû (soá hoïc hoaëc luaän lyù) cuûa bieåu thöùc baèng caùch thay theá caùc toaùn haïng
ñôn giaûn baèng caùc nuùt laù cuûa moät caây nhò phaân vaø caùc toaùn töû baèng caùc nuùt beân
trong caây. Ñoái vôùi moãi toaùn töû hai ngoâi, caây con traùi chöùa moïi toaùn haïng vaø moïi
toaùn töû thuoäc toaùn haïng beân traùi cuûa toaùn töû ñoù, vaø caây con phaûi chöùa moïi toaùn
haïng vaø moïi toaùn töû thuoäc toaùn haïng beân phaûi cuûa noù.
Hình 9.4 – Caây bieåu thöùc
Ñoái vôùi toaùn töû moät ngoâi, moät trong hai caây con seõ roãng. Chuùng ta thöôøng vieát
moät vaøi toaùn töû moät ngoâi phía beân traùi cuûa toaùn haïng cuûa chuùng, chaúng haïn daáu
tröø (pheùp laáy soá aâm) hoaëc caùc haøm chuaån nhö log() vaø cos(). Caùc toaùn töû moät ngoâi
khaùc ñöôïc vieát beân phaûi cuûa toaùn haïng, chaúng haïn haøm giai thöøa ()! hoaëc haøm
bình phöông ()2. Ñoâi khi caû hai phía ñeàu hôïp leä, nhö pheùp laáy ñaïo haøm coù theå vieát
d/dx phía beân traùi, hoaëc ()’ phía beân phaûi, hoaëc toaùn töû taêng ++ coù aûnh höôûng
Giaùo trình Caáu truùc Döõ lieäu vaø Giaûi thuaät
190
Chöông 9 – Caây nhò phaân
khaùc nhau khi naèm beân traùi hoaëc naèm beân phaûi. Neáu toaùn töû ñöôïc ghi beân traùi,
thì trong caây bieåu thöùc noù seõ coù caây con traùi roãng, nhö vaäy toaùn haïng seõ xuaát hieän
beân phaûi cuûa noù trong caây. Ngöôïc laïi, neáu toaùn töû xuaát hieän beân phaûi, thì caây con
phaûi cuûa noù seõ roãng, vaø toaùn haïng seõ laø caây con traùi cuûa noù.
Moät soá caây bieåu thöùc cuûa moät vaøi bieåu thöùc ñôn giaûn ñöôïc minh hoïa trong hình
9.4. Hình 9.5 bieåu dieãn moät coâng thöùc baäc hai phöùc taïp hôn. Ba thöù töï duyeät caây
chuaån cho caây bieåu thöùc naøy lieät keâ trong hình 9.6.
Hình 9.5 – Caây bieåu thöùc cho coâng thöùc baäc hai.
Caùc teân cuûa caùc pheùp duyeät lieân quan ñeán caùc daïng Balan cuûa bieåu thöùc: duyeät
caây bieåu thöùc theo preorder laø daïng prefix, trong ñoù moãi toaùn töû naèm tröôùc caùc
toaùn haïng cuûa noù; duyeät caây bieåu thöùc theo inorder laø daïng infix (caùch vieát bieåu
thöùc quen thuoäc cuûa chuùng ta); duyeät caây bieåu thöùc theo postorder laø daïng postfix,
moïi toaùn haïng naèm tröôùc toaùn töû cuûa chuùng. Nhö vaäy caùc caây con traùi vaø caây con
phaûi cuûa moãi nuùt luoân laø caùc toaùn haïng cuûa noù, vaø vò trí töông ñoái cuûa moät toaùn töû
so vôùi caùc toaùn haïng cuûa noù trong ba daïng Balan hoaøn toaøn gioáng vôùi thöù töï töông
ñoái cuûa caùc laàn gheù caùc thaønh phaàn naøy theo moät trong ba pheùp duyeät caây bieåu
thöùc.
Giaùo trình Caáu truùc Döõ lieäu vaø Giaûi thuaät
191
Chöông 9 – Caây nhò phaân
Hình 9.6 – Caùc thöù tö duyeät cho caây bieåu thöùc
Caây so saùnh
Hình 9.7 – Caây so saùnh ñeå tìm nhò phaân
Chuùng ta haõy xem laïi ví duï trong hình 9.7 vaø ghi laïi keát quaû cuûa ba pheùp
duyeät caây chuaån nhö sau:
preorder: Jim Dot Amy Ann Guy Eva Jan Ron Kay Jon Kim Tim Roy Tom
inorder: Amy Ann Dot Eva Guy Jan Jim Jon Kay Kim Ron Roy Tim Tom
postorder:Ann Amy Eva Jan Guy Dot Jon Kim Kay Roy Tom Tim Ron Jim
Pheùp duyeät inorder cho caùc teân coù thöù töï theo alphabet. Caùch taïo moät caây so
saùnh nhö hình 9.7 nhö sau: di chuyeån sang traùi khi khoùa cuûa nuùt caàn theâm nhoû
hôn khoùa cuûa nuùt ñang xeùt, ngöôïc laïi thì di chuyeån sang phaûi. Nhö vaäy caây nhò
phaân treân ñaõ ñöôïc xaây döïng sao cho moïi nuùt trong caây con traùi cuûa moãi nuùt coù thöù
töï nhoû hôn thöù töï cuûa noù, vaø moïi nuùt trong caây con phaûi coù thöù töï lôùn hôn noù. Do
ñoái vôùi moãi nuùt, pheùp duyeät inorder seõ duyeät qua caùc nuùt trong caây con traùi tröôùc,
roài ñeán chính noù, vaø cuoái cuøng laø caùc nuùt trong caây con phaûi, neân chuùng ta coù ñöôïc
caùc nuùt theo thöù töï.
Giaùo trình Caáu truùc Döõ lieäu vaø Giaûi thuaät
192
Chöông 9 – Caây nhò phaân
Trong phaàn sau chuùng ta seõ tìm hieåu caùc caây nhò phaân vôùi ñaëc tính treân,
chuùng coøn ñöôïc goïi laø caùc caây nhò phaân tìm kieám (binary search tree), do chuùng
raát coù ích vaø hieäu quaû cho yeâu caàu tìm kieám.
9.2.2.2. Duyeät theo chieàu roäng
Thöù töï duyeät caây theo chieàu roäng laø thöù töï duyeät heát möùc naøy ñeán möùc kia, coù
theå töø möùc cao ñeán möùc thaáp hoaëc ngöôïc laïi. Trong moãi möùc coù theå duyeät töø traùi
sang phaûi hoaëc töø phaûi sang traùi. Ví duï caây trong hình 9.7 neáu duyeät theo chieàu
roäng töø möùc thaáp ñeán möùc cao, trong moãi möùc duyeät töø traùi sang phaûi, ta coù: Jim,
Dot, Ron, Amy, Guy, Kay, Tim, Ann, Eva, Jan, Jon, Kim, Roy, Tom.
9.2.3.Hieän thöïc lieân keát cuûa caây nhò phaân
Chuùng ta haõy xem xeùt caùch bieåu dieãn cuûa caùc nuùt ñeå xaây döïng neân caây.
9.2.3.1. Caáu truùc cô baûn cho moät nuùt trong caây nhò phaân
Hình 9.8 – Caây nhò phaân lieân keát
Moãi nuùt cuûa moät caây nhò phaân (cuõng laø goác cuûa moät caây con naøo ñoù) coù hai caây
con traùi vaø phaûi. Caùc caây con naøy coù theå ñöôïc xaùc ñònh thoâng qua caùc con troû chæ
ñeán caùc nuùt goác cuûa noù. Chuùng ta coù ñaëc taû sau:
template <class Entry>
struct Binary_node {
// Caùc thaønh phaàn.
Entry data;
Binary_node<Entry> *left;
Binary_node<Entry> *right;
Giaùo trình Caáu truùc Döõ lieäu vaø Giaûi thuaät
193
Chöông 9 – Caây nhò phaân
// constructors:
Binary_node();
Binary_node(const Entry &x);
};
Binary_nodechöùa hai constructor ñeàu khôûi gaùn caùc thuoäc tính con troû laø NULL
moãi khi ñoái töôïng ñöôïc taïo ra.
Trong hình 9.8, chuùng ta thaáy nhöõng tham chieáu NULL, tuy nhieân chuùng ta coù
theå quy öôùc raèng caùc caây con roãng vaø caùc caønh ñeán noù coù theå boû qua khoâng caàn
hieån thò khi veõ caây.
9.2.3.2. Ñaëc taû caây nhò phaân
Moät caây nhò phaân coù moät hieän thöïc töï nhieân trong vuøng nhôù lieân keát. Cuõng
nhö caùc caáu truùc lieân keát, chuùng ta seõ caáp phaùt ñoäng caùc nuùt, noái keát chuùng laïi vôùi
nhau. Chuùng ta chæ caàn moät con troû chæ ñeán nuùt goác cuûa caây.
template <class Entry>
class Binary_tree {
public:
Binary_tree();
bool empty() const;
void preorder(void (*visit)(Entry &));
void inorder(void (*visit)(Entry &));
void postorder(void (*visit)(Entry &));
int size() const;
void clear();
int height() const;
void insert(const Entry &);
Binary_tree (const Binary_tree<Entry> &original);
Binary_tree & operator =(const Binary_tree<Entry> &original);
~Binary_tree();
protected:
// Caùc haøm ñeä quy phuï trôï:
void recursive_inorder(Binary_node<Entry>*sub_root,
void (*visit)(Entry &))
void recursive_preorder(Binary_node<Entry>*sub_root,
void (*visit)(Entry &))
void recursive_postorder(Binary_node<Entry>*sub_root,
void (*visit)(Entry &))
Binary_node<Entry> *root;
};
Vôùi con troû root, coù theå deã daøng nhaän ra moät caây nhò phaân roãng bôûi bieåu thöùc
root == NULL;
vaø khi taïo moät caây nhò phaân môùi chuùng ta chæ caàn gaùn rootbaèng NULL.
Giaùo trình Caáu truùc Döõ lieäu vaø Giaûi thuaät
194
Chöông 9 – Caây nhò phaân
template <class Entry>
Binary_tree<Entry>::Binary_tree()
/*
post: Caây nhò phaân roãng ñöôïc taïo ra.
*/
{
root = NULL;
}
Phöông thöùc emptykieåm tra xem moät caây nhò phaân coù roãng hay khoâng:
template <class Entry>
bool Binary_tree<Entry>::empty() const
/*
post: Traû veà trueneáu caäy roãng, ngöôïc laïi traû veà false.
*/
{
return root == NULL;
}
9.2.3.3. Duyeät caây
Baây giôø chuùng ta seõ xaây döïng caùc phöông thöùc duyeät moät caây nhò phaân lieân keát
theo caû ba pheùp duyeät cô baûn. Cuõng nhö tröôùc kia, chuùng ta seõ giaû söû nhö chuùng
ta ñaõ coù haøm visitñeå thöïc hieän moät coâng vieäc mong muoán naøo ñoù cho moãi nuùt
cuûa caây. Vaø nhö caùc haøm duyeät cho nhöõng caáu truùc döõ lieäu khaùc, con troû haøm
visitseõ laø moät thoâng soá hình thöùc cuûa caùc haøm duyeät caây.
Trong caùc haøm duyeät caây, chuùng ta caàn gheù ñeán nuùt goác vaø duyeät caùc caây con
cuûa noù. Ñeä quy seõ laøm cho vieäc duyeät caùc caây con trôû neân heát söùc deã daøng. Caùc caây
con ñöôïc tìm thaáy nhôø caùc con troû trong nuùt goác, do ñoù caùc con troû naøy caàn ñöôïc
chuyeån cho caùc laàn goïi ñeä quy. Moãi phöông thöùc duyeät caàn goïi haøm ñeä quy coù moät
thoâng soá con troû. Chaúng haïn, phöông thöùc duyeät inorder ñöôïc vieát nhö sau:
template <class Entry>
void Binary_tree<Entry>::inorder(void (*visit)(Entry &))
/*
post: Caây ñöôïc duyeät theo thöù töï inorder
uses: Haøm recursive_inorder
*/
{
recursive_inorder(root, visit);
}
Moät caùch toång quaùt, chuùng ta nhaän thaáy moät caùch toång quaùt raèng baát kyø
phöông thöùc naøo cuûa Binary_tree maø baûn chaát laø moät quaù trình ñeä quy cuõng ñöôïc
hieän thöïc baèng caùch goïi moät haøm ñeä quy phuï trôï coù thoâng soá laø goác cuûa caây. Haøm
duyeät inorder phuï trôï ñöôïc hieän thöïc baèng caùch goïi ñeä quy ñôn giaûn nhö sau:
Giaùo trình Caáu truùc Döõ lieäu vaø Giaûi thuaät
195
Chöông 9 – Caây nhò phaân
template <class Entry>
void Binary_tree<Entry>::recursive_inorder(Binary_node<Entry>*sub_root, void
(*visit)(Entry &))
/*
pre: sub_root hoaëc laø NULLhoaëc chæ ñeán goác cuûa moät caây con.
post: Caây con ñöôïc duyeät theo thöù töï inorder.
uses: Haøm recursive_inorder ñöôïc goïi ñeä quy.
*/
{
if (sub_root != NULL) {
recursive_inorder(sub_root->left, visit);
(*visit)(sub_root->data);
recursive_inorder(sub_root->right, visit);
}
}
Caùc phöông thöùc duyeät khaùc cuõng ñöôïc xaây döïng moät caùch töông töï baèng caùch
goïi caùc haøm ñeä quy phuï trôï. caùc haøm ñeä quy phuï trôï coù hieän thöïc nhö sau:
template <class Entry>
void Binary_tree<Entry>::recursive_preorder(Binary_node<Entry> *sub_root,
void (*visit)(Entry &))
/*
pre: sub_root hoaëc laø NULLhoaëc chæ ñeán goác cuûa moät caây con.
post: Caây con ñöôïc duyeät theo thöù töï preorder.
uses: Haøm recursive_inorder ñöôïc goïi ñeä quy.
*/
{
if (sub_root != NULL) {
(*visit)(sub_root->data);
recursive_preorder(sub_root->left, visit);
recursive_preorder(sub_root->right, visit);
}
}
template <class Entry>
void Binary_tree<Entry>::recursive_postorder(Binary_node<Entry> *sub_root,
void (*visit)(Entry &))
/*
pre: sub_root hoaëc laø NULLhoaëc chæ ñeán goác cuûa moät caây con.
post: Caây con ñöôïc duyeät theo thöù töï postorder.
uses: Haøm recursive_inorder ñöôïc goïi ñeä quy.
*/
{
if (sub_root != NULL) {
recursive_postorder(sub_root->left, visit);
recursive_postorder(sub_root->right, visit);
(*visit)(sub_root->data);
}
}
Chöông trình duyeät caây theo chieàu roäng luoân phaûi söû duïng ñeán CTDL haøng
ñôïi. Neáu duyeät theo thöù töï töø möùc thaáp ñeán möùc cao, moãi möùc duyeät töø traùi sang
phaûi, tröôùc tieân nuùt goác ñöôïc ñöa vaøo haøng ñôïi. Coâng vieäc ñöôïc laëp cho ñeán khi
Giaùo trình Caáu truùc Döõ lieäu vaø Giaûi thuaät
196
Chöông 9 – Caây nhò phaân
haøng ñôïi roãng: laáy moät nuùt ra khoûi haøng ñôïi, xöû lyù cho noù, ñöa caùc nuùt con cuûa noù
vaøo haøng ñôïi (theo ñuùng thöù töï töø traùi sang phaûi). Caùc bieán theå khaùc cuûa pheùp
duyeät caây theo chieàu roäng cuõng voâ cuøng ñôn giaûn, sinh vieân coù theå töï suy nghó
theâm.
Chuùng ta ñeå phaàn hieän thöïc caùc phöông thöùc cuûa caây nhò phaân nhö height,
size, vaø clear nhö laø baøi taäp. Caùc phöông thöùc naøy cuõng ñöôïc hieän thöïc deã
daøng baèng caùch goïi caùc haøm ñeä quy phuï trôï. Trong phaàn baøi taäp chuùng ta cuõng seõ
vieát phöông thöùc insert ñeå theâm caùc phaàn töû vaøo caây nhò phaân, phöông thöùc
naøy caàn ñeå taïo moät caây nhò phaân, sau ñoù, keát hôïp vôùi caùc phöông thöùc neâu treân,
chuùng ta seõ kieåm tra lôùp Binary_treemaø chuùng ta xaây döïng ñöôïc.
Trong phaàn sau cuûa chöông naøy, chuùng ta seõ xaây döïng caùc lôùp daãn xuaát töø caây
nhò phaân coù nhieàu ñaëc tính vaø höõu ích hôn (caùc lôùp daãn xuaát naøy seõ coù caùc phöông
thöùc theâm hoaëc loaïi phaàn töû trong caây thích hôïp vôùi ñaëc tính cuûa töøng loaïi caây).
Coøn hieän taïi thì chuùng ta khoâng neân theâm nhöõng phöông thöùc nhö vaäy vaøo caây
nhò phaân cô baûn.
Maëc duø lôùp Binary_treecuûa chuùng ta xuaát hieän chæ nhö laø moät lôùp voû maø caùc
phöông thöùc cuûa noù ñeàu ñaåy caùc coâng vieäc caàn laøm ñeán cho caùc haøm phuï trôï, baûn
thaân noù laïi mang moät yù nghóa quan troïng. Lôùp naøy taäp trung vaøo noù nhieàu haøm
khaùc nhau vaø cung caáp moät giao dieän thuaän tieän töông töï caùc kieåu döõ lieäu tröøu
töôïng khaùc. Hôn nöõa, chính lôùp môùi coù theå cung caáp tính ñoùng kín: khoâng coù noù
thì caùc döõ lieäu trong caây khoâng ñöôïc baûo veä moät caùch an toaøn vaø deã daøng bò thaâm
nhaäp vaø söûa ñoåi ngoaøi yù muoán. Cuoái cuøng, chuùng ta coù theå thaáy lôùp Binary_tree
coøn laøm moät lôùp cô sôû cho caùc lôùp khaùc daãn xuaát töø noù höõu ích hôn.
9.3. Caây nhò phaân tìm kieám
Chuùng ta haõy xem xeùt vaán ñeà tìm kieám moät khoùa trong moät danh saùch lieân
keát. Khoâng coù caùch naøo khaùc ngoaøi caùch di chuyeån treân danh saùch moãi laàn moät
phaàn töû, vaø do ñoù vieäc tìm kieám treân danh saùch lieân keát luoân laø tìm tuaàn töï. Vieäc
tìm kieám seõ trôû neân nhanh hôn nhieàu neáu chuùng ta söû duïng danh saùch lieân tuïc vaø
tìm nhò phaân. Tuy nhieân, danh saùch lieân tuïc laïi khoâng phuø hôïp vôùi söï bieán ñoäng
döõ lieäu. Giaû söû chuùng ta cuõng caàn thay ñoåi danh saùch thöôøng xuyeân, theâm caùc
phaàn töû môùi hoaëc loaïi caùc phaàn töû hieän coù. Nhö vaäy danh saùch lieân tuïc seõ chaäm
hôn nhieàu so vôùi danh saùch lieân keát, do vieäc theâm vaø loaïi phaàn töû trong danh
saùch lieân tuïc moãi laàn ñeàu ñoøi hoûi phaûi di chuyeån nhieàu phaàn töû sang caùc vò trí
khaùc. Trong danh saùch lieân keát chæ caàn thay ñoåi moät vaøi con troû maø thoâi.
Vaán ñeà chuû choát trong phaàn naøy chính laø:
Lieäu chuùng ta coù theå tìm moät hieän thöïc cho caùc danh saùch coù thöù töï maø trong
ñoù chuùng ta coù theå tìm kieám, hoaëc theâm bôùt phaàn töû ñeàu raát nhanh?
Giaùo trình Caáu truùc Döõ lieäu vaø Giaûi thuaät
197
Chöông 9 – Caây nhò phaân
Caây nhò phaân cho moät lôøi giaûi toát cho vaán ñeà naøy. Baèng caùch ñaët caùc entry
cuûa moät danh saùch coù thöù töï vaøo trong caùc nuùt cuûa moät caây nhò phaân, chuùng ta seõ
thaáy raèng chuùng ta coù theå tìm moät khoùa cho tröôùc qua O(log n) böôùc, gioáng nhö
tìm nhò phaân, ñoàng thôøi chuùng ta cuõng coù giaûi thuaät theâm vaø loaïi phaàn töû trong
O(log n) thôøi gian.
Ñònh nghóa: Moät caây nhò phaân tìm kieám (binary search tree -BST) laø moät caây
hoaëc roãng hoaëc trong ñoù moãi nuùt coù moät khoùa (naèm trong phaàn döõ lieäu cuûa noù)
vaø thoûa caùc ñieàu kieän sau:
1. Khoùa cuûa nuùt goác lôùn hôn khoùa cuûa baát kyø nuùt naøo trong caây con traùi cuûa noù.
2. Khoùa cuûa nuùt goác nhoû hôn khoùa cuûa baát kyø nuùt naøo trong caây con phaûi cuûa noù.
3. Caây con traùi vaø caây con phaûi cuûa goác cuõng laø caùc caây nhò phaân tìm kieám.
Hai ñaëc tính ñaàu tieân moâ taû thöù töï lieân quan ñeán khoùa cuûa nuùt goác, ñaëc tính
thöù ba môû roäng chuùng ñeán moïi nuùt trong caây; do ñoù chuùng ta coù theå tieáp tuïc söû
duïng caáu truùc ñeä quy cuûa caây nhò phaân. Chuùng ta ñaõ vieát ñònh nghóa naøy theo
caùch maø noù baûo ñaûm raèng khoâng coù hai phaàn töû trong moät caây nhò phaân tìm kieám
coù cuøng khoùa, do caùc khoùa trong caây con traùi chính xaùc laø nhoû hôn khoùa cuûa goác,
vaø caùc khoùa cuûa caây con phaûi cuõng chính xaùc laø lôùn hôn khoùa cuûa goác. Chuùng ta coù
theå thay ñoåi ñònh nghóa ñeå cho pheùp caùc phaàn töû truøng khoùa. Tuy nhieân trong
phaàn naøy chuùng ta coù theå giaû söû raèng:
Khoâng coù hai phaàn töû trong moät caây nhò phaân tìm kieám coù truøng khoùa.
Caùc caây nhò phaân trong hình 9.7 vaø 9.8 laø caùc caây nhò phaân tìm kieám, do quyeát
ñònh di chuyeån sang traùi hoaëc phaûi taïi moãi nuùt döïa treân caùch so saùnh caùc khoùa
trong ñònh nghóa cuûa moät caây tìm kieám.
9.3.1.Caùc danh saùch coù thöù töï vaø caùc caùch hieän thöïc
Ñaõ ñeán luùc baét ñaàu xaây döïng caùc phöông thöùc C++ ñeå xöû lyù cho caây nhò phaân
tìm kieám, chuùng ta neân löu yù raèng coù ít nhaát laø ba quan ñieåm khaùc nhau döôùi ñaây:
• Chuùng ta coù theå xem caây nhò phaân tìm kieám nhö moät kieåu döõ lieäu tröøu töôïng
môùi vôùi ñònh nghóa vaø caùc phöông thöùc cuûa noù;
• Do caây nhò phaân tìm kieám laø moät daïng ñaëc bieät cuûa caây nhò phaân, chuùng ta coù
theå xem caùc phöông thöùc cuûa noù nhö caùc daïng ñaëc bieät cuûa caùc phöông thöùc cuûa
caây nhò phaân;
• Do caùc phaàn töû trong caây nhò phaân tìm kieám coù chöùa caùc khoùa, vaø do chuùng
ñöôïc gaùn döõ lieäu ñeå truy xuaát thoâng tin theo caùch töông töï nhö caùc danh saùch
coù thöù töï, chuùng ta coù theå nghieân cöùu caây nhò phaân tìm kieám nhö laø moät hieän
thöïc môùi cuûa kieåu döõ lieäu tröøu töôïng danh saùch coù thöù töï (ordered list ADT).
Giaùo trình Caáu truùc Döõ lieäu vaø Giaûi thuaät
198
Chöông 9 – Caây nhò phaân
Trong thöïc teá, ñoâi khi caùc laäp trình vieân chæ taäp trung vaøo moät trong ba quan
ñieåm treân, vaø chuùng ta cuõng seõ nhö theá. Chuùng ta seõ ñaëc taû lôùp caây nhò phaân tìm
kieám daãn xuaát töø caây nhò phaân. Nhö vaäy, lôùp caây nhò phaân cuûa chuùng ta laïi bieåu
dieãn cho moät kieåu döõ lieäu tröøu töôïng khaùc. Tuy nhieân, lôùp môùi seõ thöøa keá caùc
phöông thöùc cuûa lôùp caây nhò phaân tröôùc kia. Baèng caùch naøy, söï söû duïng lôùp thöøa
keá nhaán maïnh vaøo hai quan ñieåm treân. Quan ñieåm thöù ba thöôøng ñöôïc nhìn thaáy
trong caùc öùng duïng cuûa caây nhò phaân tìm kieám. Chöông trình cuûa ngöôøi söû duïng
coù theå duøng lôùp cuûa chuùng ta ñeå giaûi quyeát caùc baøi toaùn saép thöù töï vaø tìm kieám
lieân quan ñeán danh saùch coù thöù töï.
Chuùng ta ñaõ ñöa ra nhöõng khai baùo C++ cho pheùp xöû lyù cho caây nhò phaân.
Chuùng ta seõ söû duïng hieän thöïc naøy cuûa caây nhò phaân laøm cô sôû cho lôùp caây nhò
phaân tìm kieám.
template <class Record>
class Search_tree: public Binary_tree<Record> {
public:
Error_code insert(const Record &new_data);
Error_code remove(const Record &old_data);
Error_code tree_search(Record &target) const;
private: // Caùc haøm ñeä quy phuï trôï.
};
Do lôùp caây nhò phaân tìm kieám thöøa keá töø lôùp nhò phaân, chuùng ta coù theå duøng
laïi caùc phöông thöùc ñaõ ñònh nghóa treân caây nhò phaân toång quaùt cho caây nhò phaân
tìm kieám. Caùc phöông thöùc naøy laø constructor, destructor, clear, empty,
size, height, vaø caùc phöông thöùc duyeät preorder, inorder, postorder. Ñeå
theâm vaøo caùc phöông thöùc naøy, moät caây nhò phaân tìm kieám caàn theâm caùc phöông
thöùc chuyeân bieät hoùa nhö insert, remove, vaø tree_search.
9.3.2.Tìm kieám treân caây
Phöông thöùc môùi quan troïng ñaàu tieân cuûa caây nhò phaân tìm kieám laø: tìm moät
phaàn töû vôùi moät khoùa cho tröôùc trong caây nhò phaân tìm kieám lieân keát. Ñaëc taû cuûa
phöông thöùc nhö sau:
Error_code Search_tree<Record> :: tree_search (Record &target) const;
post: Neáu coù moät phaàn töû coù khoùa truøng vôùi khoùa trong target, thì target ñöôïc cheùp ñeø bôûi
phaàn töû naøy, phöông thöùc traû veà success; ngöôïc laïi phöông thöùc traû veà not_present.
ÔÛ ñaây chuùng ta duøng lôùp Record nhö ñaõ moâ taû trong chöông 7. Ngoaøi thuoäc
tính thuoäc lôùp Key daønh cho khoùa, trong Record coù theå coøn nhieàu thaønh phaàn döõ
lieäu khaùc. Trong caùc öùng duïng, phöông thöùc naøy thöôøng ñöôïc goïi vôùi thoâng soá
target chæ chöùa trò cuûa thaønh phaàn khoùa. Neáu tìm thaáy khoùa caàn tìm, phöông
thöùc seõ boå sung caùc döõ lieäu ñaày ñuû vaøo caùc thaønh phaàn khaùc coøn laïi cuûa Record.
Giaùo trình Caáu truùc Döõ lieäu vaø Giaûi thuaät
199
Chöông 9 – Caây nhò phaân
9.3.2.1. Chieán löôïc
Ñeå tìm moät khoùa, tröôùc tieân chuùng ta so saùnh noù vôùi khoùa cuûa nuùt goác trong
caây. Neáu so truøng, giaûi thuaät döøng. Ngöôïc laïi, chuùng ta ñi sang caây con traùi hoaëc
caây con phaûi vaø laëp laïi vieäc tìm kieám trong caây con naøy.
Ví duï, chuùng ta caàn tìm teân Kim trong caây nhò phaân tìm kieám hình 9.7 vaø 9.8.
Chuùng ta so saùnh Kim vôùi phaàn töû taïi nuùt goác, Jim. Do Kim lôùn hôn Jim theo thöù
töï alphabet, chuùng ta ñi sang phaûi vaø tieáp tuïc so saùnh Kim vôùi Ron. Do Kim nhoû
hôn Jon, chuùng ta di chuyeån sang traùi, so saùnh Kim vôùi Kay. Chuùng ta laïi di
chuyeån sang phaûi vaø gaëp ñöôïc phaàn töû caàn tìm.
Ñaây roõ raøng laø moät quaù trình ñeä quy, cho neân chuùng ta seõ hieän thöïc phöông
thöùc naøy baèng caùch goïi moät haøm ñeä quy phuï trôï. Lieäu ñieàu kieän döøng cuûa vieäc tìm
kieám ñeä quy laø gì? Roõ raøng laø, neáu chuùng ta tìm thaáy phaàn töû caàn tìm, haøm seõ keát
thuùc thaønh coâng. Neáu khoâng, chuùng ta seõ cöù tieáp tuïc tìm cho ñeán khi gaëp moät caây
roãng, trong tröôøng hôïp naøy vieäc tìm kieám thaát baïi.
Haøm ñeä quy tìm kieám phuï trôï seõ traû veà moät con troû chæ ñeán phaàn töû ñöôïc tìm
thaáy. Maëc duø con troû naøy coù theå ñöôïc söû duïng ñeå truy xuaát ñeán döõ lieäu löu trong
ñoái töôïng caây, nhöng chæ coù caùc haøm laø nhöõng phöông thöùc cuûa caây môùi coù theå goïi
haøm tìm kieám phuï trôï naøy (vì chæ coù chuùng môùi coù theå gôûi thuoäc tính root cuûa
caây laøm thoâng soá). Nhö vaäy, vieäc traû veà con troû ñeán moät nuùt seõ khoâng vi phaïm
ñeán tính ñoùng kín cuûa caây khi nhìn töø öùng duïng beân ngoaøi. Chuùng ta coù ñaëc taû
sau ñaây cuûa haøm tìm kieám phuï trôï.
Binary_node<Record> *Search_tree<Record> :: search_for_node
(Binary_node<Record> *sub_root, const Record &target) const;
pre: sub_roothoaëc laø NULLhoaëc chæ ñeán moät caây con cuûa lôùp Search_tree.
post:Neáu khoùa cuûa targetkhoâng coù trong caây con sub_tree, haøm traû veà NULL; ngöôïc laïi, haøm
traû veà con troû ñeán nuùt chöùa target.
9.3.2.2. Phieân baûn ñeä quy
Caùch ñôn giaûn nhaát ñeå vieát haøm tìm kieám treân laø duøng ñeä quy:
template <class Record>
Binary_node<Record> *Search_tree<Record>::search_for_node(
Binary_node<Record>* sub_root, const Record &target) const
{
if (sub_root == NULL || sub_root->data == target) return sub_root;
else if (sub_root->data < target)
return search_for_node(sub_root->right, target);
else return search_for_node(sub_root->left, target);
}
Giaùo trình Caáu truùc Döõ lieäu vaø Giaûi thuaät
200
Chöông 9 – Caây nhò phaân
9.3.2.3. Khöû ñeä quy
Ñeä quy xuaát hieän trong haøm treân chæ laø ñeä quy ñuoâi, ñoù laø leänh cuoái cuøng ñöôïc
thöïc hieän trong haøm. Baèng caùch söû duïng voøng laëp, ñeä quy ñuoâi luoân coù theå ñöôïc
thay theá bôûi söï laëp laïi nhieàu laàn. Trong tröôøng hôïp naøy chuùng ta caàn vieát voøng
laëp theá cho leänh if ñaàu tieân, vaø thay ñoåi thoâng soá sub_root ñeå noù di chuyeån
xuoáng caùc caønh cuûa caây.
template <class Record>
Binary_node<Record> *Search_tree<Record>::search_for_node(
Binary_node<Record> *sub_root, const Record &target) const
{
while (sub_root != NULL && sub_root->data != target)
if (sub_root->data < target)
sub_root = sub_root->right;
else sub_root = sub_root->left;
return sub_root;
}
9.3.2.4. Phöông thöùc tree_search
Phöông thöùc tree_searchñôn giaûn chæ goïi haøm phuï trôï search_for_node
ñeå tìm nuùt chöùa khoùa truøng vôùi khoùa caàn tìm trong caây tìm kieám nhò phaân. Sau
ñoù noù trích döõ lieäu caàn thieát vaø traû veà Error_codetöông öùng.
template <class Record>
Error_code Search_tree<Record>::tree_search(Record &target) const
/*
post: Neáu tìm thaáy khoùa caàn tìm trong target, phöông thöùc seõ boå sung caùc döõ lieäu ñaày ñuû vaøo
caùc thaønh phaàn khaùc coøn laïi cuûa target vaø traø veà success. Ngöôïc laïi traû veà
not_present. Caû hai tröôøng hôïp caây ñeàu khoâng thay ñoåi.
Uses: Haøm search_for_node
*/
{
Error_code result = success;
Binary_node<Record> *found = search_for_node(root, target);
if (found == NULL)
result = not_present;
else
target = found->data;
return result;
}
9.3.2.5. Haønh vi cuûa giaûi thuaät
Chuùng ta thaáy raèng tree_searchdöïa treân cô sôû cuûa tìm nhò phaân. Neáu chuùng
ta thöïc hieän tìm nhò phaân treân moät danh saùch coù thöù töï, chuùng ta thaáy raèng tìm
nhò phaân thöïc hieän caùc pheùp so saùnh hoaøn toaøn gioáng nhö tree_search. Chuùng
ta cuõng ñaõ bieát tìm nhò phaân thöïc hieän O(log n) laàn so saùnh ñoái vôùi danh saùch coù
chieàu daøi n. Ñieàu naøy thöïc söï toát so vôùi caùc phöông phaùp tìm kieám khaùc, do log n
taêng raát chaäm khi n taêng.
Giaùo trình Caáu truùc Döõ lieäu vaø Giaûi thuaät
201
Chöông 9 – Caây nhò phaân
Caây trong hình 9.9a laø caây toát nhaát ñoái vôùi vieäc tìm kieám. Caây caøng “raäm raïp”
caøng toát: noù coù chieàu cao nhoû nhaát ñoái vôùi soá nuùt cho tröôùc. Soá nuùt naèm giöõa nuùt
goác vaø nuùt caàn tìm, keå caû nuùt caàn tìm, laø soá laàn so saùnh caàn thöïc hieän khi tìm
kieám. Vì vaäy, caây caøng raäm raïp thì soá laàn so saùnh naøy caøng nhoû.
Khoâng phaûi chuùng ta luoân coù theå döï ñoaùn tröôùc hình daïng cuûa moät caây nhò
phaân tìm kieám tröôùc khi caây ñöôïc taïo ra, vaø caây ôû hình (b) laø moät caây ñieån hình
thöôøng coù nhaát so vôùi caây ôû hình (a). Trong caây naøy, vieäc tìm phaàn töû c caàn boán
laàn so saùnh, coøn hình (a) chæ caàn ba laàn so saùnh. Tuy nhieân, caây ôû hình (b) vaãn
coøn töông ñoái raäm raïp vaø vieäc tìm kieám treân noù chæ dôû hôn moät ít so vôùi caây toái
öu trong hình (a).
Hình 9.9 – Moät vaøi caây nhò phaân tìm kieám coù caùc khoùa gioáng nhau
Trong hình (c), caây ñaõ trôû neân suy thoaùi, vaø vieäc tìm phaàn töû c caàn ñeán 6 laàn
so saùnh. Hình (d) vaø (e) caùc caây ñaõ trôû thaønh chuoãi caùc maéc xích. Khi tìm treân caùc
chuoãi maéc xích nhö vaäy, tree_search khoâng theå laøm ñöôïc gì khaùc hôn laø duyeät
töø phaàn töû naøy sang phaàn töû kia. Noùi caùch khaùc, tree_search khi thöïc hieän treân
chuoãi caùc maéc xích nhö vaäy ñaõ suy thoaùi thaønh tìm tuaàn töï. Trong tröôøng hôïp xaáu
Giaùo trình Caáu truùc Döõ lieäu vaø Giaûi thuaät
202
Tải về để xem bản đầy đủ
54 trang
23400
Free
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Cấu trúc dữ liệu và giải thuật - Phần 2: Các cấu trúc dữ liệu - Chương 9: Cây nhị phân", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- giao_trinh_cau_truc_du_lieu_va_giai_thuat_phan_2_cac_cau_tru.pdf
