infoarena

Comentarii la articolul Treapuri (http://infoarena.ro/treapuri) scris de Marius Stroe (http://infoarena.ro/utilizator/marius).

Veti gasi aceasta structura de date ca fiind foarte folositoare si simplu de implementat. :)

GJ Marius! :D Treapurile sunt alternativa cea mai buna cand trebuie sa scrii arbori echilibrati de mana :)

Am o intrebare... De ce la initializare se face srand-ul ala?  :?

Functia srand() e necesara pentru ca la rulari diferite functia random sa returneze valori diferite.

Da. Dar unde se genereaza ceva random?

L.E. Cheia reprezinta valoarea numarului din nodul respectiv(daca am inteles bine), dar prioritatea ce reprezinta mai exact, si cum se calculeaza?
L.E.2: Mersi Marius, am inteles :D

Întâi, țin să îi mulțumesc lui Ștefan pentru șlefuirea conținutului și lui Cosmin Negrușeri pentru completările sale.

Mișule, dacă vrei să inserezi un nod faci așa



unde R e rădăcina, key e valoarea de inserat iar rand() + 1 o prioritate aleatoare (se folosește funcția de generare a numerelor pseudoaleatoare).

L-am corectat prea mult și am uitat să menționez cum s-ar insera un nod. O să adaug și asta.

Prioritatea se folosește, cum scrie și în introducere, la menținerea arborelui echilibrat. Datorită lor arborele se balansează și tot datorită lor se poate demonstra, cum scrie la Operații, că adâncimea în medie a unui nod e O(log N). Dacă nu crezi că e de ajuns de eficient, uită-te la sursa pe care am trimis-o la problema zeap.

Nu e nevoie decât să știi ce înseamnă un treap că implementarea vine de la sine. Eu nu am două surse la fel. :)

Later edit:  Dacă mai știe cineva probleme care se rezolvă cu treapuri poate dorește să ne spună. :)

Tri de pe infoarena se rezolva cu un arbore echilibrat. In general, se intampla des sa poti folosi un treap in loc de un arbore de intervale.

Când se întâmplă să poți folosi un treap în locul unui arbore de intervale, e necesar doar un arbore binar echilibrat, cu adângimea O(logN), pentru că e static. Și poți face asta în câteva rânduri cu un algoritm simplu. După care tot interoghezi și faci update pe structura lui. Un exemplu e aici:

http://infoarena.ro/job_detail/229892?action=view-source (http://infoarena.ro/job_detail/229892?action=view-source)

Set-ul nu este un arbore propriu-zis, el menține elementele sortate. Dacă folosești set nu vei putea folosi structura arborescenta a arborelui echilibrat, deci nu poți afla nici rădăcina.

Setul e implementat ca arbore echilibrat de cautare dar nu ai acces la structura lui interna.

La join cand creez acea radacina ajutatoare nu este de preferabil ca ea sa aiba prioritatea un numar foarte mic( gen -0x3f3f3f3f sau ceva putin mai mare pentru ca eu la nil folosesc deja aceasta prioritate) ?

Rădăcina ajutătoare va fi ştearsă. Iar dacă te uiţi pe codul funcţiei erase() vei vedea că nu are nicio importanţă ce valoare are prioritatea sa. Nodul ajutător va fi coborât până va ajunge frunză, după care şters.

Imi cer scuze daca gresesc, dar am o nelamurire : Nu sunt cumva functiile rotRight si rotLeft din articol inversate?  :)

P.S : Sorry, eu am gandit altfel.La rotRight duc nodul din n-> right in locul tatalui  si la rotLeft duc nodul din n-> left in locul tatalui.Vad ca in articol e exact invers. :P

Cum s-ar putea folosi un Treap la Bile4?
Banuiesc ca este vorba despre o implementare de 100 de puncte.

Cum se determina a K-a cheie ?  :oops:

Hint: trebuie sa retii in fiecare nod cat de mare este subarborele sau.

pff hintu ala a fost un fel de explicatie completa daca stii cum sa faci cu quicksort  :weightlift: