h1. Treap-uri

(toc){width: 33em}*{text-align:left} *Cuprins:*
* '1. Ce este un Treap?':treapuri#ceeste
* '2. Avantaje':treapuri#avantaje
* '3. Operaţii':treapuri#operatii
** 'Căutare':treapuri#cautare
** 'Rotaţii':treapuri#rotatii
** 'Inserare':treapuri#inserare
** 'Ştergere':treapuri#stergere
* '4. Implementare':treapuri#cod

Î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$.

 
Î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. Ce este un _Treap_?

Treap-ul este un arbore binar în care fiecare nod conţine două informaţii:

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.

h2(#avantaje). Avantaje

h2. 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.

h2(#operatii). Operaţii

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(#cautare). Căutare

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:

Se observă că algoritmul poate fi scris şi iterativ, lucru ce este recomandat.

h3(#rotatii). Rotaţii

h3. Rotaţii

Să urmărim (în desen) efectul rotaţiilor asupra structurii de heap a arborelui. Pentru început, 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.

Complexitate: $O(1)$.

h3(#inserare). Inserare

h3. Inserare

În cadrul operaţiei de inserare vom atribui unui nod nou o prioritate şi îl vom insera, conform algoritmului standard de inserare într-un arbore binar, la baza arborelui. Cheile formează un arbore de căutare, dar priorităţile pot să nu mai formeze un heap. Pentru a redobândi această proprietate, cât timp nodul $z$ are prioritate mai mare decât părintele său, se execută o $rotaţie$ în $z$, o operaţie locală care scade nivelul lui $z$ cu $1$ şi creşte nivelul părintelui lui $z$ cu $1$, timp în care invariantul arborilor de căutare este menţinut. Timpul de inserare a lui $z$ este proporţional cu adâncimea lui înainte de rotaţii - trebuie să coborâm după care să urcăm înapoi efectuând rotaţiile necesare.
Complexitate: $O(log N)$.

h3(#stergere). Ştergere

h3. Ştergere

Operaţia de ştergere este inversul operaţiei de inserare. (Se va desena o figură) Să presupunem că vrem să ştergem nodul $z$. Cât timp $z$ nu este o frunză, alegem fiul $w$ cu prioritatea mai mare şi facem o rotaţie pentru a aduce pe $w$ în locul lui $z$. Astfel, după cum este explicat la rotaţii, nivelul lui $z$ scade cu $1$ până când va deveni frunză, iar arborele va redobândi structura de heap pentru priorităţi.

_De adăugat: split, join, print, 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ă, explicarea rotaţiilor (cum şi de ce se menţin invarianţii)._

h2(#cod). Coding

h2. Coding

Vă puteţi uita, ca şi comparaţie, la funcţiile $erase$ sau $balance$ din articolul următor despre arborii "AVL":multe-smenuri-de-programare-in-cc-si-nu-numai#AVL.