h3(#split). Split

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 iar subarborii stâng şi drept ai rădăcănii vor fi exact treapurile căutate.

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