h2. Operaţii

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. Căutare
 
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:

* *Căutare*: 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 $cheie$ există putem proceda în felul următor:

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

Se observă că algoritmul poate fi scris şi iterativ, lucru care este indicat.

h3. Inserare
 
În cadrul operaţiei de inserare vom atribui unui nod nou o prioritate şi vom rearanja arborele pentru a menţine ambii invarianţi. Cu cât generatorul de numere pseudoaleatoare distribuie uniform priorităţi, astfel încât să nu existe două noduri cu aceeaşi prioritate, cu atât arborele este mai bine balansat.
 
h3. Ştergere

* *Rotaţii*:

Operaţia de ştergere, după eliminarea unui nod, va reconstrui arborele astfel încât cei doi invarianţi să fie menţinuţi. Cum fiecare set de priorităţi asociat nodurilor va reprezenta arborele într-un singur mod şi numai într-unul singur, probabilitatea ca arborele să fie echilibrat este rezonabil de mare. Acest lucru se datorează faptului că arborii rău echilibraţi sunt puţini comparativ cu cei echilibraţi.

Vor urma în curând... :)

De adăugat: insert, remove, split, join, lookup, rotleft, rotright, print, balance, meld {$O(mlog(n/m))$} - unirea a două treapuri T1 şi T2 fără nicio relaţie de ordine între ele, difference $O(mlog(n/m))$ - din T1 şi T2 rezultă un T care conţine cheile din T1 care nu sunt în T2, interpretarea geometrică.

De adăugat: insert, remove, split, join, lookup, rotleft, rotright, print, balance, meld {$O(mlog(n/m))$} - unirea a două treapuri T1 şi T2 fără nicio relaţie de ordine între ele, difference $O(mlog(n/m))$ - din T1 şi T2 rezultă un T care conţine cheile din T1 care nu sunt în T2.

h2. Avantaje