Treap

Prerekvizity na čítanie tohto textu: od čitateľa očakávame, že už aspoň videl haldu a binárny vyhľadávací strom a že by vedel implementovať vyhľadávanie v už existujúcom binárnom strome.

O potrebe vyvažovaných stromov

Na obrázku nižšie sú štyri rôzne binárne vyhľadávacie stromy (binary search tree, BST). Všetky štyri obsahujú tú istú množinu prvkov, líšia sa však tvarom.

Pripomeňme si, že BST je zakorenený strom, v ktorom má každý vrchol nanajvýš jedného ľavého a nanajvýš jedného pravého syna. Navyše v každom vrchole platí podmienka BST: ľavý syn vrcholu $<$ vrchol $<$ pravý syn vrcholu.

Na tvare BST záleží. Čím je hlbší, tým dlhšie trvajú všetky operácie s ním: vyhľadávanie, vkladanie nového prvku, zmazanie existujúceho, atď. Samozrejme, tým, že ide o binárny strom, je jeho hĺbka zdola obmedzená: strom hĺbky $h$ môže mať nanajvýš $2^{h+1}-1$ vrcholov, a teda ak chceme strom s $n$ vrcholmi, musí jeho hĺbka byť aspoň logaritmická od $n$.

Existuje veľa rôznych spôsobov, ako zabezpečiť, že náš BST bude mať hĺbku $O(\log n)$, a teda že všetky operácie s ním budú rýchle. Najstaršia známa metóda je tá, ktorú používajú tzv. AVL-stromy. AVL-stromy sú BST, ktoré si v každom vrchole pamätajú "do ktorej strany sa nakláňa" a pomocou tejto informácie a šikovného robenia rotácií dosahujú, že strom je po každej operácii vyvážený (v nejakom špecifickom zmysle), z čoho potom vyplýva, že jeho hĺbka je určite logaritmická od počtu v ňom uložených prvkov.

V súčasnosti sa v praxi často používajú tzv. červeno-čierne stromy. Tie zabezpečujú "plytkosť" stromu pomocou inej techniky. Červeno-čierne stromy sú výbornou voľbou ak chceme vyrobiť robustnú knižnicu ­— majú totiž aj zaručenú časovú zložitosť $O(\log n)$ na všetky operácie, aj celkom dobrú rýchlosť v praxi. A skutočne, keď si napríklad v g++ pozriete implementáciu dátových štruktúr set a map, stretnete v nej práve červeno-čierne stromy.

Červeno-čierne stromy však majú jednu značnú nevýhodu: zložitú a dlhú implementáciu plnú všelijakých rozborov prípadov. Občas sa nám stane, že sa ocitneme v situácii, v ktorej si potrebujeme rýchlo implementovať vlastný BST. Vtedy by sme v prvom rade uvítali to, aby zdrojový kód bol čo najstručnejší a s čo najmenej špeciálnymi prípadmi. A práve takúto dátovú štruktúru si teraz ukážeme.

QuickSort a náhoda

Hlavným trikom pri návrhu nášho stromu bude použitie náhody. Ale skôr, ako sa pozrieme na stromy, sa oplatí spomenúť si na triedenie QuickSort. To v skutočnosti veľmi úzko súvisí s binárnymi vyhľadávacími stromami. Pri triedení QuickSort vyberieme pivota a následne ostatné prvky v poli rozdelíme na dve kôpky: na tie menšie ako pivot a na tie väčšie ako pivot. Pri BST vyberieme prvok, ktorý bude v koreni, a následne ostatné prvky rozdelíme na dve kôpky: na menšie, ktoré idú do ľavého podstromu, a na väčšie od koreňa, ktoré idú do pravého podstromu.

Aj pri QuickSorte vieme, že najhorší možný prípad je zlý: keby sme napr. ako pivota vždy zvolili najmenší spomedzi usporadovaných prvkov, dostali by sme lineárnu hĺbku rekurzie (a z toho vyplývajúcu kvadratickú časovú zložitosť). Podobne je to u BST: ak dáme vždy do koreňa najmenší zo všetkých prvkov, dostaneme BST, ktorý bude vlastne len jedna dlhá cesta ­— a teda budeme mať lineárnu hĺbku.

Pri QuickSorte si vieme pomôcť využitím náhody: dá sa dokázať, že ak pivota vždy volíme náhodne, tak takmer určite budeme mať len logaritmickú hĺbku rekurzie, a teda časovú zložitosť $O(n\log n)$. Intuícia za týmto tvrdením: aj keby sme vždy prvky rozdelili na povedzme 10% najmenších a 90% najväčších, dostali by sme strom rekurzie, ktorého všetky vetvy by mali len logaritmickú hĺbku. No a náhodne zvolený pivot nám pole aspoň takto dobre rozdelí s pravdepodobnosťou 80%.

Takéto niečo by sme chceli aj od nášho binárneho stromu: zoberieme naše prvky, nejak náhodne ich do stromu rozmiestnime a takmer určite dostaneme strom s logaritmickou hĺbkou.

No, sen je to pekný, ale so stromami je to predsa len o čosi ťažšie. Zatiaľ čo QuickSort je algoritmus, ktorý raz zbehne a je hotovo, strom potrebujeme dlhodobo udržiavať. Nestačí, keď bude v nejakom okamihu náhodne vyrobený. Potrebujeme, aby "prežil": aj keď doň postupne miliónkrát pridáme prvok, stále by sme chceli mať strom, ktorý bude v nejakom zmysle náhodný. Ako vieme takéto niečo dosiahnuť? Na scénu prichádza treap.

Treap

Na to, aby sme vrcholy v strome rozmiestnili náhodne, použijeme jednoduchý trik. Záznamy, ktoré budeme do stromu ukladať, budú mať dve zložky: kľúč a prioritu.

Kľúč je hodnota, ktorú sme tam mali aj doteraz ­— teda to, podľa čoho prvky v strome usporadúvame, vyhľadávame, atď. Priorita je nový údaj, pomocou ktorého si náhodne zvolíme tvar stromu. V tomto texte budeme ako priority používať náhodné reálne čísla z intervalu od 0 po 1 a budeme ticho predpokladať, že žiadne dva prvky v strome nemajú presne rovnakú prioritu.

Keď si nižšie budeme ukazovať obrázky treapov, budeme v každom vrchole udávať usporiadanú dvojicu (kľúč,priorita). Nezabudnite však na to, že sa tam môžu okrem nich nachádzať aj iné údaje. Môžeme napríklad mať treap, ktorý má v každom vrchole uložený záznam o jednom riešiteľovi KSP, pričom ako kľúč používame jeho login. Takéto údaje však kvôli lepšej prehľadnosti v obrázkoch vynecháme.

Ako nám pomôžu priority náhodne určiť tvar nášho stromu?

Už vieme jednu vlastnosť, ktorú budeme od treapu požadovať: musí to stále byť BST. Presnejšie, keď sa budeme pozerať len na kľúče, musíme vidieť obyčajný BST. Druhá vlastnosť bude veľmi podobná, aj keď vás možno prekvapí: keď sa budeme pozerať len na priority prvkov, musíme vidieť binárnu haldu. V každom vrchole teda musí platiť, že jeho priorita je väčšia ako priorita každého z jeho synov.

Odtiaľ pochádza aj samotný názov našej dátovej štruktúry: slovo "treap" je kombináciou slov "tree" a "heap".

Existencia treapov

Počkať, počkať. Halda? Čo už je len toto za výmysel? Dá sa to vôbec dodržať? Čo ak máme zrovna také priority, pre ktoré to nejde?

Začnime tým, že sa na jeden treap pozrieme. Na obrázku si môžeme overiť, že všetky kľúče (prvé údaje) naozaj spĺňajú podmienku BST a všetky priority (druhé údaje) spĺňajú podmienku haldy.

Čo to vlastne znamená, že priority spĺňajú podmienku haldy? Znamená to v prvom rade to, že prvok s najväčšou prioritou je určite v koreni celého stromu. Ak by pred nás niekto vysypal kopu prvkov (každý s nejakým kľúčom a nejakou prioritou), už vieme, čo by sme spravili v prvom kroku: našli by sme ten s najväčšou prioritou a dali by sme ho do koreňa.

Čo vieme povedať ďalej? Keďže kľúče majú tvoriť BST, akonáhle vieme, čo máme v koreni, tak je jednoznačne určené, ktoré prvky patria do ľavého podstromu a ktoré do pravého.

No a v každom podstrome môžeme teraz celú úvahu opakovať. Napríklad koreňom ľavého podstromu sa stane ten spomedzi prvkov v ňom, ktorý má spomedzi tých prvkov najväčšiu prioritu. A tak ďalej, až kým nevyrobíme celý treap.

Z vyššie uvedeného postupu vyplýva dôležité tvrdenie: Pre ľubovoľnú sadu dvojíc (kľúč,priorita) existuje presne jeden platný treap.

Na toto tvrdenie sa môžeme dívať nasledovne: tým, že sme každému prvku vygenerovali náhodnú prioritu, sme si vlastne náhodne zvolili tvar nášho stromu. A ako dobrá je táto náhodná voľba? Aby sme získali nejakú intuíciu, vráťme sa v myšlienkach ku našej analógii s QuickSortom. V našom strome sa deje niečo veľmi podobné. V každom podstrome treapu totiž platí, že každý prvok, ktorý sa doň dostal, mal rovnakú pravdepodobnosť toho, že práve on bude v tom podstrome koreňom. Najlepšie to je vidieť v koreni celého stromu: každý z našich $n$ prvkov mal na začiatku pravdepodobnosť $1/n$, že zrovna on dostane najväčšiu prioritu. Tým, že sme prvkom priradili náhodné priority, sme si teda koreň nášho treapu vybrali rovnomerne náhodne.

Zhrnutie

Zhrňme si, čo zatiaľ o treapoch vieme:

• Treap je binárny strom, do ktorého ukladáme dvojice (kľúč, priorita).
• Kľúče (a k ním priradené ďalšie dáta) sú tie údaje, ktoré nás naozaj zaujímajú.
• Ak sa pozeráme len na kľúče, vidíme obyčajný BST.
• Ak sa pozeráme len na priority, vidíme haldu.
• Kľúčmi a prioritami sú jednoznačne určené tvar treapu aj rozmiestnenie prvkov v ňom.
• Tým, že priority volíme náhodne, si vlastne implicitne náhodne zvolíme tvar stromu.
• Autori treapu už za nás poriadne dokázali, že skoro vždy bude hĺbka treapu logaritmická od počtu prvkov v ňom.

Treapy teda môžeme používať ako efektívnu implementáciu BST. O chvíľu si ukážeme, ako ich implementovať šikovne a veľmi, veľmi stručne.