* $prioritatea fiecărui nod este mai mare decât cea a fiilor săi (invariantul heapurilor)$

În consecinţă, Treapul este un arbore binar de căutare pentru chei şi un max-heap pentru priorităţi.

În consecinţă, treapul este un arbore binar de căutare pentru chei şi un max-heap pentru priorităţi.

În continuare, vom presupune că toate cheile şi priorităţile din Treapul $T$ sunt distincte. În practică, presupunerea aceasta are un impact neglijabil.

În continuare, vom presupune că toate cheile şi priorităţile din treapul $T$ sunt distincte. În practică, presupunerea aceasta are un impact neglijabil.

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.

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 Treapurilor: 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 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 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 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 teoriei probabilităţilor se poate deduce că adâncimea aşteptată a oricărui nod este $O(log N)$, ceea ce implică costul celor mai lente operaţii să fie $O(log N)$.

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 teoriei probabilităţilor se poate deduce că adâncimea aşteptată a oricărui nod este $O(log N)$, ceea ce implică costul celor mai lente 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 cheie există putem proceda în felul următor:

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)

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 unui Treap care respectă doar invariantul arborilor de căutare. Aşadar, 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!

Să urmărim (în desen) efectul rotaţiilor asupra structurii de heap a unui treap care respectă doar invariantul arborilor de căutare. Aşadar, 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!

O altă situaţie 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.

h3(#join). Join

Operaţia $join$ constă în unirea a două treapuri $T{~<~}$ şi $T{~>~}$, unde fiecare cheie din $T{~<~}$ este mai mică decât oricare cheie din $T{~>~}$, într-un singur super-treap. Unirea se realizează în mod invers operaţiei de $split$ prin inserarea unui nod ajutător $z$ drept rădăcină, ce are ca subarbore stâng pe $T{~<~}$ iar ca subarbore drept pe $T{~>~}$, pe care îl vom suprima.

Operaţia $join$ constă în unirea a două treapuri $T{~<~}$ şi $T{~>~}$, unde fiecare cheie din $T{~<~}$ este mai mică decât oricare cheie din $T{~>~}$, într-un singur super-treap. $Join$ se realizează în mod invers operaţiei de $split$ prin crearea unei rădăcini $z$, ce are ca subarbore stâng pe $T{~<~}$ iar ca subarbore drept pe $T{~>~}$, pe care o vom suprima.

Costul operaţiei $join$ este egal cu costul operaţiei de '$ştergere$':treapuri#stergere a lui $z$.