Arbori

Arbori

Reprezentarea arborilor de grad oarecare in limbajul C

[1] Reprezentarea 'standard'

In reprezentarea standard in fiecare nod al arborelui, pe inga informatia utila se memoreaza informatii de inlantuire care indica descendentii.

Intr-o prima varianta de reprezentare, fiecare nod este compus din informatia utila si un vector de dimensine fixa, in care se memoreaza legaturilor de tip pointer la descendenti. Dimensiunea acestui vector este data gradul maxim al nodurilor arborelui. Declaratiile de tip folosite de aceasta reprezentare sint:

struct Nod;

Un nod va ocupa o zona de memorie de dimensiune fixa:

data vDesc (GRMAX=3)

+-------- ----- ------ ---+

| | | | |

+-------- ----- ------ ---+

vDesc[1] vDesc[2] vDesc[3]

In figura de mai jos am reprezentat inlantuirile pentru arborele:

a

/ |

b c d

/

e f g

+-----------+

| a |

|-----------|

| _ | _ | _ |

+-+---+---+-+

+----- ----- ------+ +----- ----- ---------+

+-----------+ +-----------+ +-----------+

| b | | c | | d |

|-----------| |-----------| |-----------|

| 0 | 0 | 0 | | _ | _ | 0 | | _ | 0 | 0 |

+-----------+ +-+---+-----+ +-+---------+

+--+ +------+

+-----------+ +-----------+ +-----------+

| e | | f | | g |

|-----------| |-----------| |-----------|

| 0 | 0 | 0 | | 0 | 0 | 0 | | 0 | 0 | 0 |

+-----------+ +-----------+ +-----------+

In aceasta reprezentare, daca p este un pointer la un nod descendentul i al nodului va fi identificat direct prin pointerul p->vDesc[i]

Intr-un arbore cu un numar N de noduri vor exista N-1 muchii, deci in total N-1 elemente din vectorii de pointeri la descendenti sint ocupate cu informatie utila. Se obtine raportul:

N-1 1

--------- ~ -----

N * GRMAX GRMAX

care indica gradul de utilizare eficienta a memoriei. In consecinta aceasta reprezentare este acceptabila numai pentru arbori de grad mic.   

[2] Reprezentarea 'FIU-FRATE'

Pentru a obtine o utilizare mai eficienta a memoriei, pot fi tilizate listele de descendenti. Fiecare nod va contine pe linga informatia utila, doi pointeri: unul va indica lista cu descendentii sai iar cel de-al doilea urmatorul nod din lista de descendenti din care face parte.

struct Nod ;

In aceasta varianta arborele de mai sus va avea urmatoarea reprezentare:

data desc next

+-------------+

| a | | | 0 |

+-------+-----+

+-------------+ +-------------+ +-------------+

+->| b | 0 | |-+---->| c | | | |-+---->| d | | | 0 |

+-------------+ +-------+-----+ +-------+-----+

| +-------------+ +-------------+ | +-------------+

+->| e | 0 | |-+-->| f | 0 | 0 | +->| g | 0 | 0 |

Avind in vedere semnificatia pointerilor continuti intr-un nod aceasta reprezentare se mai numeste 'reprezentarea FIU-FRATE'.

In aceasta reprezentare, daca p este un pointer la un nod identificarea descendentul i al nodului va necesita parcurgerea listei inlantuite a descendentilor, lista care incepe cu:

p->desc

[3] Reprezentarea prin noduri de dimensiune variabila

O a treia solutie de reprezentare combina economia de memorie cu avantajele accesarii descendentilor pe baza de index. Aceasta solutie se bazeaza pe posibilitatea de a aloca blocuri de memorie de lungime precizata.

Vom considera aceeasi declaratie pentru tipul Nod ca si in prima varinata de reprezentare, adugind in plus un cimp in care sa se memoreze gradul nodului.

struct Nod;

Economia de memorie se va realiza prin alocarea unor zone de memorie de lungime variabila, adaptata gradului fiecarui nod. Iata cum vor arata:

- Un nod de grad 3:

data grad vDesc

+-------- ----- ------ -------+

| | 3 | | | |

+-------- ----- ------ -------+

vDesc[1] vDesc[2] vDesc[3]

- Un nod de grad 1:

data grad vDesc

+----- ----- ------------+

| | 1 | |

+----- ----- ------------+

vDesc[1]

- Un nod terminal:

data grad

+-------------+

| | 0 |

+-------------+

Pentru a realiza economia de memorie este necesar ca la alocarea spatiului pentru un nod sa se cunoasca numarul de descendenti si in functie de acest numar sa se aloce spatiul necesar pentru vectorul de descendenti. Iata cum trebuie scrisa functia make_nod care aloca spatiu pentru un nod de grad dat:

Nod* make_nod(int grad)

Utilizind operatorul new, specific limbajului C++ alocarea va avea forma:

Nod* p = (Nod*) new char[sizeof(Nod)-(GRMAX-grad)*sizeof(Nod*)];

Iata cum va arata, in aceasta varianta, reprezentarea arborelui dat:

+----- ----- ---------+

| a |3| _ | _ | _ |

+---------+---+---+-+

+----- ----- --------+ +----- ----- -----+

| b |0| | c |2| _ | _ | | d |1| _ |

+---+ ++

+-------+ +-------+ +-------+

| e |0| | f |0| | g |0|

+-------+ +-------+ +-------+

Arbori binari

Reprezentarea standard

In reprezentarea standard, un nod al arborelui este o structura cu un cimp continind eticheta nodului (data) si doua cimpuri pointeri la cei doi descendenti (lchild si rchild):

data stg drt

+----- ----- --------- ----- -----+

| | | |

+----- ----- --------- ----- -----+

struct Nod

Astfel, arborele: A

/

B C

/

D E F

va avea urmatoarea reprezentare:

+-----------+

| A | _ | _ |

+-----+---+-+

+->| B |nil| _ | +->| C | _ | _ |

+->| D |nil|nil| +->| E |nil|nil| +->| F |nil|nil|

Pentru a putea prelucra un arbore este suficient sa cunostem un pointer la nodul radacina. Valoarea nil pentru acest pointer va semnifica un arbore vid.

Pacurgeri

Un arbore binar poate fi privit conform urmatoarei scheme recursive:

+-----+

| rad | rad = radacina

+-----+ SAS = SubArbore Sting

/ SAD = SubArbore Drept

/

+-----+ +-----+

| SAS | | SAD |

+-----+ +-----+

Pe aceasta schema se definesc cele trei moduri de parcurgere a arborelui:

PREORDINE : rad SAS SAD

Se prelucreaza mai intii radacina apoi se parcurg in preordine subarborii sting si drept.

INORDINE : SAS rad SAD

Se parcurge in inordone subarborele sting, se prelucreaza radacina si apoi se pparcurge in inordine subarborele drept.

POSTORDINE : SAS SAD rad

Se parcurg mai intii in postordine subarborii sting si drept apoi se prelucreaza radacina.

Pentru arborele:

A

/

B C

/

D E F

cele trei parcurgeri prelucreaza nodurile in ordinea:

PREORDINE: A B D C E F

INORDINE: B D A E C F

POSTORDINE: D B E F C A

Putem realiza aceste parcurgeri utilizind subrutine recursive. De exemplu:

void PREORDINE(pNod p);

}

sau

void PREORDINE(Nod* p);

A doua varianta nu poate fi aplicata unui arbore vid, in timp ce prima trateaza corect arborele vid, in schimb executa un apel recursiv in plus pentru fiecare legatura care este NULL.

| Exemplu | O functie care sa calculeze valoarea maxima dintr-un arbore.

Varianta 1

char max ; // max este variabila globala

void CautaMax(Nod* p)

}

char ValMax(Nod* p)

Functia Valmax apeleaza o procedura recursiva CautaMax care face o parcurgere prin arbore testind valoarea fiecarui nod. La sfirsitul parcurgerii, variabila 'max', care este o variabila globala (externa) pentru procedura recursiva, si care a fost initializata cu cea mai mica valoare de tip char, va contine valoarea maxima a etichetelor din arbore.

Varianta 2

Pronind de la schema:

+-----+

| rad |

+-----+

/

+-----+ +-----+

| SAS | | SAD |

+-----+ +-----+

stabilim urmatoarea definitie recursiva:

ValMax(arbore) = max(rad, ValMax(SAS), ValMax(SAD))

Apelurile ValMax(SAS) si ValMax(SAD) se vor executa numai daca subarborii nu sint vizi.

Iata implementarea:

char max(char v1,char v2)

char ValMax(pNod rad)

Aceasta varianta nu se poate aplica unui arbore vid, dar are avantajul ca se poate aplica si in cazuri in care nu exista o valoare de eticheta pentru nod mai mica decit toate etichetele posibile (cum am folosit mai sus, valoarea 0).

Arbori binari de cautare

Introducere

Arborii binari de cautare sint o implementare a tipului de date abstract numit 'dictionar'. Elementele unui dictionar pot fi ordonate, criteriul de sortare fiind dat de 'cheia de sortare' (sau cheie de cautare).

Arborii binari de cautare implementeaza eficient urmatoarele operatii:

search(arbore, k) - determina daca un element specificat prin cheia de sortare k, exista in arbore si-l returneaza daca exista.

insert(arbore, x) - insereaza in arbore elementul x.

delete(arbore, k) - sterge un element specificat, specificat prin cheia k.

Proprietatea care defineste structura unui arbore binar de cautare este urmatoarea: Valoarea cheii memorate in radacina este mai mare decit toate valorile cheilor continute in subarborele sting si mai mica decit toate valorile cheilor continute in subarborele drept.

Aceasta proprietate trebuie sa fie indeplinita pentru toti subarborii, de pe orice nivel in arborele binar de cautare.

Exemplu (am reprezentat pentru fiecare nod numai cheile de cautare):

20

/

13 45

/ /

5 17 33 90

/

Operatii de acces

Iata cum pot fi realizate prin niste functii recursive operatiile insert si search

insert(r,a) // r - pointer la radacina (trasmis prin referinta)

// a - atomul de inserat

make_nod(a) // creeaza un nod nou in care memoreaza atomul a

Pentru varianta de mai sus trebuie sa permitem functiei insert sa modifice valoarea argumentului r, pentru aceasta el va fi un parametru trensmis prin referinta. In implementarea C++ functia insert va avea prototipul:

void insert(Nod*& r, Atom a);

O varianta care nu necesita argument referinta (deci poate fi implementata in C) este data mai jos.

insert(r,a)

Apelul acestei variante va avea de fiecare data forma:

rad = insert(rad, a)

Procedura search intoarce pointer la nodul cu cheia de cautare data sau pointerul NULL daca nu exista nodul respectiv.

search(r,k)

Trebuie observat ca atit operatia search cit si operatia insert parcurg o ramura a arborelui (un lant de la radacina spre o frunza). Aceasta parcurgere poate fi efectuata iterativ. Este vorba de a parcurge o inlantuire, deci se impune o analogie cu parcurgerea listei inlantuite.

Parcurgerea listei inlantuite Parcurgerea unei ramuri in arbore

p=cap; p=rad;

while(p!=0) }

Procedura de inserare in arborele binar de cautare, realizata nerecursiv, are urmatoarea forma (presupunem ca r este parametru transmis prin referinta):

insert(r,a)

Stergerea unui nod intr-un arbore de cautare binar

In continuare vom scrie functia C++ pentru stergerea unei valori dintr-un arbore binar de cautare care contine numere intregi.

Pentru stergerea unei valori din arbore este necesara mai intii identificarea nodului care contine aceasta valoare. Vom folosi pentru aceasta tehnica prezentata la operatia search. Pentru simplitate consideram nodurile etichetate cu numere intregi care vor contitui chiar cheile de cautare (key(data(p) = data(p)).

struct Nod;

void delete(Nod*& rad, int a)

Am redus sarcina initiala la a scrie functia deleteRoot care sterge radacina unui arbore binar de cautare nevid.

Pentru aceasta avem urmatoarele cazuri:

| Atunci cind radacina nu are nici un descendent stergerea este o operatie imediata.

rad rad

| |-+----------||| ==> |nil|

pointerul un arbore

rad indica cu un nod ==> arbore vid

| Atunci cind radacina are un sigur descendent nodul sters va

fi inlocuit cu subarborele descendent.

rad rad

_||S A D||_

||| ==> |||||||||||||

_|||||_ -------------

_||S A D||_

|||||||||||||

-------------

sau

rad rad

/ _||S A S||_

||| |||||||||||||

_|||||_ -------------

_||S A S||_

| Atunci cind radacina are doi descendenti, ea va fi inlocuita cu nodul cu valoarea cea mai mare din subarborele sting, acest nod avind intotdeuana cel mult un descendent. Nodul cel mai mare dintr-un arbore (subarbore) binar de cautare se gaseste pornind din radacina si inaintind cit se poate spre dreapta. De exemplu:

/

13 45

/ /

5 17 33 90 <- Nodul cel mai mare

/ /

15 40

Deci:

rad rad

/ /

_|||||_ _|||||_ _|||||_ _|||||_

_||S A S||_ _||S A D||_ _||S A S||_ _||S A D||_

|||||||||||-| ||||||||||||| |||||||||| |||||||||||||

------------- ------------- ---------- -------------

Exemplu:

|20| <-Trebuie sters |17|

+--+ +--++--+ +--+ +--+ +--++--+ +--+

| 5| |17||33| |90| | 5| |15||33| |90|

+--+ +--++--+ +--+ +--+ +--++--+ +--+

/ / /

Urmatoarea functie detaseaza dintr-un arbore binar de cautare nevid nodul cu valoarea cea mai mare si intoarce pointer la acest nod.

Nod* removeGreatest(Nod*& r)

else return removeGreatest(r->rchild);

}

Varianta prezentata este recursiva. Se poate scrie usor si o

varianta nerecursiva pentru aceasta procedura.

Tinind cont de cazurile posibile prezentate procedura deleteRoot va trata separat cazurile:

- daca subarborele sting este vid: promoveaza subarborele drept. Cazul in care si subarborele drept este vid nu trebuie tratat separat, in acest caz se promoveaza arborele vid (rad devine NULL);

- altfel daca, subarborele drept este vid: promoveaza subarborele sting.

- altfel (ambii subarbori nu sint vizi): inlocuieste radacina cu cel mai mare nod din subarborele sting.

void deleteRoot(Nod*& rad)

delete p;