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 medie aşteptată a oricărui nod este $O(log N)$, ceea ce implică costul celor mai lente operaţii să fie, în medie, $O(log N)$.

Mai jos avem definiţia în cod $C++$ a unui treap şi o funcţie de iniţializare, care marchează că treapul cu rădăcina $R$ este gol.