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;};In orice nod este verificata proprietatea arborelui 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:
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
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 !!!!
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).