Structuri de Date și Analiza Algoritmilor

8. Arbori

8.1. Arbori generalizaţi

8.1.1. Definiţii

În definirea noţiunii de arbore se porneşte de la noţiunea de vector.

Fie V o mulţime având elementele a1, a2,....an.

Pe mulţimea V se poate defini o aşa numită "relaţie de precedenţă" în felul următor: se spune că ai precede pe aj dacă i < j. Aceasta se notează: aipaj.

Se poate verifica uşor că relaţia astfel definită are următoarele proprietăţi, valabile pentru structura de vector:

(1) Oricare ar fi a∈V avem aa. (S-a notat cu relaţia "nu precede");

pp

(2) Dacă apb şi bpc atunci ac (tranzitivitate); [8.1.1.a] p

(3) Oricare ar fi a∈V şi b∈V, dacă a≠b atunci avem fie ab fie ba. pp

Din proprietăţile (1) şi (2) rezultă că relaţia de precedenţă nu determină în V ”bucle închise”, adică nu există nici o secvenţă de elemente care se preced două câte două şi în care ultimul element este acelaşi cu primul, cum ar fi de exemplu abcda. pppp

Proprietatea (3) precizează că relaţia de precedenţă este definită pentru oricare două elemente a şi b ale lui V, cu singura condiţie ca a≠b.

Fie V o mulţime finită peste elementele căreia s-a definit o relaţie de precedenţă, stabilind referitor la fiecare pereche de elemente, care dintre ele îl precede pe celalălalt.

Dacă această relaţie posedă proprietăţile [8.1.1.a], atunci ea imprima peste mulţimea V o structură de vector (fig.8.1.1.a).

a b cde

Fig. 8.1.1.a. Structură de vector

În figura 8.1.1.b apare o altă reprezentare intuitivă a unei structuri de vector. Săgeţile din figură indică relaţia "succesor".

a b c d e

Fig.8.1.1.b. Relaţia succesor

Această relaţie se defineşte cu ajutorul relaţiei de precedenţă după cum urmează: dacă între elementele a şi b ale lui V este valabilă relaţia ab şi nu există nici un c∈V astfel ca acb atunci se zice că b este succesorul lui a. ppp

Se observă că relaţia "succesor" (mulţimea săgeţilor din figura 8.1.1.b.), precizează relaţia "precedenţă" fără a fi însă identică cu ea. Spre exemplu, există relaţia be (prin tranzitivitate), dar nici o săgeată nu conectează pe b cu e. p

În figura8.1.1.c apare o aşa numită structură de arbore care se defineşte prin generalizarea structurii de vector.

b cdg hf e ijnol k m ap nivelul 1 nivelul 2 nivelul 3 nivelul 4 nivelul 5

Fig. 8.1.1.c. Structură de arbore

Astfel, dacă în cazul vectorului, toate elementele cu excepţia ultimului au exact un succesor, la structura de arbore se admite ca fiecare element să aibă un număr oarecare de succesori, inclusiv zero, cu restricţia ca două elemente distincte să nu aibă acelaşi succesor.

Relaţia succesor defineşte o relaţie de precedenţă pe structura de arbore. Astfel, din figura avem bp, dn, etc. pp

Relaţia de precedenţă definită pe structura de arbore se bucură de proprietăţile (1) şi (2) de la [8.1.1.a] dar nu satisface proprietatea (3).

Într-adevăr în figura 8.1.1.c, pentru elementele b şi c nu este valabilă nici una din relaţiile bc sau cb, la fel pentru elementele d şi k. Prin urmare, relaţia de precedenţă este definită numai pentru o parte a perechilor de elemente ale arborelui, cu alte cuvinte este o relaţie parţială. pp

În general, o structură de arbore se defineşte ca o mulţime A de n≤0 noduri de acelaşi tip, peste care s-a definit o relaţie de precedenţă având proprietăţile (1) şi (2) de la [8.1.1.a] precum şi următoarele două proprietăţi [8.1.1b]:

(3) Oricare ar fi b,c∈A, astfel încît bpc şi cb, dacă bd şi ce atunci d

pp≠e. Cu alte cuvinte, două elemente oarecare între care nu există relaţia de precedeţă nu pot avea acelaşi succesor. [8.1.1.b]

(4) Dacă A nu este vidă (n >0) atunci există un element numit rădăcină, care precede toate celelalte elemente.

Pentru structura de arbore se poate formula şi o altă definiţie echivalentă cu cea de mai sus.

Prin arbore, se înţelege o mulţime de n0 noduri de acelaşi tip, care dacă nu este vidă, atunci are un anumit nod numit rădăcină, iar restul nodurilor formează un număr finit de arbori, doi câte doi disjuncţi. ≥

Se constată că atât această definiţie, cât şi structura pe care o defineşte, sunt recursive, lucru deosebit de important deoarece permite prelucrarea simplă a unei astfel de structuri cu ajutorul unor algoritmi recursivi.