h3(#inserare). Inserare

În cadrul operaţiei de inserare vom atribui unui nod nou o prioritate aleatoare şi îl vom insera, conform algoritmului standard de inserare într-un arbore binar, la baza arborelui. Să presupunem că dorim să inserăm nodul $z$ cu cheia $9$ şi prioritatea $51$.

p=. !treapuri?Fig2b.png!

p=. !treapuri?Fig2c.png!
 
p=. _*Figura 2*: De la stânga la dreapta: inserarea nodului $z$. De la dreapta la stânga: ştergerea nodului $z$._
 
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 de inserat, are prioritatea mai mare decât a părintelui său, se va executa o '$rotaţie$':treapuri#rotatii în $z$, o operaţie locală care scade nivelul lui $z$ cu $1$ şi creşte nivelul părintelui lui $z$ cu $1$, şi care menţine invariantul arborilor de căutare. Timpul de inserare al 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.

În cadrul operaţiei de inserare vom atribui unui nod nou o prioritate aleatoare ş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 de inserat, fie el $z$, are prioritatea mai mare decât a părintelui său, se va executa o '$rotaţie$':treapuri#rotatii în $z$, o operaţie locală care scade nivelul lui $z$ cu $1$ şi creşte nivelul părintelui lui $z$ cu $1$, şi care menţine invariantul arborilor de căutare. Timpul de inserare al 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)$.