h2(#avantaje). Avantaje

Structurile de date de heap şi de arbori binari de căutare sunt uşor de implementat şi de înţeles, iar Treapurile sunt o combinaţie a acestor două concepte. Astfel, este suficient să fie înţeleşi cei doi invarianţi, după care implementarea unui Treap se poate face cu uşurinţă în 20 de minute, fără antrenament. De obicei, la structuri ca $Arbori Roşu-Negrii$ trebuie folosite serii de rotaţii stânga şi dreapta complexe şi analizate o multitudine de cazuri, pe când la Treapuri facem doar câte o rotaţie stânga sau dreapta la fiecare pas al algoritmului. Ei nu sunt predaţi pentru că $Arborii Roşu-Negrii$ sau $AVL$ au demonstraţia că limita celei mai lente operaţii este $O(log N)$ şi sunt exemple didactice, dar Treapurile, deşi cu o demonstraţie mai grea pentru limita de $O(log N)$, ce implică probabilităţi, sunt mult mai uşor de implementat iar în practică, cu siguranţă este greu de decis care sunt mai rapizi. Sunt deci, o opţiune demnă de luat în seamă.

Structurile de date de heap şi de arbori binari de căutare sunt uşor de implementat şi de înţeles, iar Treapurile sunt o combinaţie a acestor două concepte. Astfel, este suficient să fie înţeleşi cei doi invarianţi, după care implementarea unui Treap se poate face cu uşurinţă în 20 de minute, fără antrenament. De obicei, la structuri ca $Arbori Roşu-Negrii$ trebuie folosite serii de rotaţii stânga şi dreapta complexe şi analizate o multitudine de cazuri, pe când la Treapuri facem doar câte o rotaţie stânga sau dreapta la fiecare pas al algoritmului. Ei nu sunt predaţi pentru că $Arborii Roşu-Negrii$ sau $AVL$ au demonstraţia că limita celei mai lente operaţii este $O(log N)$ şi sunt exemple didactice, dar Treapurile, deşi cu o demonstraţie mai grea pentru limita de $O(log N)$, ce implică probabilităţi, sunt mult mai uşor de implementat iar în practică cu siguranţă este greu de decis care sunt mai rapizi. Sunt deci, o opţiune demnă de luat în seamă.

h2(#operatii). Operaţii

Costul operaţiilor de mai jos este proporţional cu adâncimea unui nod din Treap. După cum am menţionat mai sus, cu ajutorul probabilităţilor se poate deduce că adâncimea aşteptată a oricărui nod este $O(log N)$, ceea ce implică costul unei operaţii să fie $O(log N)$.

Costul operaţiilor de mai jos este proporţional cu adâncimea unui nod din Treap. Cu ajutorul probabilităţilor se poate deduce că adâncimea aşteptată a oricărui nod este $O(log N)$, ceea ce implică costul unei operaţii să fie $O(log N)$.

h3(#cautare). Căutare

Căutarea într-un Treap este identică cu cea într-un Arbore Binar de Căutare. Pentru a verifica dacă o valoare există putem proceda în felul următor:

Căutarea într-un Treap este identică cu cea într-un Arbore Binar de Căutare. Priorităţile din noduri sunt folosite pentru a menţine arborele echilibrat. Pentru a verifica dacă o valoare există putem proceda în felul următor:

== code(cpp) |
int search(T* n, int key)

h3(#rotatii). Rotaţii

Rotaţiile sunt cărămizile de la baza structurii de Treap.

Să urmărim (în desen) efectul rotaţiilor asupra structurii de heap a arborelui. Pentru început, să presupunem că arborele din figura din stânga are o structură de heap cu excepţia lui $w$ care are o prioritate mai mare decât a lui $z$. Dacă îl rotim pe $w$ spre dreapta (figură rotaţie stânga - dreapta) vedem, în figura din dreapta, că structura de heap este satisfăcută. Din moment ce $A$ era un subarbore valid al lui $w$, va rămâne în continuare un subarbore valid. Cum $B$ şi $C$ se aflau iniţial sub $z$ ei aveau o prioritate mai mică decât a lui $z$, şi, astfel, după rotaţie ei sunt subarbori valizi pentru $z$. Este clar că $z$ este un fiu valid al lui $w$, prin presupunerea făcută iniţial.

Să urmărim (în desen) efectul rotaţiilor asupra structurii de heap a Treapului. Pentru început, să presupunem că arborele din figura din stânga are o structură de heap cu excepţia lui $w$ care are o prioritate mai mare decât a lui $z$. Dacă îl rotim pe $w$ spre dreapta (figură rotaţie stânga - dreapta) vedem, în figura din dreapta, că structura de heap este satisfăcută. Din moment ce $A$ era un subarbore valid al lui $w$, va rămâne în continuare un subarbore valid. Cum $B$ şi $C$ se aflau iniţial sub $z$ ei aveau o prioritate mai mică decât a lui $z$, şi, astfel, după rotaţie ei sunt subarbori valizi pentru $z$. Este clar că $z$ este un fiu valid al lui $w$, prin presupunerea făcută iniţial. Urmăriţi dacă şi invariantul arborilor de căutare se menţine. Reţineţi că această rotaţie stă la baza algoritmului de inserare!

Pe de altă parte, să presupun că arborele are o structură de heap, cu excepţia lui $z$ care are o prioritate mai mică decât a ambilor fii şi să presupunem că $w$ este fiul cu prioritatea mai mare. Dacă efectuăm o rotaţie spre dreapta în $z$, radăcina va deveni $w$ care are în continuare subarborele valid stâng $A$, iar pe $z$ ca fiu valid în dreapta. Nivelul lui $z$ a scăzut cu $1$ dar este posibil ca subarborele său să nu aibă structura de heap şi să ne situăm fie în cazul acesta, când ambii fii au prioritatea mai mare fie în cazul de mai înainte când doar unul din fii are prioritatea mai mare. Astfel, continuând să îl rotim pe $z$ vom redobândi structura de heap pentru priorităţi.

O altă situaţie în care putem fi puşi este ca arborele să aibă o structură de heap, cu excepţia lui $z$ care are o prioritate mai mică decât a ambilor fii. Să presupunem că $w$ este fiul cu prioritatea mai mare. Dacă efectuăm o rotaţie spre dreapta în $z$, radăcina va deveni $w$ care are în continuare subarborele valid stâng $A$, iar pe $z$ ca fiu valid în dreapta. Nivelul lui $z$ a scăzut cu $1$ dar este posibil ca subarborele său să nu aibă structura de heap şi să ne situăm fie în cazul acesta, când ambii fii au prioritatea mai mare fie în cazul de mai înainte când doar unul din fii are prioritatea mai mare. Vom continua să îl rotim pe $z$ până când vom redobândi structura de heap.
 
Cazurile simetrice sunt imaginea în oglindă pentru cazurile de mai sus. Astfel, va fi necesar să facem o rotaţie spre stânga.

Cazurile simetrice, când trebuie să efectuăm o rotaţie spre dreapta, se tratează analog.

Pentru o rotaţie sunt necesare doar câteva operaţii cu pointeri.

h3(#inserare). Inserare

În cadrul operaţiei de inserare vom atribui unui nod nou o prioritate şi îl vom insera, conform algoritmului standard de inserare într-un arbore binar, la baza arborelui. Cheile formează un arbore de căutare, dar priorităţile pot să nu mai formeze un heap. Pentru a redobândi această proprietate, cât timp nodul de inserat, fie el $z$, are prioritatea mai mare decât a părintelui său, se va executa o rotaţie în $z$, o operaţie locală care scade nivelul lui $z$ cu $1$ şi creşte nivelul părintelui lui $z$ cu $1$, timp în care invariantul arborilor de căutare este menţinut. Timpul de inserare a lui $z$ este proporţional cu adâncimea lui înainte de rotaţii - trebuie să coborâm după care să urcăm înapoi efectuând rotaţiile necesare.

În cadrul operaţiei de inserare vom atribui unui nod nou o prioritate şi îl vom insera, conform algoritmului standard de inserare într-un arbore binar, la baza arborelui. Cheile formează un arbore de căutare, dar priorităţile pot să nu mai formeze un heap. Pentru a redobândi această proprietate, cât timp nodul $z$ are prioritate mai mare decât părintele său, se execută o $rotaţie$ în $z$, o operaţie locală care scade nivelul lui $z$ cu $1$ şi creşte nivelul părintelui lui $z$ cu $1$, timp în care invariantul arborilor de căutare este menţinut. Timpul de inserare a lui $z$ este proporţional cu adâncimea lui înainte de rotaţii - trebuie să coborâm după care să urcăm înapoi efectuând rotaţiile necesare.

Complexitate: $O(log N)$.
h3(#stergere). Ştergere

Operaţia de ştergere este inversul operaţiei de inserare. (Se va desena o figură) Să presupunem că vrem să ştergem nodul $z$. Cât timp $z$ nu este o frunză, alegem fiul $w$ cu prioritatea mai mare şi facem o rotaţie pentru a aduce pe $w$ în locul lui $z$. Astfel, după cum este explicat la 'rotaţii':treapuri#rotatii, nivelul lui $z$ scade cu $1$ până când va deveni frunză iar arborele va redobândi structura de heap.

Operaţia de ştergere este inversul operaţiei de inserare. (Se va desena o figură) Să presupunem că vrem să ştergem nodul $z$. Cât timp $z$ nu este o frunză, alegem fiul $w$ cu prioritatea mai mare şi facem o rotaţie pentru a aduce pe $w$ în locul lui $z$. Astfel, după cum este explicat la rotaţii, nivelul lui $z$ scade cu $1$ până când va deveni frunză, iar arborele va redobândi structura de heap pentru priorităţi.

Complexitate: $O(log N)$.