h1. Treap-uri

Mă documentez. :D

În acest articol voi prezenta o alternativă pentru arbori binari de căutare echilibraţi, precum $AVL$, $Red-Black Trees$, $Splay Trees$ şi $B-Trees$.
 
h2. Ce este un _Treap_?
 
Treap-ul este un arbore binar în care fiecare nod conţine două informaţii:
 
* $cheie$;
 
* $prioritate$.
 
Proprietăţile cele mai importante ale acestei structuri de date sunt următoarele:
 
* _dacă parcurgem arborele în inordine, atunci vom obţine nodurile sortate_;
 
* _prioritatea fiecărui nod este mai mare decât cea a fiilor săi_.
 
În consecinţă, treap-ul este un arbore binar de căutare pentru chei şi un max-heap pentru priorităţi.
 
În continuare, vom presupune, pentru uşurinţă, că toate cheile din treap-ul $T$ sunt distincte. Cazul în care avem nevoie să inserăm şi valori ce se repetă se va trata cu uşurinţă după ce acest articol va fi înţeles.
 
Astfel, din moment ce $T$ este un heap, nodul $v$ cu prioritatea cea mai mare trebuie să fie rădăcina. Cum este şi un arbore binar de căutare, orice nod $u$ cu $cheie(u) < cheie(v)$ se găseşte în subarborele stâng al lui $v$, şi orice nod $w$ cu $cheie(w) > cheie(v)$ se găseşte în subarborele drept.
 
h2. Operaţii