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 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 valoare 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 Treapului. 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. 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 în care putem fi puşi 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.

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.

Cazurile simetrice sunt imaginea în oglindă pentru cazurile de mai sus. Astfel, va fi necesar să facem o rotaţie spre stânga.