Astfel, din moment ce $T$ este un heap, nodul $v$ cu prioritatea cea mai mare trebuie să fie rădăcina. Întrucât 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.

Cheile şi priorităţile determină în mod unic forma unui treap. Prin inducţie se demonstrează că treapul este arborele binar obţinut prin inserarea cheilor în ordinea descrescătoare a priorităţilor. Algoritmul de inserare este cel obişnuit pentru arborii de căutare. Astfel, cum fiecare set de priorităţi asociat nodurilor va aranja arborele într-un singur mod, probabilitatea ca arborele să fie echilibrat este rezonabil de mare, fapt datorat numărului mic al arborilor rău echilibraţi în comparaţie cu cei echilibraţi. Iată şi secretul acestei structuri de date: probabilitatea infimă de a se găsi o serie de priorităţi generate aleator care să nu menţină arborele echilibrat.

Cheile şi priorităţile asociate lor, in condiţiile în care ambele sunt distincte, determină în mod unic forma unui treap. Prin inducţie se demonstrează că treapul este arborele binar obţinut prin inserarea cheilor în ordinea descrescătoare a priorităţilor. Algoritmul de inserare este cel obişnuit pentru arborii de căutare. Astfel, cum fiecare set de priorităţi asociat nodurilor va aranja arborele într-un singur mod, probabilitatea ca arborele să fie echilibrat este rezonabil de mare, fapt datorat numărului mic al arborilor rău echilibraţi în comparaţie cu cei echilibraţi. Iată şi secretul acestei structuri de date: probabilitatea infimă de a se găsi o serie de priorităţi generate aleator care să nu menţină arborele echilibrat.

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 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ă. Pe de altă parte, treapurile suportă şi alte două operaţii pe care nu le putem face cu $Arborii Roşu-Negrii$ sau cu arborii $AVL$. Aceste operaţii sunt '$join$':treapuri#join şi '$split$':treapuri#split.

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 se poate face cu uşurinţă în 20 de minute, fără antrenament. De obicei, la structuri ca $Arborii Roşu-Negru$ trebuie folosite serii de rotaţii stânga şi dreapta complexe şi analizată 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ă se preferă ca exemple didactice $Arborii Roşu-Negru$ sau cei $AVL$ care au o demonstraţie accesibilă că limita celei mai lente operaţii este $O(log N)$. 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ă. Pe de altă parte, treapurile suportă şi alte două operaţii pe care nu le putem face cu $Arborii Roşu-Negru$ sau cu arborii $AVL$. Aceste operaţii sunt '$join$':treapuri#join şi '$split$':treapuri#split.

h2(#operatii). Operaţii

    T *left, *right;
    T() {}
    T(int key, int priority, T* left, T* right) {

        this->key = key, this->priority = priority,
                    this->left = left, this->right = right;

        this->key = key, this->priority = priority;
        this->left = left, this->right = right;

    }

} *R, *nil;     // nil indica un nod 'gol'

} *R, *nil; // nil indica un nod 'gol'

void init(T* &R)
{

void init(T* &R) {

    srand(unsigned(time(0)));

 
    R = nil = new T();
    nil->key = nil->priority = 0,
        nil->left = nil->right = NULL;

    R = nil = new T(0, 0, NULL, NULL);

}
==

Căutarea într-un treap este identică cu cea într-un arbore binar de căutare. Pentru a verifica dacă o cheie există putem proceda în felul următor:
== code(cpp) |

int search(T* n, int key)
{
    if (n == nil)  return 0;
    if (key == n->key)  return 1;

int search(T* n, int key) {
    if (n == nil) return 0;
    if (key == n->key) return 1;

    if (key < n->key)
        return search(n->left, key);
    else

h3(#rotatii). Rotaţii

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

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

p=. !treapuri?Fig1d.png!

p=. !treapuri?Fig1.png!

p=. _*Figura 1*: Rotaţiile într-un arbore binar de căutare. Nodurile sunt reprezentate de cercuri iar subarborii de triunghiuri. Ambele operaţii de rotaţie menţin invariantul arborilor de căutare._

În cadrul operaţiei de inserare vom atribui unui nod nou o prioritate aleatoare şi îl vom insera, conform algoritmului standard de inserare într-un arbore binar, la baza arborelui. Să presupunem că dorim să inserăm nodul $z$ cu cheia $9$ şi prioritatea $51$.

p=. !treapuri?Fig2c.png!

p=. !treapuri?Fig2.png!

p=. _*Figura 2*: De la stânga la dreapta: inserarea nodului $z$. De la dreapta la stânga: ştergerea nodului $z$. Deoarece $z$ are prioritatea cea mai mare dintre toate nodurile, această inserare poate fi privită şi ca o operaţie de $split$. Subarborii stâng şi drept ai rădăcinii din ultima figură sunt chiar treapurile căutate: $T{~<~}$ şi $T{~>~}$. Invers, din $T{~<~}$ şi $T{~>~}$ se obţine, prin ştergerea rădăcinii, rezultatul operaţiei $join$._