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.
|
