În acest articol voi prezenta o alternativă pentru arborii binari de căutare echilibraţi, precum $AVL$, $Red-Black Trees$, $Splay Trees$ şi $B-Trees$.
h2(#ceeste). Ce este un _Treap_?
h2(#despreTreap). Ce este un Treap?
Treap-ul este un arbore binar în care fiecare nod conţine două informaţii:
Treapul este un arbore binar în care fiecare nod conţine două informaţii:
* $cheie$;
* $prioritate$.
* $prioritate$
Structura de date respectă doi invarianţi:
* _dacă parcurgem arborele în inordine, atunci vom obţine nodurile sortate_; (invariantul arborilor de căutare)
* $dacă parcurgem arborele în inordine, atunci vom obţine nodurile sortate (invariantul arborilor de căutare)$
* _prioritatea fiecărui nod este mai mare decât cea a fiilor săi_. (invariantul heapurilor)
* $prioritatea fiecărui nod este mai mare decât cea a fiilor săi (invariantul heapurilor)$
În consecinţă, treap-ul 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 Treap-ul $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.
Este important să reţinem că un Treap este determinat în mod unic de chei şi de priorităţi. 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.
Este important să reţinem că un Treap este determinat în mod unic de chei şi de priorităţi. 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.
h2(#avantaje). Avantaje
Heapurile şi Arborii Binari de Căutare sunt uşor de implementat şi de înţeles, iar treapurile sunt o combinaţie a acestor două concepte. Astfel, e suficient să fie înţeles invariantul, 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 mulţime de cazuri, pe când la Treapuri facem doar câte o rotaţie stânga sau o rotaţie dreapta la fiecare pas al algoritmului. Ei nu sunt predaţi pentru că Arborii Roşu-Negrii sau AVL au demonstraţia că merg în $O(log N)$ şi sunt exemple didactice, dar Treapurile, deşi cu o demonstraţie mai grea, sunt mult mai uşori de implementat şi poate şi puţin mai rapizi ca arborii AVL.
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 şi cu siguranţă greu de decis în practică care sunt mai rapizi. Sunt deci, o opţiune demnă de luat în seamă.
h2(#operatii). Operaţii
