AVL, respectivi Arbori Bicolori

[•MarcvsHdr]

Deschid topicul asta pentru ca m-am lovit de o dificultate de implementare. Am gasit recent o problema la care am nevoie de arbori de cautare - echilibrati.

Am citit vreo 2 zile si am invatat despre arbori AVL, dar lipseste un amanunt de implementare si m-am blocat. Mai exact, nu stiu cum sa reactualizez factorul ala de echilibru pe masura ce rotesc subarborii. O idee era sa pastrez si inaltimile, dar mi se pare destul de grotesc si implementarea din care m-am inspirat nu folosea inaltimile, ci doar factori de echilibru. (bibliografia mea se compune majoritar din cartea lui Ioan Maxim, "Arbori")

Cat despre arbori bicolori, nu am inteles nimic. Mi se pare tare naspa implementarea si m-a speriat cu totul.

Din cate am vazut, sunt gata implementati arbori echilibrati in STL, dar eu nu stiu sa folosesc STL si ma oftic tare... 

Ma poate ajuta cineva cu detalii de implementare la AVL? Teoretic stiu, dar nu stiu cum sa implementez practic.

P.S. chiar daca invat sa folosesc STL, tot vreau sa stiu sa implementez si manual, ca imi ofera pace sufleteasca 

[•Cosmin]

Gasesti implementare de avl in articolul Multe jmenuri ... al lui Mircea de pe sait. Parca in cartea aia cu arbori ai implementat tot ... Arborii rosu negrii sunt ok de implementat, trebuie doar curaj si vointa sa razbati prin tot, eu i-am implementat prima data cu cormenul langa mine cand eram tanar .

Sunt implementati in STL dar nu au operatia de gasire al celui de al k-lea element, care e destul de utila.

Cateodata poti rezolva problema cu o structura statica, adica iei toate elementele care vor fi inserate candva in arbore, le sortezi, iei ca radacina elementul din mijloc si tot asa, obtinand un arbore echilibrat, dar acum mai tii o valoare booleana in fiecare nod care iti zice daca elementul curent mai e sau nu in arbore, si cand faci o stergere practic schimbi valoarea booleana si atat. Asa nu mai te stresezi cu reechilibrari.

O structura de date destul de misto e structura de treap, care dupa ce o intelegi o poti implementa foarte repede fara sa trebuiasca sa tii minte cazuri de reechilibrare. Sunt o structura foarte intuitiva.

[•Darth_Niculus]

Mai exista si scape-goat-uri... care recunosc ca nu am implementat niciodata in ciuda faptului ca am citit despre ei... parca tot mai simplu e cu AVL-urile

[•filipb]

AVL-urile pot fi evitate in majoritatea cazurilor. Singurul caz pe care l-am intalnit unde nu a fost posibila evitarea lor ( a implementarii lor manuale adica ) este atunci cand iti trebuie o structura de date in care sa stergi, inserezi si faci query cate elemete sunt <= cu o cheie data x. Aici e obligatoriu de implementat manual.

STL iti ofera cam tot ce iti ofera un AVL implementat manual cu exceptia faptului ca nu merge sa interoghezi cate elemente are <= x, ceea ce e foarte urat in unele cazuri ( se intalneste destul de rar in problemele de interogari 2D ). Uite un mic program STL care foloseste set-uri ( AVL-uri ):

Cod:

#include <stdio.h>
#include <set> // biblioteca set-urilor

using namespace std; // linia asta trebuie introdusa cand folosesti STL

set<int> A; // declaratia unui set denumit A cu elemente de tip int

int main()
{
     A.insert(1); // insereaza elementul int 1
     A.insert(3); // insereaza elementul int 3
     A.insert(2); // insereaza elementul int 2
     A.erase(2); // sterge elementul 2

     if (A.find(2) != A.end()) // daca gaseste 2
         printf("DA\n");
     else 
         printf("NU\n"); // intra pe ramura else si afiseaza NU

     if (A.find(3) != A.end()) // daca gaseste 3
         printf("DA\n"); // intra pe ramura if si afiseaza DA
     else 
         printf("NU\n"); 


     return 0;
}

Baza STL-ului care se poate dovedi extrem de utila in concursuri ( vector, map, set, pair, sort, iteratori ) se invata in maxim o zi si chiar merita.

Mai exista si scape-goat-uri... care recunosc ca nu am implementat niciodata in ciuda faptului ca am citit despre ei... parca tot mai simplu e cu AVL-urile

  inseamna ca sunt nasoale tare scape-goate-urile de e mai simplu cu AVL.

[•Darth_Niculus]

  Hm.. majoritatea mi-au spus ca sunt mai simple ca AVL-urile.... dar mie nu-mi pare (desi presupun ca nu le-am inteles eu bine)

[•domino]

Treap-urile sunt baza.

[•MarcvsHdr]

Very useful stuff. Thanks a LOT, guys.
Am auzit si eu de treap dar nu am facut sapaturi pentru ca nu credeam ca o sa fie util. Acuma ca mi-ati spus voi, ma pun sa il citesc calumea la noapte. 

[•peanutz]

Am eu ceva implementari de avl daca vrei.

[•Darth_Niculus]

Am eu ceva implementari de avl daca vrei.

      Ar fi foarte folositoare daca n-ar fi deja una foarte buna pe site