Rotaţiile sunt cărămizile de la baza structurii de treap.

p=. !treapuri?Fig1.png!

p=. !treapuri?Fig1-ok.png!

p=. _*Descriere:* Rotaţiile într-un arbore binar de căutare. Nodurile sunt reprezentate de cercuri, iar subarborii de triunghiuri. Ambele operaţii de rotaţie menţin invariantul arborilor de căutare._

p=. _Rotaţiile într-un arbore binar de căutare. Nodurile sunt reprezentate de cercuri, iar subarborii de triunghiuri. Ambele operaţii de rotaţie menţin invariantul arborilor de căutare._

Să urmărim 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 vedem în figura a doua 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.

p=. !treapuri?Fig2.png!

p=. _*Descriere:* De la stânga la dreapta: inserarea nodului $z$. De la dreapta la stânga: ştergerea nodului $z$. Deoarece $z$ are prioritatea cea mai mare dintre toate nodurile, această inserare poate fi privită şi ca o operaţie de $split$. Subarborii stâng şi drept ai rădăcinii din ultima figură sunt chiar treapurile căutate: $T{~<~}$ şi $T{~>~}$. Invers, din $T{~<~}$ şi $T{~>~}$ se obţine, prin ştergerea rădăcinii, rezultatul operaţiei $join$._

p=. _De la stânga la dreapta: inserarea nodului $z$. De la dreapta la stânga: ştergerea nodului $z$. Deoarece $z$ are prioritatea cea mai mare dintre toate nodurile, această inserare poate fi privită şi ca o operaţie de $split$. Subarborii stâng şi drept ai rădăcinii din ultima figură sunt chiar treapurile căutate: $T{~<~}$ şi $T{~>~}$. Invers, din $T{~<~}$ şi $T{~>~}$ se obţine, prin ştergerea rădăcinii, rezultatul operaţiei $join$._

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 a lui $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.