Arbori binari strictiProprietati si Aplicatii

Un arbore binar strict este un arbore binar n care fiecare nod are fie nici un fiu, fie exact doi fii. Nodurile cu doi copii se vor numi noduri interne, iar cele fr copii se vor numi noduri externe sau frunze. Ele pot fi de alt tip dect nodurile interne.

A

B

D

C

F

G

E

(a)

U

X

V

Z

Y

(b)

Fig.4.1.1. (a) Un arbore binar nestrict. (b) Arbore binar strict. sstrictstrict.

Completarea canonic a unui arbore binar oarecare T la unul strict se face n felul urmtor: se nlocuiete fiecare fiu vid al nodurilor din T cu un nod de tip special. Nodurile arborelui iniial T vor deveni toate noduri interne, iar cele adugate canonic vor fi frunze.Convenim s reprezentm grafic cu cercuri nodurile interne i cu dreptunghiuri nodurile externe.

Exemple de aplicaii ale structurii de arbore binar strictreprezentari de expresii aritmetice cu operatori binarialgoritmiproceduri de deciziecodificare binara

Proprietati ale arborilor binari strictiNE = numrul nodurilor externe iNI = numrul nodurilor interne ale unui arbore binar strict

Propoziia 1. ntr-un arbore binar strict, numrul nodurilor externe i al celor interne sunt legate prin relaia:NE = NI + 1.Demonstraie.

2NI = NI + NE 1,

NE = 2NI NI + 1 = NI + 1,

lungime extern a unui arbore binar strict = suma lungimilor drumurilor de la rdcin pn la fiecare nod extern. E = mulimea frunzelorr este rdcina, l(r, x) lungimea drumului de la r la nodul x.(Drumul de la rdcin la un nod se msoar n numr de arce.)lungime intern a unui arbore binar strict = suma lungimilor drumurilor de la rdcin la toate nodurile interioare. I = mulimea nodurilor interioare

Propoziia 2. ntr-un arbore binar strict este adevrat relaiaLE = LI + 2NI .Demonstraie. inducie dup n = numrul total de noduri ale unui arbore binar strict. (tim c n nu poate lua orice valoare din mulimea numerelor naturale.)(a) n = 1 ...(b) Presupunem c relaia LE = LI + 2NI este adevrat pentru orice arbore binar strict care are un numr total de noduri mai mic dect un numr natural m dat, deci pentru orice n < m.Fie un arbore binar strict T cu numrul total de noduri n, n < m. T este compus dintr-un nod rdcin, intern, i fiii si stng i drept, Ts i Td, care sunt la rndul lor subarbori binari strici. Notam cu NIs, NEs, LIs, LEs caracteristicile lui Ts i cu NId, NEd, LId, LEd caracteristicile lui Td(1) NI = NIs + NId + 1(2) NE = NEs + NEd(3) LE = LEs + NEs + LEd + NEd(4) LI = LIs + NIs + LId + NId(5) LEs = LIs + 2NId(6) LEd = LId + NIdLE = LEs + NEs + LEd + NEd = LIs + NIs + NEs + LId + NId + NId + NEd = (LIs + NIs + LId + NId) + (2NIs + 1) + (2NId + 1)

LE = LI + 2(NIs + NId = 1) = LI + 2NI

Propoziia 3. ntr-un arbore binar strict de adncime d avem urmtoarea inegalitateDemonstraie. Inegalitatea din enun revine la demonstrarea urmtoarelor afirmaii:1. Dintre toi arborii binari strici de adncime dat, d, cel cu numr maxim de frunze este cel care are toate frunzele la ultimul nivel (adic d).2. Un arbore cu toate frunzele la nivelul d are exact 2d frunze, adic NE = 2d.(inductie pt. (2)): d = 0 (ipot. ind.) d = k, numrul de frunze (aflate toate la nivelul k) este NE = 2k.Putem construi dintr-un asemenea arbore, n mod foarte simplu i direct, un arbore binar strict care are adncime d = k + 1 i proprietatea c toate frunzele sunt la nivelul k + 1. Se nlocuiete fiecare frunz de la nivelul k, cu un nod interior, iar acestora li se ataeaz cte dou frunze, procedeu care produce un arbore cu de dou ori mai multe frunze dect precedentul. Deci, pentru arborele de adncime k + 1 i toate frunzele la acest nivel avem NE = 2 * 2k = 2k+1

Corolar. ntr-un arbore binar strict de adncime d avem inegalitatea

Propoziia 4. Dintre toi arborii binari strici cu acelai numr de frunze, fixat, NE, au lungime extern minim aceia cu proprietatea c frunzele lor sunt repartizate pe cel mult dou niveluri adiacente.LE = LE (2d k) + [2(k + 1) + (d 1)]LE LE = 2d k + 2k + 2 + d 1 = d + k + 1 = (d k 1).Dar, din k = 2 este satisfcut i n-o mai putem aplica (cu acelai efect, micorarea strict a lungimii) pentru d k = 1

T

X

Y

d-1

d

k d-2

(A)

(B)

T'

Y

X

k

k+1

d-1

Propoziia 5. Lungimea extern minim a unui arbore binar strict cu l frunze este dat de formula(a) Cazul n care toate frunzele sunt la ultimul nivel, d. Atunci l = 2d, deci d = lg l (unde lg este notaia pentru logaritmul n baza 2).n cazul acesta, lungimea extern este dat de formulaLE = l * d = l * lg l,Unde n partea dreapt avem exact valoarea expresiei din enun, deoarece l 2lg l = l 2d = 0.

LEmin =

l

+ 2(l-

).

_1055068864.unknown

_1055068991.unknown

_1055068741.unknown

Propoziia 6. ntr-un arbore binar strict avem urmtoarea inegalitate:Demonstraie. Prin lungime medie nelegem media raportat la numrul de frunze. Deoarece am estimat n Propoziia 5 lungimea minim, putem estima acum media ei i obinem

LEmedie

.

_1055069298.unknown

LEmedie LEmin/l >

.

_1055069502.unknown

LEmin/l

+ 2(l

)/l.

_1055069332.unknown

_1055069371.unknown

Aplicatie a structurii de arbore binar strict la demonstrarea rezultatului privind limita inferioara a algoritmilor de sortare bazati pe comparatii intre chei

Clasa algoritmilor de sortare bazati pe comparatii intre cheisortarea direct prin inseriesortarea direct prin selecia minimului (sau maximului)sortarea direct prin interschimbaresortarea rapid (QuickSort)sortarea cu ansamble (HeapSort)complexitatea algoritmilor de mai sus se estimeaz n mod esenial n funcie de numrul de comparaii intre elementele multimii de sortat.-- primii trei algoritmi de mai sus au o complexitate de ordinul lui n2 -- sortarea rapid i sortarea cu ansamble au performane de ordinul lui n log2n.Aratam in continuare ca NU se poate cobori sub acesta limita (in aceasta clasa).

Teorem. Orice algoritm de sortare a n chei, algoritm bazat pe comparaii ntre chei, va face cel puin:Demonstraie. Consideram algoritmi - datele de intrare sunt vectori de lungime n, (x1, x2, , xn), cu componentele presupuse distincte. - bazai pe comparaii de tipul xi < xj. Unui asemenea algoritm i se asociaz un arbore binar de decizie, care va fi arbore binar strict: (a) o intruciune de ieire va fi o frunz ce conine vectorul sortat; (b) o comparaie xi < xj va fi un nod interior, al crui fiu stng este arborele asociat instruciunilor ce se execut dac xi < xj este adevrat, iar fiul drept este arborele asociat instruciunilor ce se execut dac xi < xj este fals.Numrul total al instruciunilor de ieire i deci al frunzelor va fi numrul total de ordini posibile pe vectorul (x1, , xn), deci n!.

Exemplu: arbore binar de decizie asociat unui algoritm de sortare a unei multimi cu n=3 elemente

Nu

DaA

DaA

DaA

DaA

Nu

DaA

Nu

Nu

Nu

a1

Pe un set particular de date de intrare, aciunea algoritmului este echivalent cu parcurgerea unui drum de la rdcin pn la frunza ce conine respectivul set de date ordonat. Numrul de comparaii efectuate = numrul de noduri interioare pe acest drum = lungimea acestui drum (msurat n arce).Numrul de comparaii pe care l face algoritmul n cazul mediu, revine la a estima numrul mediu de noduri interioare pe toate drumurile, cu alte cuvinte lungimea extern medie a arborelui binar strict de decizie asociat: (Propozitia 6) lungimea extern medie a unui asemenea arbore este mai mare dect Numrul de comparaii n cazul cel mai nefavorabil, revine la a estima numrul de noduri interioare pe drumul cel mai lung pn la o frunz = d = adncimea arborelui: (Corolar la Propozitia 3)