Structuri de Date 2023 - C3: Arbori binari

Structuri de Date

Curs 3: Arbori binari

Cuprins:

Arbori oarecare
Arbori binari
Arbori binari de cautare
Insertia in arborele binar de cautare
Afisarile arborilor binari (nu numai de cautare)
Cautarea in arborele binar de cautare
Stergerea din arborele binar de cautare

Arbori oarecare

Definitie:

Formal, un arbore este o structura ierarhica care poate fi definita recursiv in felul urmator:

Fie este un arbore vid.
Fie este un tuplu

(Informatie, [fiu1,fiu2,...,fiuN] )

in care membrul [fiu1,fiu2,...,fiuN] este o lista de oricati alti subarbori, fiecare element fiind la randul lui arbore (deci tupluri de acelasi fel)

ca si implementare lista [fiu1,fiu2,...,fiuN] este o lista de referinte (pointeri la alti arbori de acelasi tip)

Terminologie:

subarborii unui nod se numesc fii ai acelui nod denumit parinte/tata
primul nod din arbore este denumit radacina, fiind singurul nod fara parinte/tata
distanta fata de radacina = numarul de legaturi ierarhice parcurse pentru a ajunge la nodul curent incepand cu radacina
spunem ca nodurile aflate la aceeasi distanta de radacina se afla pe acelasi nivel
inaltimea unui arbore = lungimea drumului catre cel mai indepartat nod

Proprietati:

exista un nod unic care nu are parinte/tata denumit radacina:
nu contine cicluri, astfel incat
1. toate referintele sunt unice (nu au voie sa se repete la nivelul intregului arbore)
2. nicio referinta nu are voie sa fie catre radacina

Implementare:

struct nod{ int info; nod *fii[max_fii];};struct arbore{ nod* radacina; arbore(){radacina=NULL;}}

Clasificare

Dupa numarul maxim de fii:

• arbori binari

• arbori ternari

• arbori cuaternari

.....

• arbori oarecare

Dupa numarul minim de fii nevizi:

• arbori nestricti (pot exista oricati fii vizi sau nevizi)

• ???

• arbori stricti (fiecare nod are numarul maxim de fii sau niciunul)

Arbore binar strict:

Dupa densitatea nodurilor:

(arbori incompleti)
arbori plini/completi

• pe fiecare nivel al arborelui se gaseste numarul maxim de noduri

arbori completi pe nivele

• pe fiecare nivel al arborelui se gaseste numarul maxim de noduri, mai putin pe ultimul nivel, nivel completat partial, compact de la stanga la dreapta

Arbore complet(plin):

Arbore complet pe nivele:

Dupa relatii de ordine definite ulterior:

arbori neordonati
arbori ordonati:

• cu relatie de ordine intre fiii aceluiasi nod

-> arbori de cautare (search trees)

• cu relatie de ordine intre parinte si fiu

-> ansamble (heap-uri)

Arbore binar de cautare:

Min-Heap:

Observatii:

proprietatile legate de numarul de fii se pot verifica la nivel de nod!
proprietatile legate de ordinea aditionala se pot verifica la nivel de nod + fii imediati!

Odata fixata structura arborelui ales -> toate proprietatile trebuie sa fie respectate

2. Arbori binari

Definitie:

Formal, un arbore binar poate fi definit recursiv in felul urmator:

Fie este un arbore vid.
Fie este un tuplu

(Informatie, subarbore stang, subarbore drept)

in care membrii subarbore stang si drept sunt la randul lor arbori (deci tupluri de acelasi fel)

Implementare:

struct nod{ int info; nod *st,*dr;};struct arbore{ nod* radacina; arbore(){radacina=NULL;}}

Exemplu:

(1,

(7,

(2,vid,vid),

(6,

(5,vid,vid),

(11,vid,vid)

)

),

(9,vid,

(9,

(5,vid,vid),

vid

)

Legatura intre numarul de noduri si inaltimea arborelui binar:

Un arbore binar complet(plin) de inaltime h are atatea noduri:

Un arbore binar complet pe nivele cu n noduri are inaltimea:

3. Arbori Binari de Cautare

Un arbore binar de cautare este:

un arbore binar in care fiecare nod are maxim doi fii
de cautare in sensul in care pentru fiecare nod x: subarborele stang contine chei mai mici sau egale decat x, iar subarborele drept chei mai mari decat x

In fiecare nod trebuie sa fie adevarata proprietatea arborelui de cautare:

subarbore stang <= nod curent < subarbore drept

4. Insertia in Arborele Binar de Cautare

Intr-un arbore binar de cautare avem o metoda specifica pentru inserat o valoare x in asa fel incat sa verificam cele doua conditii de mai sus:

se incepe cu pozitia radacinii arborelui
daca in pozitia curenta nu exista nod, x se leaga in arbore la aceasta pozitie
daca exista nod cu valoarea t la pozitia curenta , atunci x se insereaza in subarborele stang daca x <= t, sau in subarborele drept, altfel

Exemplu: creati arborele binar de cautare obtinut prin inserarea pe rand a cheilor 6 4 9 2 1 5 3 7 8:

Arbore Binar de Cautare

5. Afisarile arborilor binari (nu numai de cautare)

//Preordine void RSD(nod *radacina){ if (radacina!=NULL){ cout<<radacina->info<<" "; RSD(radacina->st); RSD(radacina->dr); }}

//Inordinevoid SRD(nod *radacina){ if (radacina!=NULL){ SRD(radacina->st); cout<<radacina->info<<" "; SRD(radacina->dr); }}

//Postordine void SDR(nod *radacina){ if (radacina!=NULL){ SDR(radacina->st); SDR(radacina->dr); cout<<radacina->info<<" "; }}

IMPORTANT: exista multi arbori care au acelasi SRD
IMPORTANT: un arbore poate fi reconstruit unic din doua afisari diferite, de exemplu SRD si RSD. Nu este suficienta 1 singura afisare!

Pe exemplul dat, SRD: 1 2 3 4 5 6 7 8 9

Pe exemplul dat SRD cu apel in radacina, pas cu pas:

sunt in 6, ma duc in stanga

sunt in 4, ma duc in stanga,

sunt in 2, ma duc in stanga,

sunt in 1, ma duc in stanga,

sunt in NULL, ma intorc,

sunt in 1, afisez 1, ma duc in dreapta,

sunt in NULL, ma intorc,

sunt in 1, ma intorc,

sunt in 2, afisez 2, ma duc in dreapta,

sunt in 3, ma duc in stanga,

sunt in NULL, ma intorc,

sunt in 3, afisez 3, ma duc in dreapta,

sunt in NULL, ma intorc,

sunt in 3, ma intorc,

sunt in 2, ma intorc,

sunt in 4, afisez 4, merg in dreapta, ETC

similar celelalte afisari, RSD si SDR, doar se modifica ordinea afisarii si intrarii in recursie

Pe exemplul dat, RSD: 6 4 2 1 3 5 9 7 8

Afisare RSD de tip folder

void RSD(){RSD(radacina,0);}void RSD(nod *radacina, int nivel){ if (radacina!=NULL){ for (int i=0;i<nivel;i++) cout<<" "; cout<<radacina->info<<endl; RSD(radacina->st,nivel+1); RSD(radacina->dr,nivel+1); }}

6 4 2 1 3 5 9 7 8

void RSD(){RSD(radacina,0,0);}void RSD(nod *radacina, int nivel, int dir){ if (radacina!=NULL){ for (int i=0;i<nivel;i++) cout<<" "; cout<<radacina->info<<(dir==-1?"st":"")<<(dir==1?"dr":"")<<endl; RSD(radacina->st,nivel+1,-1); RSD(radacina->dr,nivel+1,1); }}

6 4st 2st 1st 3dr 5dr 9dr 7st 8dr

Aceasta afisare identifica un unic arbore binar.

6. Cautarea in Arborele Binar de Cautare

int find(int x){return find(x,radacina);}int find(int x, nod* radacina){ if (radacina==NULL) return 0; if (x==radacina->info) return 1; if (x<radacina->info) return find(x,radacina->st); else return find(x,radacina->dr);}

7. Stergerea din Arborele Binar de Cautare

Daca stergem un nod, dar vrem sa pastram calitatea de arbore de cautare, atunci nu e trivial:

daca stergem un nod fara fii, de exemplu 1:

2->stanga = NULL

daca stergem un nod cu un singur fiu, de exemplu 7:

9->stanga = 7->dreapta

!!!! daca stergem un nod cu ambii fii, de exemplu 6, candidatii care il pot inlocui sunt:

- 5 cel mai mare nod (mai mic decat 6)
- 7 cel mai mic nod (mai mare decat 6)

Cum se gaseste nodul 5: merg o data in stanga si apoi numai in dreapta pana cand nu se mai poate.

Dupa ce pun valoarea nodului 5 sau 7 in radacina, apoi vechiul nod se sterge cu unul din cazurile mai simple: pentru ca are cel mult un fiu !!!!

Complexitate Arbori Binari de Cautare

Insertia

Worst case: O( n ) in arbore degenerat = lista (de exemplu, inseram valori crescatoare)

Average case: O( log n ) pentru intrari distribuite uniform

Extragerea

Worst case: O( n ) in arbore degenerat (construiti un astfel de caz!)

Average case: O( log n ) pentru intrari distribuite uniform