Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Treapuri  (Citit de 16991 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
stef2n
Nu mai tace
*****

Karma: 218
Deconectat Deconectat

Mesaje: 641



Vezi Profilul
« : Decembrie 03, 2008, 14:35:00 »

Comentarii la articolul Treapuri scris de Marius Stroe.

Veti gasi aceasta structura de date ca fiind foarte folositoare si simplu de implementat. Smile
« Ultima modificare: Februarie 20, 2009, 02:49:56 de către Stefan Istrate » Memorat

Exista 10 categorii de oameni: cei care inteleg sistemul binar si cei care nu il inteleg.
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #1 : Decembrie 03, 2008, 17:35:13 »

GJ Marius! Very Happy Treapurile sunt alternativa cea mai buna cand trebuie sa scrii arbori echilibrati de mana Smile
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
Mishu91
Nu mai tace
*****

Karma: 169
Deconectat Deconectat

Mesaje: 751



Vezi Profilul
« Răspunde #2 : Decembrie 04, 2008, 16:00:33 »

Am o intrebare... De ce la initializare se face srand-ul ala?  Confused
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #3 : Decembrie 04, 2008, 16:13:22 »

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

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
Mishu91
Nu mai tace
*****

Karma: 169
Deconectat Deconectat

Mesaje: 751



Vezi Profilul
« Răspunde #4 : Decembrie 04, 2008, 16:31:11 »

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 Very Happy
« Ultima modificare: Decembrie 04, 2008, 20:32:17 de către Andrei Misarca » Memorat
Marius
Nu mai tace
*****

Karma: 154
Deconectat Deconectat

Mesaje: 572



Vezi Profilul
« Răspunde #5 : Decembrie 04, 2008, 16:56:02 »

Î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

Cod:
insert(R, key, rand() + 1);


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. Smile

Later edit:  Dacă mai știe cineva probleme care se rezolvă cu treapuri poate dorește să ne spună. Smile
« Ultima modificare: Decembrie 04, 2008, 22:47:21 de către Marius Stroe » Memorat

Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #6 : Decembrie 13, 2008, 21:38:19 »

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.
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
Marius
Nu mai tace
*****

Karma: 154
Deconectat Deconectat

Mesaje: 572



Vezi Profilul
« Răspunde #7 : Decembrie 14, 2008, 21:35:50 »

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
Memorat

Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
Mishu91
Nu mai tace
*****

Karma: 169
Deconectat Deconectat

Mesaje: 751



Vezi Profilul
« Răspunde #8 : Iunie 15, 2010, 17:34:00 »

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.
Memorat
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #9 : Iunie 16, 2010, 08:51:59 »

Setul e implementat ca arbore echilibrat de cautare dar nu ai acces la structura lui interna.
Memorat
APOCALYPTO
Nu mai tace
*****

Karma: 3
Deconectat Deconectat

Mesaje: 250



Vezi Profilul
« Răspunde #10 : Iunie 16, 2010, 22:07:48 »

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) ?
Memorat
Marius
Nu mai tace
*****

Karma: 154
Deconectat Deconectat

Mesaje: 572



Vezi Profilul
« Răspunde #11 : Iunie 17, 2010, 10:12:10 »

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.
Memorat

Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
dornescuvlad
Nu mai tace
*****

Karma: -138
Deconectat Deconectat

Mesaje: 234



Vezi Profilul
« Răspunde #12 : Iulie 15, 2010, 20:03:45 »

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

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. Tongue
« Ultima modificare: Iulie 15, 2010, 21:42:38 de către Vlad Eugen Dornescu » Memorat
APOCALYPTO
Nu mai tace
*****

Karma: 3
Deconectat Deconectat

Mesaje: 250



Vezi Profilul
« Răspunde #13 : Noiembrie 15, 2010, 18:56:54 »

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

Karma: 19
Deconectat Deconectat

Mesaje: 162



Vezi Profilul
« Răspunde #14 : Ianuarie 31, 2012, 20:40:00 »

Cum se determina a K-a cheie ?  Embarassed
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #15 : Ianuarie 31, 2012, 21:47:55 »

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

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
sulzandrei
Strain
*

Karma: -3
Deconectat Deconectat

Mesaje: 28



Vezi Profilul
« Răspunde #16 : Septembrie 14, 2016, 23:51:53 »

pff hintu ala a fost un fel de explicatie completa daca stii cum sa faci cu quicksort  Weightlift
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines