Astfel, din moment ce $T$ este un heap, nodul $v$ cu prioritatea cea mai mare trebuie să fie rădăcina. Cum este şi un arbore binar de căutare, orice nod $u$ cu $cheie(u) < cheie(v)$ se găseşte în subarborele stâng al lui $v$, şi orice nod $w$ cu $cheie(w) > cheie(v)$ se găseşte în subarborele drept.

Este important să reţinem că un Treap este determinat în mod unic de chei şi de priorităţi. Prin inducţie se demonstrează că Treapul este arborele binar obţinut prin inserarea cheilor în ordinea descrescătoare a priorităţilor. Algoritmul de inserare este cel obişnuit pentru arborii de căutare. Astfel, cum fiecare set de priorităţi asociat nodurilor va aranja arborele într-un singur mod, probabilitatea ca arborele să fie echilibrat este rezonabil de mare, fapt datorat numărului mic al arborilor rău echilibraţi în comparaţie cu cei echilibraţi. Iată şi secretul Treapurilor: probabilitatea infimă de a se găsi o serie de priorităţi generate aleator care să nu menţină arborele echilibrat.

Cheile şi priorităţile determină în mod unic forma unui Treap. Prin inducţie se demonstrează că Treapul este arborele binar obţinut prin inserarea cheilor în ordinea descrescătoare a priorităţilor. Algoritmul de inserare este cel obişnuit pentru arborii de căutare. Astfel, cum fiecare set de priorităţi asociat nodurilor va aranja arborele într-un singur mod, probabilitatea ca arborele să fie echilibrat este rezonabil de mare, fapt datorat numărului mic al arborilor rău echilibraţi în comparaţie cu cei echilibraţi. Iată şi secretul Treapurilor: probabilitatea infimă de a se găsi o serie de priorităţi generate aleator care să nu menţină arborele echilibrat.

h2(#avantaje). Avantaje