Treapy budeme implementovať podobne ako každý iný strom. V tomto texte si ukážeme ich implementáciu v C++. Začneme tým, že si vyrobíme štruktúru predstavujúcu jeden vrchol stromu. Tá môže vyzerať napríklad nasledovne:
struct item {
// kľúč je nejakého konkrétneho typu T
T key;
// priorita je celé číslo, lebo je zbytočné z rand() vyrábať číslo reálne
int priority;
// pointre na ľavého a pravého syna
item *l, *r;
// a ešte konštruktor, ktorý k danému kľúču priradí náhodnú prioritu
item(const T &key) : key(key), priority(rand()), l(NULL), r(NULL) {}
};
// pointer na item si nazveme pitem, nech je v neskoršom kóde menej *
typedef item* pitem;
Vyhľadávať v treapoch sa dá rovnako ako v klasickom BST, tam nie je čo zlepšovať. Chceli by sme ale vedieť robiť operácie insert a erase: teda vkladať a vyberať prvky. Ako na to? Dalo by sa to robiť aj priamo, ale takáto implementácia je zbytočne zložitá. My na to pôjdeme "od lesa": ukážeme si dve iné operácie, ktoré sa obe implementujú veľmi ľahko, a potom si insert aj delete vyrobíme v podstate zadarmo.
Prvou operáciou bude split.
Split je jednoduchá operácia. Na vstupe dostane dve veci: treap $T$, uložený niekde v pamäti, a hodnotu kľúča $x$. Táto operácia prerobí treap $T$ na dva treapy $T_1$ a $T_2$. V treape $T_1$ skončia tie prvky $T$, ktoré majú kľúč menší alebo rovný $x$, v treape $T_2$ skončia všetky ostatné prvky. Dôležité je, že táto operácia zničí pôvodný treap $T$. Nič sa teda nikam nekopíruje, len presmerujeme niektoré pointre medzi vrcholmi tak, aby sa pôvodný treap rozpadol na dva menšie.
Ako spraviť split? Začneme v koreni. Ak ten patrí (podľa svojho kľúča) do $T_1$, tak aj celý ľavý podstrom patrí do $T_1$. Rekurzívne teda zavoláme split na pravý podstrom. Ten sa nám rozpadne na dve časti: ľavú, ktorá ešte patrí do $T_1$, a pravú, ktorou je celé $T_2$. Už len teda ľavú časť, ktorú nám vrátilo rekurzívne volanie, zavesíme pod koreň $T_1$ ako jeho pravý podstrom a sme hotoví. No a ak koreň patrí už do T2, tak spravíme to isté, len v jeho ľavom podstrome.
Tu je celá implementácia:
// split:
// — v premenných t, key dostane vstup
// — do premenných l, r vyplní výstup, teda pointre na korene treapov T1 a T2
void split(pitem t, T key, pitem &l, pitem &r) {
if (!t) { l = r = NULL; return; }
if (key < t->key) {
split(t->l, key, l, t->l);
r = t;
} else {
split(t->r, key, t->r, r);
l = t;
}
}
Druhou operáciou bude merge. Tú si je najlepšie zapamätať ako "undo split". Vstupom pre merge sú teda dva treapy $T_1$ a $T_2$. Ale nie len tak hocijaké: musí platiť, že každý kľúč v $T_1$ je menší ako každý kľúč v $T_2$. (Inými slovami, platným vstupom pre merge je výstup splitu.) Operácia merge v pamäti prehádže pointre tak, aby tieto dva menšie treapy spojila do jedného.
Ako spraviť merge? Začneme tým, že sa pozrieme na korene oboch menších treapov. Ten z nich, ktorý má väčšiu prioritu, bude zjavne koreňom výsledného treapu. Čo sa stane, ak je to koreň treapu $T_1$? Jeho ľavý podstrom ostane nedotknutý. A jeho nový pravý podstrom vznikne tak, že mergneme dokopy jeho súčasný pravý podstrom a celý treap $T_2$. (V tomto kroku sme využili pozorovanie, že všetky kľúče v $T_2$ sú väčšie ako kľúč z koreňa $T_1$, a teda celý $T_2$ patrí do jeho pravého podstromu.) No a ak celkovým koreňom bude pôvodný koreň $T_2$, stane sa to isté, len symetricky.
Celá implementácia tejto myšlienky má opäť len pár riadkov:
// merge:
// — v premenných l, r dostane vstup
// — do premennej t vyplní výstup, teda pointer na koreň spojeného treapu
void merge(pitem &t, pitem l, pitem r) {
if (!l || !r) {
t = l ? l : r;
return;
}
if (l->priority > r->priority) {
merge(l->r, l->r, r);
t = l;
} else {
merge(r->l, l, r->l);
t = r;
}
}
No dobre. Vieme split a merge. My sme ale chceli robiť insert a delete! Ako na ne?
Insert sa teraz spraví ľahko. Máme treap a dostali sme nový prvok, ktorý doň chceme vložiť. (Pre jednoduchosť predpokladajme, že sa prvok s týmto kľúčom ešte v treape nenachádza. Ak potrebujeme zahadzovať duplikáty, spravili by sme najskôr kontrolu, či tento prvok už v treape máme.)
Začneme v koreni treapu. Opäť sú len dve možnosti. Prvou je, že náš nový prvok má prioritu menšiu ako koreň treapu. V takomto prípade porovnáme ich kľúče, aby sme zistili, či náš prvok patrí do ľavého alebo pravého podstromu. A keď to už vieme, tak ho do príslušného podstromu vložíme rekurzívnym volaním funkcie insert.
Druhou možnosťou je, že náš nový prvok má od aktuálneho väčšiu prioritu. Čo vtedy? Nuž, vtedy sa má náš nový prvok stať koreňom. Zavoláme teda na náš pôvodný treap funkciu split, pričom ako kľúč použijeme kľúč práve vkladaného prvku. Dostaneme tak treapy $T_1$ a $T_2$. Náš nový prvok bude koreňom treapu a treapy $T_1$ a $T_2$ budú jeho ľavým a pravým podstromom.
Vo všeobecnosti sa teda stane to, že začneme v koreni a podľa kľúča spravíme niekoľko krokov dodola, až kým sa nedostaneme na miesto, kam už náš vkladaný prvok podľa priority patrí. V tej chvíli zavoláme split, príslušný podstrom rozbijeme na dva menšie kusy a medzi ne vložíme ten nový prvok.
Implementácia je opäť veľmi stručná:
void insert(pitem &t, pitem it) {
if (!t) {
t = it;
return;
}
if (it->priority > t->priority) {
split(t, it->key, it->l, it->r);
t = it;
} else {
insert(it->key < t->key ? t->l : t->r, it);
}
}
A ako sa prvky maže? Ešte ľahšie.
Ak je prvok, ktorý chceme zmazať, priamo v koreni, tak ho zmažeme, zavoláme merge na jeho podstromy a máme hotovo. A ak nie je v koreni, tak sa len rekurzívne zavoláme na podstrom, v ktorom sa (podľa kľúča) nachádza.
void erase(pitem &t, T key) {
if (!t) return;
if (t->key == key) merge(t, t->l, t->r);
else erase(key < t->key ? t->l : t->r, key);
}
Tak, a to je všetko. Tieto štyri stručné metódy už dokopy tvoria plnohodnotný vyvažovaný binárny vyhľadávací strom.