Chöông 10 – Caây nhieàu nhaùnh
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
237
Chöông 10 – CAÂY NHIEÀU NHAÙNH
Chöông naøy tieáp tuïc nghieân cöùu veà caùc caáu truùc döõ lieäu caây, taäp trung vaøo caùc
caây maø soá nhaùnh taïi moãi nuùt nhieàu hôn hai. Chuùng ta baét ñaàu töø vieäc trình baøy
caùc moái noái trong caây nhò phaân. Keá tieáp chuùng ta tìm hieåu veà moät lôùp cuûa caây goïi
laø trie ñöôïc xem nhö töø ñieån chöùa caùc töø. Sau ñoù chuùng ta tìm hieåu ñeán caây B-tree
coù yù nghóa raát lôùn trong vieäc truy xuaát thoâng tin trong caùc taäp tin. Moãi phaàn
trong soá naøy ñoäc laäp vôùi caùc phaàn coøn laïi. Cuoái cuøng, chuùng ta aùp duïng yù töôûng
cuûa B-tree ñeå coù ñöôïc moät lôùp khaùc cuûa caây nhò phaân tìm kieám goïi laø caây ñoû-ñen
(red-black tree).
10.1. Vöôøn caây, caây, vaø caây nhò phaân
Nhö chuùng ta ñaõ thaáy, caây nhò phaân laø moät daïng caáu truùc döõ lieäu ñôn giaûn vaø
hieäu quaû. Tuy nhieân, vôùi moät soá öùng duïng caàn söû duïng caáu truùc döõ lieäu caây maø
trong ñoù soá con cuûa moãi nuùt chöa bieát tröôùc, caây nhò phaân vôùi haïn cheá moãi nuùt chæ
coù toái ña hai con khoâng ñaùp öùng ñöôïc. Phaàn naøy laøm saùng toû moät ñieàu ngaïc nhieân
thuù vò vaø höõu ích: caây nhò phaân cung caáp moät khaû naêng bieåu dieãn nhöõng caây khaùc
bao quaùt hôn.
10.1.1. Caùc teân goïi cho caây
Tröôùc khi môû roäng veà caùc loaïi caây, chuùng ta xeùt ñeán caùc ñònh nghóa. Trong
toaùn hoïc, khaùi nieäm caây coù moät yù nghóa roäng: ñoù laø moät taäp baát kyø caùc ñieåm (goïi
laø ñænh), vaø taäp baát kyø caùc caëp noái hai ñænh khaùc nhau (goïi laø caïnh hoaëc nhaùnh)
sao cho luoân coù moät daõy lieân tuïc caùc caïnh (ñöôøng ñi) töø moät ñænh baát kyø ñeán moät
ñænh baát kyø khaùc, vaø khoâng coù chu trình, nghóa laø khoâng coù ñöôøng ñi naøo baét ñaàu
töø moät ñænh naøo ñoù laïi quay veà chính noù.
Ñoái vôùi caùc öùng duïng trong maùy tính, chuùng ta thöôøng khoâng caàn nghieân cöùu
caây moät caùch toång quaùt nhö vaäy, vaø khi caàn laøm vieäc vôùi nhöõng caây naøy, ñeå nhaán
maïnh, chuùng ta thöôøng goïi chuùng laø caùc caây töï do (free tree). Caùc caây cuûa chuùng
ta phaàn lôùn luoân coù moät ñænh ñaëc bieät, goïi laø goác cuûa caây, vaø caùc caây daïng naøy
chuùng ta seõ goïi laø caùc caây coù goác (rooted tree).
Moät caây coù goác coù theå ñöôïc veõ theo caùch thoâng thöôøng cuûa chuùng ta laø goác naèm
treân, caùc nuùt vaø nhaùnh khaùc quay xuoáng döôùi, vôùi caùc nuùt laù naèm döôùi cuøng. Maëc
duø vaäy, caùc caây coù goác vaãn chöa phaûi laø taát caû caùc daïng caây maø chuùng ta thöôøng
duøng. Trong moät caây coù goác, thöôøng khoâng phaân bieät traùi hoaëc phaûi, hoaëc khi moät
nuùt coù nhieàu nuùt con, khoâng theå noùi raèng nuùt naøo laø nuùt con thöù nhaát, thöù hai,
v.v...Neáu khoâng vì moät lyù do naøo khaùc, söï thi haønh tuaàn töï caùc leänh thöôøng buoäc
chaët moät thöù töï leân caùc nuùt con cuûa moät nuùt. Chuùng ta ñònh nghóa moät caây coù thöù
Chöông 10 – Caây nhieàu nhaùnh
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
238
töï (ordered tree) laø moät caây coù goác trong ñoù caùc con cuûa moät nuùt ñöôïc gaùn cho
moät thöù töï.
Löu yù raèng caùc caây coù thöù töï maø trong ñoù moãi nuùt coù khoâng quaù hai con vaãn
chöa phaûi cuøng moät lôùp vôùi caây nhò phaân. Neáu moät nuùt trong caây nhò phaân chæ coù
moät con, noù coù theå naèm beân traùi hoaëc beân phaûi, luùc ñoù ta coù hai caây nhò phaân
khaùc nhau, nhöng chuùng cuøng laø moät caây coù thöù töï.
Nhö moät nhaän xeùt cuoái cuøng lieân quan ñeán caùc ñònh nghóa, chuùng ta haõy löu yù
raèng caây 2-tree maø chuùng ta ñaõ nghieân cöùu khi phaân tích caùc giaûi thuaät ôû nhöõng
chöông tröôùc laø moät caây coù goác (nhöng khoâng nhaát thieát phaûi laø caây coù thöù töï) vôùi
ñaëc tính laø moãi nuùt trong caây coù 0 hoaëc 2 nuùt con.
Hình 10.1 cho thaáy raát nhieàu daïng caây khaùc nhau vôùi soá nuùt nhoû. Moãi lôùp caây
keå töø caây ñaàu tieân coù ñöôïc baèng caùch keát hôïp caùc caây töø caùc lôùp coù tröôùc theo
nhieàu caùch khaùc nhau. Caùc caây nhò phaân coù theå coù ñöôïc töø caùc caây coù thöù töï töông
öùng, baèng caùch phaân bieät caùc nhaùnh traùi vaø phaûi.
Hình 10.1 - Caùc da
ï
n
g
khaùc nhau cuûa caâ
y
.
Chöông 10 – Caây nhieàu nhaùnh
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
239
10.1.2. Caây coù thöù töï
10.1.2.1. Hieän thöïc trong maùy tính
Neáu chuùng ta muoán söû duïng moät caây coù thöù töï nhö moät caáu truùc döõ lieäu, moät
caùch hieån nhieân ñeå hieän thöïc trong boä nhôù maùy tính laø môû roäng caùch hieän thöïc
chuaån cuûa moät caây nhò phaân, vôùi soá con troû thaønh vieân trong moãi nuùt töông öùng
soá caây con coù theå coù, thay vì chæ coù hai nhö ñoái vôùi caây nhò phaân. Chaúng haïn,
trong moät caây coù moät vaøi nuùt coù ñeán möôøi caây con, chuùng ta caàn phaûi giöõ ñeán
möôøi con troû thaønh vieân trong moät nuùt. Nhöng nhö vaäy seõ daãn ñeán vieäc caây phaûi
chöùa moät soá raát lôùn caùc con troû chöùa trò NULL. Chuùng ta coù theå tính ñöôïc chính
xaùc con soá naøy. Neáu caây coù n nuùt, moãi nuùt coù k con troû thaønh vieân, thì seõ coù taát caû
laø n x k con troû. Moãi nuùt coù chính xaùc laø moät con troû tham chieáu ñeán noù, ngoaïi tröø
nuùt goác. Nhö vaäy coù n-1 con troû khaùc NULL. Tæ leä caùc con troû NULL seõ laø:
> 1 -
Neáu moät nuùt coù theå coù möôøi caây con, thì coù hôn 90% con troû laø NULL. Roõ raøng
laø phöông phaùp bieåu dieãn caây coù thöù töï naøy hao toán raát nhieàu vuøng nhôù. Lyù do laø
vì, trong moãi nuùt, chuùng ta ñaõ giöõ moät danh saùch lieân tuïc caùc con troû ñeán taát caû
caùc con cuûa noù, vaø caùc danh saùch lieân tuïc naøy chöùa quaù nhieàu vuøng nhôù chöa ñöôïc
söû duïng. Chuùng ta caàn tìm caùch thay theá caùc danh saùch lieân tuïc naøy bôûi caùc danh
saùch lieân keát.
10.1.2.2. Hieän thöïc lieân keát
Ñeå naém caùc con cuûa moät nuùt trong moät danh saùch lieân keát, chuùng ta caàn hai
loaïi tham chieáu. Thöù nhaát laø tham chieáu töø nuùt cha ñeán nuùt con ñaàu tieân beân traùi
cuûa noù, chuùng ta seõ goïi laø first_child. Thöù hai, moãi nuùt, ngoaïi tröø nuùt goác, seõ
xuaát hieän nhö moät phaàn töû trong danh saùch lieân keát naøy, do ñoù noù caàn theâm moät
tham chieáu ñeán nuùt keá trong danh saùch, nghóa laø tham chieáu ñeán nuùt con keá tieáp
cuøng cha. Tham chieáu thöù hai naøy ñöôïc goïi laø next_sibling. Hieän thöïc naøy ñöôïc
minh hoïa trong hình 10.2.
(n x k)
–
(n
–
1)
⎯⎯⎯⎯⎯⎯⎯
n x k
1
⎯
k
Hình 10.2 – Hieän thöïc lieân keát cuûa caây coù thöù töï
Chöông 10 – Caây nhieàu nhaùnh
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
240
10.1.2.3. Söï töông öùng töï nhieân
Ñoái vôùi moãi nuùt cuûa caây coù thöù töï chuùng ta ñaõ ñònh nghóa hai tham chieáu
first_child vaø next_sibling. Baèng caùch söû duïng hai tham chieáu naøy chuùng ta
coù ñöôïc caáu truùc cuûa moät caây nhò phaân, nghóa laø, hieän thöïc lieân keát cuûa moät caây coù
thöù töï laø moät caây nhò phaân lieân keát. Neáu muoán, chuùng ta coù theå coù ñöôïc moät hình
aûnh deã nhìn hôn cho caây nhò phaân baèng caùch söû duïng hieän thöïc lieân keát cuûa caây
coù thöù töï vaø quay theo chieàu kim ñoàng hoà moät goùc nhoû, sao cho caùc tham chieáu
höôùng xuoáng (first_child) höôùng sang traùi, vaø caùc tham chieáu naèm ngang
(next_sibling) höôùng sang phaûi. Ñoái vôùi hình 10.2, chuùng ta coù ñöôïc caây nhò
phaân ôû hình 10.3.
10.1.2.4. Söï töông öùng ngöôïc laïi
Giaû söû nhö chuùng ta laøm ngöôïc laïi caùc böôùc cuûa quaù trình treân, baét ñaàu töø moät
caây nhò phaân vaø coá gaéng khoâi phuïc laïi moät caây coù thöù töï. Ñieàu quan saùt ñaàu tieân
chuùng ta caàn nhaän thaáy laø khoâng phaûi moïi caây nhò phaân ñeàu coù theå coù ñöôïc töø
moät caây coù thöù töï bôûi quaù trình treân: do tham chieáu next_sibling cuûa nuùt goác
cuûa caây coù thöù töï luoân baèng NULL neân goác cuûa caây nhò phaân töông öùng luoân coù caây
con beân phaûi roãng. Ñeå tìm hieåu söï töông öùng ngöôïc laïi naøy moät caùch caån thaän,
chuùng ta caàn phaûi xem xeùt moät lôùp caáu truùc döõ lieäu khaùc qua moät soá ñònh nghóa
môùi döôùi ñaây.
Hình 10.3 – Hình ñaõ ñöôïc quay cuûa hieän thöïc lieân keát
Chöông 10 – Caây nhieàu nhaùnh
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
241
10.1.3. Röøng vaø vöôøn
Trong quaù trình tìm hieåu veà caây nhò phaân chuùng ta ñaõ coù kinh nghieäm veà caùch
söû duïng ñeä quy, ñoái vôùi caùc lôùp khaùc cuûa caây chuùng ta cuõng seõ tieáp tuïc laøm nhö
vaäy. Söû duïng ñeä quy coù nghóa laø thu heïp vaán ñeà thaønh vaán ñeà nhoû hôn. Do ñoù
chuùng ta neân xem thöû ñieàu gì seõ xaûy ra neáu chuùng ta laáy moät caây coù goác hoaëc
moät caây coù thöù töï vaø caét boû ñi nuùt goác. Nhöõng phaàn coøn laïi, neáu khoâng roãng, seõ
laø moät taäp caùc caây coù goác hoaëc moät taäp coù thöù töï caùc caây coù thöù töï töông
öùng.
Thuaät ngöõ chuaån ñeå goïi moät taäp tröøu töôïng caùc caây ñoù laø röøng (forest), nhöng
khi chuùng ta duøng thuaät ngöõ naøy, noùi chung chuùng ta thöôøng hình dung ñoù laø caùc
caây coù goác. Cuïm töø “röøng coù thöù töï” (ordered forest) ñoâi khi coøn ñöôïc söû duïng ñeå
goïi taäp coù thöù töï caùc caây coù thöù töï, do ñoù chuùng ta seõ ñeà cöû moät thuaät ngöõ coù
tính ñaëc taû töông töï cho lôùp caùc caây coù thöù töï, ñoù laø thuaät ngöõ vöôøn (orchard).
Löu yù raèng chuùng ta khoâng chæ coù ñöôïc moät röøng hoaëc moät vöôøn nhôø vaøo
caùch loaïi boû ñi nuùt goác cuûa moät caây coù goác hoaëc moät caây coù thöù töï, chuùng ta
coøn coù theå taïo neân moät caây coù goác hoaëc moät caây coù thöù töï baèng caùch baét ñaàu töø
moät röøng hoaëc moät vöôøn, theâm moät nuùt môùi taïi ñænh, vaø noái caùc nhaùnh töø nuùt
môùi naøy ñeán goác cuûa taát caû caùc caây trong röøng hoaëc vöôøn ñoù. Caùch naøy ñöôïc minh
hoïa trong hình 10.4.
Chuùng ta seõ söû duïng quaù trình naøy ñeå ñöa ra moät ñònh nghóa ñeä quy môùi cho
caùc caây coù thöù töï vaø caùc vöôøn. Tröôùc heát, chuùng ta haõy xem thöû neân baét ñaàu nhö
theá naøo. Chuùng ta nhôù raèng moät caây nhò phaân coù theå roãng. Moät röøng hay moät
vöôøn cuõng coù theå roãng. Tuy nhieân moät caây coù goác hay moät caây coù thöù töï khoâng theå
laø caây roãng, vì noù phaûi chöùa ít nhaát laø moät nuùt goác. Neáu chuùng ta muoán baét ñaàu
xaây döïng caây vaø röøng, chuùng ta coù theå löu yù raèng moät caây vôùi chæ moät nuùt coù theå
coù ñöôïc baèng caùch theâm moät goác môùi vaøo moät röøng ñang roãng. Moät khi chuùng ta
ñaõ coù caây naøy roài thì chuùng ta coù theå taïo ñöôïc moät röøng goàm bao nhieâu caây moät
nuùt cuõng ñöôïc. Sau ñoù chuùng ta coù theå theâm goác môùi ñeå taïo caùc caây coù goác chieàu
Hình 10.4 – Loaïi boû vaø theâm nuùt goác.