h1. Treap-uri

h1. Treapuri

(toc){width: 33em}*{text-align:left} *Cuprins:*
* '1. Ce este un Treap?':treapuri#despreTreap

h3(#stergere). Ş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':treapuri#rotatii, nivelul lui $z$ scade cu $1$ până când va deveni frunză iar arborele va redobândi structura de heap.

Operaţia de ştergere este inversul operaţiei de inserare. (Se va desena o figură) Dacă dorim să suprimăm nodul $z$, atunci 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':treapuri#rotatii, nivelul lui $z$ scade cu $1$ până când devine o frunză. La finalul algoritmului, după ştergerea lui $z$, arborele va redobândi structura de heap.

Complexitate: $O(log N)$.