Complexitate: $O(log N)$.

h3(#split). Split

_De adăugat: split, join, print, meld {$O(mlog(n/m))$} - unirea a două treapuri T1 şi T2 fără nicio relaţie de ordine între ele, difference $O(mlog(n/m))$ - din T1 şi T2 rezultă un T care conţine cheile din T1 care nu sunt în T2, interpretarea geometrică, explicarea rotaţiilor (cum şi de ce se menţin invarianţii)._

Uneori dorim să despărţim treapul $T$ în două treapuri $T{~<~}$ şi $T{~>~}$ astfel încât cheile din $T{~<~}$ să conţină cheile din $T$ mai mici decât o cheie $key$ dată, iar $T{~>~}$ să conţină cheile din $T$ mai mari decât aceeaşi cheie $key$. Soluţia constă în inserarea unui nod ajutător $z$ a cărui cheie este $key$ şi prioritate $infinit$. După inserare, $z$ va fi rădăcina arborelui, având prioritatea cea mai mare. Dacă ştergem rădăcina, subarborele stâng şi cel drept vor fi exact treapurile căutate.
 
Costul operaţiei $split$ este egal cu costul operaţiei de '$inserare$':treapuri#inserare a lui $z$.
 
Complexitate: $O(log N)$.
 
h3(#join). Join
 
Operaţia $join$ constă în unirea a două treapuri $T{~<~}$ şi $T{~>~}$, unde fiecare cheie din $T{~<~}$ este mai mică decât oricare cheie din $T{~>~}$, într-un singur super-treap. Unirea se realizează în mod invers operaţiei de $split$ prin inserarea unui nod ajutător $z$ drept rădăcină, ce are ca subarbore stâng pe $T{~<~}$ iar ca subarbore drept pe $T{~>~}$, pe care îl vom suprima.
 
Costul operaţiei $join$ este egal cu costul operaţiei de '$ştergere$':treapuri#stergere a lui $z$.
 
Complexitate: $O(log N)$.

h2(#cod). Coding