Tài liệu Cấu trúc dữ liệu (chương 9) docx

Chöông 9 – Caây nhò phaân

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

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.

(a)

M

- A

- - N

- - C

- - - B M ( A ( N C ( B ) ) D O ( Y ( T X ) E L S ) )

- D (c)

- O

- - Y

- - - T

- - - X

- - E

- - L

- - S

(b)

Hình 9.1 – Caùc caùch bieåu dieãn cuûa caây

M

A

N C Y

D O

E L S

B T X

Chöông 9 – Caây nhò phaân

Giaùo trình Caáu truùc Döõ lieäu vaø Giaûi thuaät 184

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:

Chöông 9 – Caây nhò phaân

Giaùo trình Caáu truùc Döõ lieäu vaø Giaûi thuaät 185

Ñò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æ

Chöông 9 – Caây nhò phaân

Giaùo trình Caáu truùc Döõ lieäu vaø Giaûi thuaät 186

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.

Chöông 9 – Caây nhò phaân

Giaùo trình Caáu truùc Döõ lieäu vaø Giaûi thuaät 187

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û.

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

Hình 9.3 – Caây nhò phaân ñaày ñuû vôùi 31 nuùt.