Structuri de Date 2023 - L3: Arbori binari

Structuri de Date

Laborator 3: Arbori binari

Laborator 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

Se implementeaza cu pointeri:

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

In orice nod este verificata proprietatea arborelui de cautare.

Insertie

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:

Afisarile arborilor binari

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

//Inordine void RSD(nod *radacina){ if (radacina!=NULL){ cout<<radacina->info<<" "; RSD(radacina->st); RSD(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

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

Stergerea

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

Sursa:

#include <iostream>using namespace std; struct nod_arbore{ int info; nod_arbore* fiu_stang; nod_arbore* fiu_drept;}; struct arbore{ nod_arbore* radacina; arbore(){ radacina=NULL; } void insert_element(int x){ nod_arbore* nou = new nod_arbore; nou->info = x; nou->fiu_stang=NULL; nou->fiu_drept=NULL; if (radacina==NULL){ radacina=nou; return; } nod_arbore* pointer_prev = NULL; nod_arbore* pointer = radacina; int directie = 0; while(pointer!=NULL){ pointer_prev=pointer; if (x<=pointer->info){ pointer=pointer->fiu_stang; directie = -1; }else{ pointer=pointer->fiu_drept; directie = 1; } } if (directie <0) pointer_prev->fiu_stang=nou; else pointer_prev->fiu_drept=nou; } void delete_element(int x){ nod_arbore* pointer_prev =NULL; nod_arbore* pointer =radacina; int directie=0; while (pointer!=NULL && pointer->info!=x){ pointer_prev=pointer; if (x<= pointer->info){ pointer=pointer->fiu_stang; directie= -1; }else{ pointer= pointer->fiu_drept; directie =1; } } if (pointer==NULL){ cout<<"nu exista "<<x<<endl; return; } //pointer indica nodul care trebuie sters //cazul in care nodul de sters nu are fii if (pointer->fiu_stang==NULL && pointer->fiu_drept==NULL){ cout<<"nu are fii "<<x<<endl; if (pointer == radacina){ cout<<"este radacina "<<x<<endl; radacina=NULL; delete pointer; return; } if (directie<0) pointer_prev->fiu_stang=NULL; else pointer_prev->fiu_drept=NULL; delete pointer; return; } //cazul in care nodul de sters are doar fiu stang if (pointer->fiu_stang!=NULL && pointer->fiu_drept==NULL){ cout<<"are doar fiu stang "<<x<<endl; if (pointer == radacina){ cout<<"este radacina "<<x<<endl; radacina=pointer->fiu_stang; delete pointer; return; } if (directie<0) pointer_prev->fiu_stang=pointer->fiu_stang; else pointer_prev->fiu_drept=pointer->fiu_stang; delete pointer; return; } //cazul in care nodul de sters are doar fiu drept if (pointer->fiu_stang==NULL && pointer->fiu_drept!=NULL){ cout<<"are doar fiu stang "<<x<<endl; if (pointer == radacina){ cout<<"este radacina "<<x<<endl; radacina=pointer->fiu_drept; delete pointer; return; } if (directie<0) pointer_prev->fiu_stang=pointer->fiu_drept; else pointer_prev->fiu_drept=pointer->fiu_drept; delete pointer; return; } //cazul in care nodul de sters are ambii fii cout<<"are ambii fii "<<x<<endl; nod_arbore* pointer2=pointer->fiu_stang; while (pointer2->fiu_drept!=NULL) pointer2=pointer2->fiu_drept; int valoare = pointer2->info; cout<<"nodul "<<valoare<<" il poate inlocui pe "<<x<<endl; delete_element(valoare);//doar daca sunt toate cheile distincte //am garantia ca valoare va fi sters ori cu stergerea-fara-fii //ori cu stergerea doar-fiu-stang; sigur nu are fiu drept pointer->info=valoare; } void SRD(){ cout<<"SRD: "; SRD(radacina); cout<<endl; } void SRD(nod_arbore* pointer){ if (pointer!=NULL){ SRD(pointer->fiu_stang); cout<<pointer->info<<" "; SRD(pointer->fiu_drept); } } void RSD(){ cout<<"RSD: "; RSD(radacina); cout<<endl; } void RSD(nod_arbore* pointer){ if (pointer!=NULL){ cout<<pointer->info<<" "; RSD(pointer->fiu_stang); RSD(pointer->fiu_drept); } } }; int main(){ arbore arb; arb.insert_element(6); arb.insert_element(4); arb.insert_element(9); arb.insert_element(2); arb.insert_element(1); arb.insert_element(5); arb.insert_element(3); arb.insert_element(7); arb.insert_element(8); arb.SRD(); arb.RSD(); arb.delete_element(6); arb.SRD(); arb.RSD(); return 0;}

Alegerea temei de laborator (link)

MAXIM ~3 STUDENTI PER SEMIGRUPA LA ACEEASI TEMA

🙂 Folosind arbori binari de cautare, implementati intersectia a doua multimi. Fiecare multime este un arbore binar de cautare, iar rezultatul este un nou arbore binar de cautare, continand elementele din intersectie. O(n log n)
🙂 Folosind arbori binari de cautare, implementati diferenta a doua multimi. Fiecare multime este un arbore binar de cautare, iar rezultatul este un nou arbore binar de cautare, continand elementele din diferenta. O(n log n)
🙂 Folosind arbori binari de cautare, implementati diferenta simetrica a doua multimi. Fiecare multime este un arbore binar de cautare, iar rezultatul este un nou arbore binar de cautare, continand elementele din diferenta simetrica. O(n log n)
🙂 Folosind arbori binari de cautare, implementati reuniunea a doua multiseturi. Fiecare multiset este un arbore binar de cautare, iar rezultatul este un nou arbore binar de cautare, continand elementele din reuniune. O(n log n) 4a 2b 7c ∪ 2a 4b 3c = 4a 4b 7c -> luam maximum
🙂 Folosind arbori binari de cautare, implementati intersectia a doua multiseturi. Fiecare multiset este un arbore binar de cautare, iar rezultatul este un nou arbore binar de cautare, continand elementele din intersectie. O(n log n) 4a 2b 7c ∩ 2a 4b 3c = 2a 2b 3c -> luam minimum
🙂🔨👑 Folosind arbori binari de cautare, implementati diferenta a doua multiseturi. Fiecare multiset este un arbore binar de cautare, iar rezultatul este un nou arbore binar de cautare, continand elementele din diferenta. O(n log n) 4a 2b 7c \ 2a 4b 3c = 2a 4c -> luam diferenta
🙂🔨👑 Folosind arbori binari de cautare, implementati diferenta simetrica a doua multiseturi. Fiecare multiset este un arbore binar de cautare, iar rezultatul este un nou arbore binar de cautare, continand elementele din diferenta simetrica. O(n log n) 4a 2b 7c ∆ 2a 4b 3c = 2a 2b 4c -> (A\B)∪(B\A)

🙂🔨👑 Probleme pentru smecheri:

A. (3p) Implementati un arbore binar de cautare reprezentat pe un array.

Folositi valori speciale (e.g -1) pentru a marca noduri non-prezente (NULL).

Folositi valori speciale (e.g -3 si -2) pentru a imbunatati performanta stergerii:

Stergerea se comporta la fel ca la arborele cu pointeri, mai putin cazul:

Cand un nod cu un singur fiu este sters, in loc sa caram toate nodurile din subarbore un nivel mai sus, nodul ia valoarea -3 sau -2 specificand ca arborele se continua pe acea directie, fara sa mai mutam nodurile.

Analizati ce cazuri speciale (arbori degenerati) pot sa apara din cauza introducerii valorilor speciale.

B. (3p)Fie factorul de echilibru al unui nod = (inaltimea subarborelui drept) - (inaltimea subarborelui stang).

Sa se sorteze un array de arbori dupa toate criteriile:

factorul de echilibru (crescator),
apoi in caz de egalitate, dupa inaltimea maxima (crescator),
apoi in caz de egalitate, dupa numarul de noduri (crescator).