4. Arbori binari
Arbori
Un arbore cu rãdãcinã ("rooted tree") este o structurã neliniarã, în care fiecare nod poate avea mai multi succesori, dar un singur predecesor, cu exceptia nodului rãdãcinã, care nu are nic 515d310f i un predecesor. Structura de arbore se poate defini recursiv astfel: Un arbore poate fi :
- nimic (arbore vid)
- un singur nod (rãdãcina)
- un nod care are ca succesori un numar finit de arbori.
Altfel spus, dacã se eliminã rãdãcina unui arbore rezultã mai multi arbori, care erau subarbori în arborele initial (dintre care unii pot fi arbori fãrã nici un nod). Un arbore poate fi privit ca o extindere a unei liste liniare sau ca un caz particular de graf fãrã cicluri.
Structura de arbore este o structurã
ierarhicã, cu noduri asezate pe niveluri succesive, cu relatii de tip
"pãrinte-fiu" între noduri. Fiecare nod are o anumitã "înãltime" fatã de
rãdãcinã; toti succesorii unui nod se aflã pe acelasi nivel si au aceeasi
înãltime. Nodurile terminale, fãrã succesori, se numesc si "
Structurile arborescente se folosesc în programare deoarece:
- Reprezintã un model natural pentru o ierarhie de obiecte, de persoane, de operatii, de functii;
- Permit mentinerea în ordine a unei colectii de date dinamice (cu multe adãugãri si stergeri) simultan cu o cãutare rapidã dupã continut (reprezintã o bunã structurã de cãutare).
Arborii se folosesc pentru implementarea tipurilor abstracte multime, dictionar si coadã cu prioritãti.
Un caz particular important de arbori îl constituie arborii binari, în care un nod poate avea cel mult doi succesori: un succesor la stânga si un succesor la dreapta.
De cele mai multe ori legãturile unui nod cu succesorii sãi se reprezintã prin pointeri, dar este posibilã si o reprezentare a arborilor fãrã pointeri, printr-un vector de înregistrãri , unde fiecare înregistrare corespunde unui nod, iar adresele de legãturã între noduri sunt indici în vector. De obicei se întelege prin arbore o structurã cu pointeri, deoarece aceastã structurã este mai eficientã în cazul unor colectii cu numãr necunoscut sau foarte variabil de elemente.
Un arbore este complet definit printr-o singurã variabilã, care contine adresa nodului rãdãcinã.
Operatiile uzuale cu arbori sunt:
- Initializare arbore (creare arbore vid sau cu un singur nod);
- Adãugarea unui nod la un arbore ( ca nod frunzã);
- Cãutarea unei valori date într-un arbore;
- Eliminarea (stergerea) unui nod cu valoare datã;
- Afisarea tuturor nodurilor din arbore într-o anumitã ordine (mai general, aplicarea unor operatii asupra tuturor nodurilor din arbore).
O reprezentare liniarã posibilã a unui arbore este o expresie cu paranteze complete, în care fiecare nod este urmat de o parantezã ce grupeazã succesorii sãi. Exemple:
1) a (b,c)
este un arbore binar cu 3 noduri: rãdãcina 'a', având la stânga pe 'b' si la dreapta pe 'c'
5 (3 (1,), 7(,9))
este un arbore binar ordonat cu rãdãcina 5. Nodul 3 are un singur succesor, la stânga, iar nodul 7 are numai succesor la dreapta.
5
_______|_______
3 7
___|___ ___|___
1 9
Operatiile cu arbori binari se realizeazã mai compact prin functii recursive, care reflectã structura recursivã a unui arbore: prelucrarea unui arbore binar se reduce la prelucrarea celor doi subarbori din componenta sa.
Arbori binari cu pointeri
Definirea unui nod dintr-un arbore binar seamãnã cu definirea unui nod dintr-o listã înlãntuitã, dar contine douã adrese de legãturã (doi pointeri), cãtre cei doi succesori posibili :
typedef struct nod Nod;
Initializarea unui arbore vid se reduce la atribuirea valorii NULL pentru variabila rãdãcinã. Poate fi luatã în considerare si o initializare a rãdãcinii cu prima valoare introdusã în arbore, pentru ca adãugãrile ulterioare sã nu mai modifice adresa rãdãcinii (dacã nu se face modificarea arborelui pentru reechilibrare, dupã fiecare adãugare ).
Una dintre cele mai simple operatii cu un arbore binar este determinarea înãltimii unui arbore; înãltimea unui arbore este egalã cu cea mai mare dintre înãltimile subarborilor sãi, plus unu pentru rãdãcinã, pentru un arbore nevid si zero pentru arborele vid.
// calcul inaltime arbore binar
int inaltime (Nod * r)
Modificând putin functia anterioarã se obtine o functie care sã numere nodurile dintr-un arbore.
Cãutarea unei valori într-un arbore binar se reduce la cãutarea succesivã în fiecare din cei doi subarbori:
// cautare în arbore oarecare
Nod * cautAB ( Nod * r, int x)
Vizitarea nodurilor unui arbore binar înseamnã de fapt liniarizarea arborelui, adicã stabilirea unei secvente liniare de noduri. Explorarea unui arbore se poate face în adâncime sau în lãrgime (nivel cu nivel). Explorarea în adâncime se poate face în mai multe feluri, în functie de ordinea în care se iau în considerare rãdãcina, subarborele stânga si subarborele dreapta :
- Ordine prefixatã (preordine sau RSD) : rãdãcinã, stânga, dreapta
- Ordine infixatã (inordine sau SRD) : stânga, rãdãcinã, dreapta
- Ordine postfixatã (postordine sau SDR): stânga, dreapta, rãdãcinã
Fie arborele binar descris prin expresia cu paranteze:
5 ( 2 (1,4(3,)), 8 (6 (,7),9) )
Explorarea pe niveluri produce secventa de noduri: 5 2 8 1 4 6 9 3 7
Explorarea prefixatã produce secventa de noduri: 5 2 1 4 3 8 6 7 9
Explorarea infixatã produce secventa de noduri: 1 2 3 4 5 6 7 8 9
Explorarea postfixatã produce secventa de noduri: 1 3 4 2 7 6 9 8 5
Functia urmãtoare afiseazã în ordine infixatã valorile din nodurile unui arbore binar
void infix (Nod * r)
Functia "infix" poate fi usor modificatã pentru o altã strategie de vizitare a nodurilor.
void prefix (Nod * r)
Modul de realizare a operatiei de adãugare a unui nod la un arbore binar depinde de tipul arborelui ( ordonat sau nu ), deci dacã trebuie mentinutã o relatie între valorile nodurilor .
Arbori binari de cãutare
Un arbore binar ordonat, numit si arbore de sortare sau arbore de cãutare, este un arbore binar cu proprietatea cã orice nod are valoarea mai mare decât toti succesorii la stânga si mai micã decât toti succesorii la dreapta. Rezultã cã toate valorile din subarborele stânga sunt mai mici si toate valorile din subarborele dreapta sunt mai mari ca valoarea din rãdãcinã, pentru orice subarbore dintr-un arbore ordonat. Exemplu de arbore binar de cãutare:
5 ( 2 (1,4(3,)), 8 (6 (,7),9) )
Avantajul unui astfel de arbore este acela cã permite o cãutare mai rapidã a unei valori, comparabilã cu cãutarea binarã pentru vectori ordonati: dupã ce se comparã valoarea cãutatã cu valoarea din rãdãcinã se poate decide în care din cei doi subarbori se aflã (dacã existã) valoarea cãutatã. Fiecare nouã comparatie eliminã un subarbore din cãutare si reduce cu 1 înãltimea arborelui în care se cautã.
Timpul minim de cãutare se realizeazã pentru un arbore ordonat echilibrat (cu înãltime minimã), la care înãltimile celor doi subarbori sunt egale sau diferã cu 1. Acest timp este de ordinul log2(n), unde "n" este numãrul total de noduri din arbore. Procesul de cãutare într-un arbore binar ordonat poate fi exprimat recursiv sau nerecursiv.
// cãutare recursivã în arbore ordonat
Nod * cautABC ( Nod * r, int x)
// cãutare nerecursivã în arbore ordonat
Nod * cautABC ( Nod * r, int x)
return NULL;
Valoarea maximã dintr-un arbore binar de cãutare se aflã în nodul din extremitatea dreaptã, iar valoarea minimã în nodul din extremitatea stângã. O functie pentru determinarea valorii maxime dintr-un arbore binar de cãutare se poate scrie iterativ sau recursiv:
// valoare maxima din arbore binar de cautare
int maxABC ( Nod * r)
Adãugarea unui nod la un arbore binar ordonat seamãnã cu cãutarea, pentru cã se cautã nodul frunzã cu valoarea cea mai apropiatã de valoarea care se adaugã. Nodul nou se adaugã ca frunzã (arborele creste prin frunze).
// adaugare nod la arbore binar ordonat
void addABC (Nod ** r, int x)
if (x < p->val)
addABC (&(p->st),x);
else
addABC (&(p->dr),x);
Functia urmãtoare realizeazã nerecursiv operatia de adãugare nod la un arbore de cãutare:
// adaugare nod la arbore binar ordonat (nerecursiv)
Nod * add (Nod * r, int x)
if (x <q->val)
q->st=n; // n se adauga la stanga lui q
else
q->dr=n; // n se adauga la dreapta lui q
return r;
Eliminarea unui nod cu valoare datã dintr-un arbore binar ordonat trebuie sã considere urmãtoarele situatii:
- Nodul de sters nu are succesori (este o frunzã);
- Nodul de sters are un singur succesor;
- Nodul de sters are doi succesori.
Eliminarea unui nod cu un succesor sau fãrã sduccesori este simplã si se reduce la înlocuirea legãturii la nodul sters prin legãtura acestuia la succesorul nenul sau prin NULL.
Eliminarea unui nod cu 2 succesori se face prin înlocuirea sa cu un nod care are cea mai apropiatã valoare de cel sters; acesta poate fi nodul din extremitatea dreaptã a subarborelui stânga sau nodul din extremitatea stânga a subarborelui dreapta.
Operatia de eliminare nod se poate exprima nerecursiv sau recursiv.
// eliminare valoare datã dintr-un arbore binar
Nod * delABC (Nod * r, int x)
// inlocuieste nodul r cu nodul p
if (pp != r)
pp->dr = p->st;
else
r->st =NULL;
r->val =p->val;
}
free (p);
}
}
return r;
Expresii reprezentate prin arbori
O expresie care contine numai operatori binari poate fi reprezentatã printr-un arbore binar în care un nod poate contine fie un operator fie un operand. Exemplu de arbore pentru expresia
(a+b) / (c-d)
/
_______|_______
| |
___ +___ ___--___
| | | |
a b c d
Evaluarea expresiei se face de la frunze spre rãdãcinã, în ordine postfixatã. Functia urmãtoare are ca rezultat valoarea unei expresii aritmetice cu operanzi si rezultat de tip "float" :
enum ; // OP=0, VAL=1
typedef struct Nod ;
// evaluare expresie reprez. prin arbore
float eval(Nod * n)
Crearea arborelui corespunzãtor unei expresii aritmetice fãrã paranteze si cu operanzi formati dintr-o singurã cifrã se poate face folosind functiile urmãtoare:
// creare nod cu operand/operator
Nod * nodnou( char op)
// creare arbore dintr-o expresie aritmetica fara paranteze
Nod * exparb ( Nod* r, char *exp)
if (*exp==0)
else
Rãdãcina arborelui "r" este initializatã în programul principal cu adresa unui nod ce contine operatorul '+' si care are la stânga un nod cu un operand zero.
|
