Arbori

Arbori

Definiţie. Se numeşte graf G = (X, V) o pereche formată din două mulţimi, mulţimea X a nodurilor sau vîrfurilor grafului, şi mulţimea V a muchiilor grafului, unde o muchie v V este o pereche ordonată de noduri v=(x,y), x,y X.Un graf neorientat este un graf în care perechea (x,y) se identifică cu perechea (y,x). Un graf fără cicluri este un graf în care, pornind de la un vîrf dat nu putem ajunge din nou la el folosind muchii.

Definiţie. Se numeşte arbore un graf H = (X, V) care este neorientat, conex, fără cicluri, cu un nod precizat numit rădăcină. Pentru orice vârf x X , există un număr finit de vârfuri x1,...,xn X asociate lui x, numite descendenţi direcţi (sau fiii) lui x.

Arbori - def. recursiva

O structură de arbore (k-arbore), T, de un anume tip de bază este (a) fie o structură vidă (adică T = );(b) fie este nevidă, deci conţine un nod de tipul de bază, pe care-l vom numi rădăcină şi îl vom nota root(T), plus un număr finit de structuri disjuncte de arbori de acelaşi tip, T1, T2, …, Tk, numiţi subarborii lui T (sau fiii lui root(T)).

Reprezentarea ca graf a unui k-arbore:

root(T)

T1 T2 Tk

Fig.3.1.1. Un k-arbore T, cu nodul rădăcină root(T) şi fii săi, T1 , T2 ,…,Tk .

Arbori - reprezentari

B C D

E F G H I J

A

Fig.3.1.3. Relaţii de incluziune modelate cu 3-arbori.

- graf: relatia tata-fiu reprezentata ca muchie sau arc

- expresie de liste de fii

Arbori - terminologie

arborii ordonaţi, arbori în care există o relaţie de ordine între descendenţii unui nod

arborii neordonaţi, arbori în care nu există o relaţie de ordine între descendenţii unui nod

Arbori - terminologie

gradul arborelui = întregul k care reprezintă numărul maxim de fii ai unui nod.

Fiecărui nod al arborelui îi vom asocia un nivel în felul următor:(a)rădăcina se află la nivelul 0,(b)dacă un nod se află la nivelul i atunci fiii săi sunt la nivelul i+1.

Numim înălţime (sau adâncime) a unui arbore nivelul maxim al nodurilor sale.

Se numeşte terminal sau frunză un nod fără descendenţi.Se numeşte nod interior orice nod care nu e terminal.

Un 2-arbore ordonat se numeşte arbore binar. (fiu stâng, respectiv fiu drept.)

Arbori - tipuri de legaturi

Reprezentarea unui arbore cu legătură tată - fiu: din fiecare nod, avem acces la oricare dintre fii. (pentru arbori ordonaţi, pentru arbori la care accesul la noduri se face "de sus în jos”)

Cu legături de tip tată (fiecare nod "ştie" cine este tatăl său) se pot reprezenta arbori neordonaţi. (tip de legătură frecvent pentru probleme în care nodurile arborelui reprezintă elementele unei mulţimi şi suntem interesaţi să facem operaţii pe mulţimi: teste de apartenenţă şi reuniuni de mulţimi)

Un alt tip de reprezentare este cu tip de legătură fiu - frate. Aceasta înseamnă că pentru fiecare nod al arborelui avem acces la primul său fiu şi la fraţii săi. (Nodurile de pe acelaşi nivel se numesc fraţi şi îi organizăm ca listă.)

Fig.3.1.5. Figura (b) reprezintă arborele binar asociat canonic 3-arborelui din figura (a). S-au folosit legăturile primul fiu şi frate (reprezentate prin săgeţi punctate în figura (a)). Legătura “primul fiu” din arborele iniţial devine legătură de tip fiu stâng, iar legătura “frate” devine legătură de tip “fiu drept” în arborele binar asociat canonic.

C B

A

D

H G I F E J

(a)

Putem trece în mod canonic de la un k-arbore T (reprezentat cu legătură tată - fii) la un arbore binar care se va numi arbore binar canonic asociat lui T transformând "primul fiu" în fiu stâng şi legătura la frate în fiu drept.Prin trecerea la arborele binar canonic asociat putem transfera probleme de k-arbori la arbori binari.

Arbori (oarecari) - traversariSe presupune data o reprezentare in care fiecare nod are trei câmpuri: info: pentru informaţia din noduri nrfii: valoarea NF, întreagă, reprezintă numărul de fii ai nodului fii: vector de dimensiune NF, cu componente pointeri, astfel încât, fii[J] este pointer către fiul J al nodului, iar J= 1,2,…,NF.

Algoritmul de traversare este următorul:

1. Se porneşte de la rădăcină.2. La fiecare nod curent: (a) se procesează info (b) se introduc într-o structură ajutătoare fiii nodului curent în vederea procesării ulterioare.3. Se extrage din structura ajutătoare un alt nod şi se reia de la punctul 2.

Ca structură ajutătoare putem folosi una dintre structurile liniare pe care le cunoaştem, stiva sau coada.Dacă folosim o coadă obţinem traversarea în lăţime (breadth first) a arborelui.Dacă folosim o stivă obţinem traversarea în adâncime (depth first) a arborelui.

Arbori (oarecari) - traversare in latime

procedure TravLat(Root){traversarea în lăţime a arborelui Root, folosind o coadă Queue şi procedurile QINSERT(Queue, ) pentru inserare în coadă, respectiv, QDELETE(Queue, ) pentru ştergere din coadă} Queue {iniţializarea cozii} if Root <> nil then QINSERT (Queue, Root) endif while Queue do QDELETE (Queue, NodCrt) {procesează NodCrt. info} for K:= 1 to NodCrt .nrfii do QINSERT(Queue, NodCrt .fii[K] ) endfor endwhileendproc

Arbori (oarecari) - traversare in adancime

procedure TravAd(Root){traversarea în adâncime a unui arbore, Root, folosind o stivă STACK, cu procedurile PUSH (STACK, ) şi POP (STACK, ) pentru introducere, respectiv extragere din stivă} STACK {iniţializarea stivei} if Root <> nil then PUSH (STACK, Root) endif while STACK do POP (STACK, NodCrt) {procesează NodCrt . Info} for K:= NodCrt .nrfii downto 1 do PUSH (STACK, NodCrt .fii[K]) endfor endwhileendproc

Arbori binari

Un arbore binar (2-arbore ordonat) T este:(1) fie un arbore vid (T=).(2) fie e nevid, şi atunci conţine un nod numit rădăcină, împreună cu doi subarbori binari disjuncţi numiţi subarborele stâng, respectiv subarborele drept.

Arbori binari

Fig.3.2.1. Arborele binar ce reprezintă expresia aritmetică (a+(b / c))*(d-(e*f)).

*

e f

*

+ -

/ a

b

d

c

Exemplu - reprezentari expresii aritmetice

• în Preordine (RSD) (Rădăcină Stânga Dreapta)

• în Inordine (SRD) (Stănga Rădăcină Dreapta)

• în Postordine (SDR)(Stănga Dreapta Rădăcină)

Arbori binari - traversari in adancime

Arbori binari - trav. in preordine

Procedure PreOrdine(Root){RSD}Stack {iniţializarea stivei Stack cu stiva }p: = Root {iniţializare pointerului curent}

while p <> nil do (A) repeat

1) {procesează p.info}2) if p.right <> nil then

PUSH (Stack, p.right)endif

3) p: = p.leftuntil p = nil

(B) if Stack <> then POP (Stack, p)

endifendwhile

endproc

Arbori binari - trav. in inordineProcedure InOrdine(Root); {SRD}

Stack p: = Root

do while p <> nil do {pun câte un nod în stivă şi mă deplasez la stânga, cât pot} PUSH (Stack,p) p: = p.left

endwhile repeat

if Stack <> then{extrag câte un nod din stivă şi-l procesez}

POP(Stack, p){procesează p.info}

else return {ieşire din do..repeat}endif

until p.right <> nil {până la primul care are fiu drept} p: = p.right {mă duc un pas la dreapta şi reiau ciclul do..repeat} repeatendproc

Arbori binari - trav. in postordineprocedure PostOrdine(Root) {SDR}

Stack p: = Rootdo (1) while p <> nil and p.left <> nil do

PUSH (Stack, p)p: = p.left

endwhile(2) while p.right = nil do

repeat{procesează p.info}if Stack <> then

Old: = p POP (Stack, p)

else return {ieşire din do..repeat}endif

until Old = p.leftendwhile

(3) PUSH (Stack, p)(4) p: = p.right repeat

endproc

Arbori binari însăilaţi (a) (b)

D A H F

G B

E

C

D A H F

G B

E

C

Fig.3.2.4. Arbore binar însăilat în inordine (b): Pointerii care aveau valoarea nil în (a) au fost setaţi în felul următor: legăturile

de tip left (fiu stâng) către nodul predecesor în inordine, iar legăturile de tip right (fiu drept) către nodul succesor în inordine.