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 unei 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 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