Recepty z programátorské kuchařky
Treapy

Dnes si ukážeme datovou strukturu zvanou treap. Treapy jsou odrůdou binárních vyhledávacích stromů. Ovšem místo abychom je pracně udržovali vyvážené, použijeme jednoduché pravidlo založené na náhodných číslech. Díky němu budou treapy v průměru stejně rychlé jako vyvážené stromy, ale budou mnohem jednodušší. Také treapy naučíme mnoho dalších operací a nakonec vymyslíme, jak pomocí nich reprezentovat posloupnosti. Začneme ovšem trošku netradičně binárním vyhledáváním.

Binární vyhledávání

Při konstrukci vyhledávacích stromů vyjdeme z binárního vyhledávání. Proto si ho nejprve připomeneme:

Máme obrovské pole setříděných záznamů, třeba identifikačních čísel studentů nejmenované univerzity (záznamy však nemusí být čísla, stačí, když jsou navzájem porovnatelné). Naším úkolem je najít záznam z v poli s N záznamy x₁ < x₂ < … < x_N.

Při použití binárního vyhledávání neboli půlení intervalu se podíváme na prostřední záznam x_m a porovnáme s ním naše z. Pokud z<x_m, víme, že se z nemůže vyskytovat „napravo“ od x_m, protože tam jsou všechny záznamy větší než x_m, a tím spíše než z. Analogicky pokud z>x_m, nemůže se z vyskytovat v první polovině pole. V obou případech nám zbude jedna polovina a v ní budeme pokračovat stejným způsobem. Tak budeme postupně půlit interval, ve kterém se z může nacházet, až buďto z najdeme, nebo vyloučíme všechny prvky, kde by prvek mohl být.

Tento algoritmus můžeme naprogramovat buďto rekurzivně, nebo pomocí cyklu, v němž budeme udržovat interval <l,r>, ve kterém se hledaný prvek ještě může nacházet. My si ukážeme přístup s cyklem:

def bin_najdi(z):
    levy = 0
    pravy = N
    while levy <= pravy:
        median = (levy+pravy)//2
        # hledaná hodnota je vlevo
        if z < x[median]:
            pravy = median - 1
        # je vpravo
        elif z > x[median]:
            levy = median+1
        # našli jsme přímo hodnotu
        else:
            return median
        # hledaná hodnota nebyla nikde
        return -1

int bin_najdi(int z) {
    int levy, pravy, median;
    // interval, ve kterém hledáme
    levy = 0; pravy = N;
    // dokud interval ještě není prázdný
    while (levy <= pravy) {
        median = (levy+pravy)/2;
        // hledaná hodnota je vlevo
        if (z < x[median])
            pravy = median-1;
        // je vpravo
        else if (z > x[median])
            levy = median+1;
        else // našli jsme ji
            return median;
    }
    return -1; // hledaná hodnota nebyla nikde
}

Binární vyhledávání je velmi rychlé, pokud máme možnost si data předem setřídit. Jakmile ale potřebujeme za běhu programu přidávat a odebírat záznamy, se zlou se potážeme. Buďto budeme mít záznamy uložené v poli a pak nezbývá než při zatřiďování nového prvku ostatní „rozhrnout“, což může trvat až N kroků, anebo si je budeme udržovat v nějakém seznamu. Do něho dokážeme přidávat v konstantním čase, jenže pak pro změnu nebudeme při vyhledávání schopni najít tolik potřebnou polovinu.

Vyhledávací stromy

Představme si, jakými všemi možnými cestami se může v našem poli binární vyhledávání ubírat. Na začátku porovnáváme s prostředním prvkem a podle výsledku se vydáme jednou ze dvou možných variant (nebo rovnou zjistíme, že se jedná o hledaný prvek, ale to není moc zajímavý případ). V každé variantě nás zase čeká porovnání se středem příslušného intervalu a výsledek nás opět pošle jednou ze dvou dalších variant atd. To můžeme přehledně popsat pomocí stromu:

Jeden vrchol stromu prohlásíme za kořen a ten bude odpovídat celému poli (a jeho prostřednímu prvku). K němu budou připojené vrcholy obou polovin pole (opět obsahující příslušné prostřední prvky) a tak dále. Ovšem jakmile známe tento strom, můžeme náš půlící algoritmus provádět přímo podle stromu (ani k tomu nepotřebujeme vidět původní pole a umět v něm hledat poloviny): začneme v kořeni, porovnáme a podle výsledku se buďto přesuneme do levého, nebo pravého podstromu, a tak dále. Každý průběh algoritmu bude tedy odpovídat nějaké cestě z kořene stromu do hledaného vrcholu.

V každém vrcholu budeme mít uložený klíč, což bude hodnota onoho prostředního prvku. Podle klíčů se pak bude porovnávat.

Teď si ale všimněte, že aby hledání klíče podle stromu fungovalo, strom vůbec nemusel vzniknout půlením intervalu – stačilo, aby v každém vrcholu platilo, že všechny klíče v levém podstromu jsou menší než tento vrchol a naopak klíče v pravém podstromu větší. Hledání v témže poli by také popisovaly následující stromy (např.):

Hledací algoritmus podle jiných stromů samozřejmě už nemusí mít pěknou logaritmickou složitost (kdybychom hledali podle „degenerovaného“ stromu z pravého obrázku, trvalo by to dokonce lineárně). Důležité ale je, že takovéto stromy se dají poměrně snadno modifikovat a že je při troše šikovnosti můžeme udržet dostatečně podobné ideálnímu půlení intervalu. Pak bude hloubka stromu stále O(log N), tím pádem i časová složitost hledání, a jak za chvilku uvidíme, i mnohých dalších operací.

Vyvažování stromů

Existují algoritmy, které umí udržovat stromy při přidávání a odebírání tak, aby jejich hloubka byla O(log N).

Jedním z takovýchto algoritmů jsou AVL stromy. Jejich implementace je ale poměrně zdlouhavá, a proto si dnes ukážeme jednodušší (v některých ohledech ale trošku horší) řešení.

Treap

Při vyvažování si pomůžeme náhodou. V každý moment bude strom uspořádán nějak náhodně. Díky tomu bude opravdu malá šance, že by se jeho tvar podobal cestě.

Každému vrcholu při vytváření přiřadíme náhodně vybrané číslo z nějakého intervalu. Toto číslo označme jako prioritu.

Náš strom pak vždy bude splňovat tuto podmínku: Každý vrchol má menší nebo stejnou prioritu než každý jeho syn. Tedy strom bude na prioritách splňovat podmínky haldy. Z toho také název treap, který je spojením tree a heap. Pak platí následující tvrzení.

Věta: V případě, že jsou priority po dvou různé a klíče také, existuje pouze jeden možný tvar stromu.

Důkaz: Pojďme zkusit strom postavit. Do kořene musíme umístit vrchol s nejmenší prioritou. Ostatní vrcholy pak můžeme rozdělit podle toho, jestli mají větší nebo menší klíč než kořen. Z toho nám vzniknou dvě skupiny (mohou být i prázdné). Z každé musíme postavit jeden podstrom kořene. Na to rekurzivně použijeme stejný algoritmus.

Všechny kroky při vytváření ovšem jsou jednoznačné, a tedy existuje pouze jeden výsledek. Q.E.D.

V případě, že se vyskytne několik stejných priorit, tak už konstrukce nebude jednoznačná. Ovšem všimneme si, že rozdíly budou jen lokální. Tedy v případě, že shodných priorit nebude moc, možné tvary treapu se nebudou moc lišit. Priority tedy stačí vybírat jako (pseudo)náhodná čísla a nemusíme kolize nijak speciálně řešit.

Povšimněte si analogie s Quicksortem. V něm náhodně vybereme prvek a ostatní rozdělíme na dvě skupiny, které také zpracujeme rekurzivně. Jelikož jsou priority přidělovány náhodně, tak také vlastně vybíráme náhodný prvek. U obou algoritmů pak jen doufáme, že rekurze nebude moc hluboká, a tím pádem nám výpočty nezaberou moc času.

Přesněji řečeno platí, že pro libovolné klíče bude průměrná hloubka treapu O(log N). Průměrujeme přitom pouze přes náhodný výběr priorit, na klíčích nezáleží.

Dokázat toto tvrzení je ale poměrně složité, proto ho zde uvádíme pouze bez důkazu. Zájemci si mohou přečíst článek (v angličtině), případně si poslechnout přednášku.

Dodejme ještě, že v případě různých klíčů existuje jen jedna možnost postavení treapu, tak nezáleží na tom, jakým postupem vznikl.

Základní operace: Merge a Split

V předchozí části jsme ukázali, co to treap je. Ovšem kdybychom s ním neuměli dělat nic jiného, než vyhledávání a postavení, tak by pro nás nebyl moc užitečný. Mohli bychom ho jednoduše nahradit binárním vyhledáváním v poli.

Nyní přidáme dvě poměrně nezajímavě vypadající operace a pomocí nich pak vybudujeme většinu ostatních operací.

Popišme vrchol treapu následující strukturou:

class Node:
    left = None
    right = None

    def __init__(self, priority, key):
        self.priority = priority
        self.key = key

struct Treap
{
	Treap *left, *right;
	int key;
	int priority;
};

Struktura tedy obsahuje dvě položky, kam lze umístit levý a pravý podstrom. Dále ještě obsahuje klíč a prioritu.

Merge. Tato operace vezme dva treapy a spojí je do jednoho. Ovšem musí platit, že všechny klíče v prvním z nich budou menší (nebo případně stejné) než klíče v druhém z nich.

Merge vstupní treapy rozebere a složí z nich svůj výsledek. Neprovádí žádné kopírování do nového stromu – to by bylo moc pomalé.

Pojďme nový treap postupně stavět. Sledujme obrázek:

Začneme od kořene. Tam dle definice musíme umístit vrchol s nejmenší prioritou. To ale musí být jeden z kořenů zdrojových treapů.

Dále uvažujeme, že se jedná o kořen prvního (levého) treapu. V opačném případě provedeme totéž, jen s prohozením stran. Všechny prvky v levém podstromu levého treapu musely být menší nebo stejné jako kořen, tedy mohou ve finálním treapu skončit také vlevo. Dále si povšimněme, že všechny ostatní prvky (pravý podstrom levého treapu a pravý treap) jsou větší nebo stejné jako kořen, a tedy mohou být umístěné do pravého podstromu.

Levý podstrom nového kořene tedy již máme vytvořený a stačí ho přiřadit. Pravý ještě vytvořený není. Je potřeba ho vytvořit ze dvou částí: z pravého podstromu levého treapu a z pravého treapu. Povšimneme si, že toto ale je zase Merge dvou treapů. Tedy nám stačí zavolat náš algoritmus rekurzivně.

V případě, že alespoň jeden vstup je prázdný treap, tak stačí ten druhý vrátit jako výsledek. Nahlédneme, že se naše rekurze vždy zastaví, protože se vždy zavolá na alespoň o jedna menší součet velikostí treapů. Nově vzniklý kořen už do rekurze určitě nezasahuje.

Pojďme ale tento odhad vylepšit. Všimneme si, že každé volání rekurze vrátí kořen, který se ve výsledném treapu pověsí pod kořen předchozí rekurze.

Tedy i-tý vrácený kořen bude v hloubce i. To ale znamená, že počet volání rekurze nebude větší než hloubka výsledného stromu. O ní ale doufáme, že bude malá.

def merge(left, right):
    if left is None or right is None:
        return left if right is None else right

    if left.priority < right.priority:
        left.right = merge(left.right, right)
        return left
    else:
        right.left = merge(left, right.left)
        return right

Treap *merge(Treap *left, Treap *right)
{
	if (!left || !right) return left?left:right;
	if (left->priority < right->priority)
	{
		left->right = merge(left->right, right);
		return left;
	}
	else
	{
		right->left = merge(left, right->left);
		return right;
	}
}

Split. Opačnou operací k Merge je Split. Ten nám treap rozřeže na dva. Na vstupu mu dáme jeden treap a klíč x. Zpět dostaneme dva treapy. První z nich obsahuje pouze položky, jejíž klič je menší než x. Druhý obsahuje zbytek, tedy položky s klíčem ≥ x.

Uvědomíme si, že o každém vrcholu jednoznačně víme, jestli patří do levého, nebo do pravého podstromu. Stačí jeho klíč porovnat s x.

Pojďme tedy treap párat od kořene. Opět sledujme obrázek:

Dále uvažme, že kořen patří do levého výsledku. V opačném případě provedeme totéž, jen s prohozením stran. Kořen tedy bude kořenem levého výsledku. Všimneme si, že jeho levý podstrom už dále nebudeme muset řešit.

Je potřeba tedy jen rozdělit jeho pravý podstrom. Část má zůstat jeho pravý podstrom (a tedy v levém výsledku). Zbytek pak bude pravým výsledkem.

Tedy chceme znovu rozdělit menší treap na dva podle x. To ale zvládneme rekurzivním zavoláním operace Split.

V případě, že vstup je prázdný treap, tak oba výstupy jsou také prázdné treapy. Nahlédneme, že počet operací je nejvýše hloubka vstupního treapu, protože při každém zavolání rekurze se dostaneme o jedno patro níže.

def split(parent, key):
    if parent is None:
        return (None, None)

    if parent.key < key:
        left = parent
        left.right, right = split(parent.right, key)
    else:
        right = parent
        left, right.left = split(parent.left, key)

    return (left, right)

pair<Treap*, Treap*> split(Treap *in, int key)
{
	Treap *left=in,*right=in;
	if (!in) return {NULL, NULL};
	if (in->key <  key)
		tie(left->right, right) =
				split(in->right, key);
	else
		tie(left, right->left) =
				split(in->left, key);
	return {left, right};
}

Treap jako vyhledávací strom

Insert. Pomocí spojování a slévání si postavíme již trošku zajímavější operace. Insert správně zatřídí jeden prvek do treapu.

Treap nejprve splitneme na dva podle klíče vkládaného prvku (označme po řadě A a B). Založíme nový prvek s náhodnou prioritou. Pak už jen stačí postupně spojovat. Nejprve spojíme A a nový prvek. Pak ho ještě spojíme s B.

Všimneme si, že při každém spojování skutečně platí nutná podmínka o pořadí klíčů.

Find. Hledat již umíme. V ruce máme vždy vyhledávací strom. Pojďme na to ale používat jen předchozí operace.

Označme hledaný klíč x. Stačí rozdělit treap před požadovaným klíčem a pak pravou část ještě po něm. Tedy provést Split na klič x. Na pravý výsledek pak ještě provedeme další Split. Tentokrát ale do levého výsledku pošleme všechny hodnoty ≥ x. Evidentně není problém vytvořit Split s neostrou nerovností. Pro celá čísla nám ale jen stačí udělat Split s hodnotou x+1.

Tím dostaneme tři treapy. Prostřední z nich obsahuje prvek s hledaným klíčem (v případě, že existuje). Ovšem nesmíme zapomenout na to, že pak zase tyto tři treapy musíme spojit, protože Split původní treap zničí.

Delete. Odstranění prvku s nějakým klíčem je jen mírnou modifikací předešlého algoritmu. Prostě poté, co daný prvek najdeme, tak je zahodíme a spojíme jen zbylé dvě části.

Lower bound. Dále ukážeme, jak najít prvek, který má nejmenší klíč větší než nějaké zadané číslo x.

Treap rozdělíme podle x. Pak už víme, že požadovaný vrchol musí být nejmenší z pravé části. Ten ale umíme snadno najít. Stačí jít od kořene pořád vlevo, dokud má vrchol levého potomka. Ani zde pak nesmíme zapomenout na finální slepení pracovních částí.

Případně můžeme s treapem pracovat pouze jako s vyhledávacím stromem. Lower bound lze provést průchodem od kořene jako při hledání. Poslední prvek, na který narazíme a má klíč ≥ x, je totiž požadovaným výsledkem.

Rozšíření o počítání prvků

Hlavní výhoda treapu od již implementovaných algoritmů ve většině programovacích jazyků je, že treap můžeme snadno implementovat a dále upravovat k obrazu svému. Díky tomu z něho můžeme vytvořit mnohem zajímavější datovou strukturu.

Pojďme u každého vrcholu počítat velikost podstromu pod ním. Uvědomíme si, u kterých vrcholů se tyto hodnoty mění při základních operacích Split a Merge. Ostatní vybudované operace vlastně jen využívají těchto, takže je nemusíme uvažovat zvlášť. Dále ještě vytváříme samostatné vrcholy, ale to také není žádná komplikace.

U Splitu stačí přepočítat počet vrcholů u vytvořených výsledků. Všimneme si, že modifikace v podstromech se dělají jen pomocí rekurze, a tedy se také počty správně opraví před tím, než budeme počítat aktuální velikost.

U operace Merge je situace podobná. Stačí jen přepočítat hodnotu u vraceného výsledku.

Přepočítání je jednoduché, stačí sečíst počet vrcholů v podstromech (jestli existují) a k tomu přičíst jedničku za aktuální vrchol.

Všimněte si, že takto vždy budeme mít v každém vrcholu spočtenou velikost podstromu, ale i tak složitost všech operací asymptoticky nevzroste.

K čemu je počítání velikostí podstromu ale dobré?

Když najdeme nějaký vrchol, můžeme se podívat, o kolikátý vrchol v původním treapu se jedná (když si je představíme seřazené podle klíčů). Stačí spočítat počet vrcholů v před aktuálním vrcholem (tedy s menším klíčem). Jedná se o velikost treapu, který vznikne před aktuálním prvkem v při destruktivním Splitu

Můžeme také najít n-tý nejmenší prvek v treapu. Ukážeme, jak provést Split, aby v levém výsledku skončilo n vrcholů. Budeme počítat, kolik ještě vrcholů chceme umístit do levého výsledného stromu. Jelikož se bude jednat o parametr rekurze, dále budeme značit také jako x. Mírně modifikujeme naši funkci Split. Nahradíme část, kde vybíráme, jestli aktuální vrchol půjde do levého či do pravého výsledku.

V případě, že počet vrcholů v levém podstromu a v kořeni je menší nebo stejný než n, tak kořen (a tedy nutně i celý levý podstrom) půjde doleva. Z pravého podstromu pak ještě rekurzivně vybereme zbývající počet potřebných vrcholů.

Když nalevo od aktuálního vrcholu je alespoň požadovaný počet vrcholů, tak aktuální vrchol umístíme do pravého výsledku. Do levého pak rekurzivně vybereme n vrcholů z levého podstromu.

Jelikož jsme vlastně nezměnili nic jiného než způsob výběru větve programu, časová složitost a jiné charakteristiky algoritmu se nezmění.

V případě, že chceme pouze najít n-tý prvek (a ne treap kolem něho rozdělit), můžeme použít i nedestruktivního postupu. Prostě jen půjdeme od kořene a stejným způsobem budeme počítat počet vrcholů, které ještě chceme přeskočit. Když bude počet vrcholů k přeskočení menší než velikost levého podstromu, tak půjdeme do levého podstromu. Když budou stejné, tak se jedná o aktuální vrchol. Ve zbývajících případech půjdeme do pravého podstromu. Od počtu vrcholů k přeskočení ovšem budeme muset odečíst velikost levého podstromu aktuálního vrcholu.

Pojďme se podívat na implementaci.

class Node:
    left = None
    right = None

    def __init__(self, priority, key):
        self.priority = priority
        self.key = key
        self.size = 1

def update(node):
    if node is None:
        return

    node.size = 1
    if node.left is not None:
        node.size += node.left.size
    if node.right is not None:
        node.size += node.right.size

def merge(left, right):
    if left is None or right is None:
        return left if right is None else right

    if left.priority < right.priority:
        left.right = merge(left.right, right)
        update(left)
        return left
    else:
        right.left = merge(left, right.left)
        update(right)
        return right

def split(parent, key):
    if parent is None:
        return (None, None)

    if parent.key < key:
        left = parent
        left.right, right = split(parent.right, key)
    else:
        right = parent
        left, right.left = split(parent.left, key)

    update(left)
    update(right)
    return (left, right)

def split_by_count(parent, n):
    if parent is None:
        return (None, None)

    left_count = 1 + (0 if parent.left is None else parent.left.size)

    if left_count <= n:
        left = parent
        left.right, right = split_by_count(parent.right, n - left_count)
    else:
        right = parent
        left, right.left = split_by_count(parent.left, n)

    update(left)
    update(right)
    return (left, right)

struct Treap
{
	Treap *left=NULL, *right=NULL;
	int key;
	int priority;
	int size=1;
};

void update(Treap *in)
{
	if (!in) return;
	in->size = 1;
	if (in->left) in->size += in->left->size;
	if (in->right) in->size += in->right->size;
}

Treap *merge(Treap *left, Treap *right)
{
	if (!left || !right) return left?left:right;
	if (left->priority < right->priority)
	{
		left->right = merge(left->right, right);
		update(left);
		return left;
	}
	else
	{
		right->left = merge(left, right->left);
		update(right);
		return right;
	}
}

pair<Treap*, Treap*> split(Treap *in, int key)
{
	Treap *left=in, *right=in;
	if (!in) return {NULL, NULL};
	if (in->key < key)
		tie(left->right, right) = split(in->right, key);
	else
		tie(left, right->left) = split(in->left, key);
	update(left);
	update(right);
	return {left, right};
}

pair<Treap *, Treap *> split_by_count
		(Treap *in, int n)
{
	Treap *left=in, *right=in;
	int left_count = 1 +
			(in->left ? in->left->size : 0);
	if (!in) return {NULL, NULL};
	if (left_count <= n)
		tie(left->right, right) = split_by_count(in->right, n-left_count);
	else
		tie(left, right->left) = split_by_count(in->left, n);
	update(left);
	update(right);
	return {left, right};
}

Reprezentace posloupností

Pojďme udělat pokus. Odstraníme z vrcholů klíče, podle kterých byl treap setříděn. Sice teď v treapu nemůžeme hledat, ale pořád s ním jdou dělat zajímavé věci.

Všimneme si, že Merge je vlastně vůbec nevyužíval. Jen prostě dostane dva treapy a „nalepí“ je za sebe. Split je sice využíval, ale místo něho jsme před chvílí vytvořili Split za n-tým prvkem, který klíče také nepotřebuje.

Máme tedy „bezejmenné“ vrcholy, ovšem stále s dobře definovaným pořadím. Nyní do každého vrcholu připíšeme nějakou hodnotu. Podle té ovšem není treap setříděn – nemusí to být číslo, dokonce ani něco, co se dá porovnávat.

Všimněte si, že jsme dostali reprezentaci posloupnosti. Můžeme se totiž ptát na n-tý prvek a případně ho změnit. Navíc umíme za nebo před libovolný prvek přidat další a také posloupnosti rozdělovat a spojovat.

Každá z těchto operací nám trvá průměrně O(log N) času, kde N je počet prvků posloupnosti.

Mimochodem, původní případ, kdy jsme měli hodnoty setříděně, byl obdobou binárního vyhledávání na této posloupnosti.

Intervalový strom

V předchozí části jsme vybudovali posloupnost. Pojďme na ní postavit nějaké zajímavé operace.

Pokusíme se rychle odpovídat na dotazy, jaký je součet na určitém úseku posloupnosti. Dokonce se nemusí jednat jen o součet. Stačí nám jakákoliv asociativní operace. To je taková, kde nezáleží na uzávorkování. Například může jít o maximum, součin modulo prvočíslo a podobně, nebo dokonce v případě, že hodnota je maticí, tak se může jednat o součin matic. Pro jednodušší představu ale dále budeme mluvit o součtu.

V klasickém poli by se tento problém řešil pomocí intervalového stromu.

Využijeme obdobného postupu jako u počítání velikostí podstromu. V každém vrcholu si budeme pamatovat součet.

Budeme součty přepočítávat vždy ve stejné momenty jako velikosti podstromu. Tedy ze stejného důvodu budou vždy aktuální a jednotlivé operace se asymptoticky nezpomalí.

Na součet se pak zeptáme opravdu jednoduše. Treap rozřízneme na tři části: před požadovaným intervalem, požadovaný interval a část za ním. Pak už se jen jednoduše zeptáme na součet prostřední části.

Líný intervalový strom. Dále se naučíme jednotlivé úseky rychle měnit. Problematiku si ukážeme pouze na konkrétním příkladu. Ke každému prvku úseku se pokusíme přičíst zadané číslo.

V každém vrcholu si budeme pamatovat, kolik se má do každého vrcholu v jeho podstromu ještě přičíst (označme aktualizace). Vždy předtím, než s daným vrcholem budeme něco dělat, tuto hodnotu propagujeme do podstromu. To znamená, že ji přičteme k hodnotě aktuálního vrcholu a k hodnotám aktualizace synů.

Jelikož všechny operace provádíme od kořene, celá cesta mezi kořenem a aktuálním vrcholem bude propagovaná. Hodnota aktuálního vrcholu tedy bude správná.

Přičtení k úseku je pak jednoduché. Treap rozdělíme zase na tři části a k aktualizaci prostředního treapu přičteme danou hodnotu. Nakonec vše zase poslepujeme k sobě.

Hodnoty se sice hned nezmění ve všech vrcholech, ale máme zaručeno, že až s nimi budeme pracovat, tak už bude aktuální.

Problém ovšem nastává, když chceme toto rozšíření aplikovat spolu s dotazy na součet (nebo jinou operaci) intervalů. Při propagování aktualizací totiž budeme muset upravovat i tyto součty. Na toto bohužel neexistuje žádná obecná poučka. Vždy je potřeba se zamyslet, jak spolu interagují obě dvě funkce. Když třeba přičítáme x ke každému vrcholu, je nutné zvýšit součet podstromu o nx, kde n je počet vrcholů v podstromu. Maximum bychom ale zvýšili pouze o x.

Příklad použití treapů

Na závěr si ukážeme jednu úlohu, na kterou se treapy hodí (je to úloha P-II-1 z 69. ročníku MO kategorie P).

Zadání: Na polici je vyznačeno n pozic a na každé z nich leží jedno jablíčko. Pozice jsou očíslovány zleva doprava čísly od 0 do n - 1. Jablíčko na pozici i má velikost a_i. Všechna jablíčka mají navzájem různé velikosti. Chceme všechna jablíčka uspořádat podle velikosti od nejmenšího po největší. Kvůli přísným hygienickým předpisům je však nesmíme přemisťovat sami, musíme na to použít techniku. V místnosti s jablíčky máme mechanické rameno. Pomocí něho můžeme sebrat jablíčka z libovolného souvislého úseku police a vrátit je zpátky na polici na jejich původní místa, ale v opačném pořadí. Tuto operaci nazveme reverze. Každá reverze trvá stejně dlouho bez ohledu na to, jak dlouhý úsek obracíme.

Řešení pomocí treapu: Pokusíme se postupně výsledek stavět od začátku. Začneme umísťovat jablíčka od nejmenších velikostí. Tím začne vznikat prefix výsledku, do kterého pak již nebudeme zasahovat.

Je tedy vždy potřeba najít nejmenší zatím neumístěné jablko. Pak provedeme reverzi úseku od pozice, kam ho chceme dostat, po pozici, kde je. Tím se evidentně dostane na příslušnou pozici a nenaruší se ani prefix již dobře umístěných jablíček.

Jak ale udržovat aktuální pozice jablíček a hledat nejmenší na nějakém úseku? Využijeme treap.

Přidáme línou operaci proveď reverzi na podstromu. Tu budeme vyhodnocovat jednoduše. Stačí prohodit levého a pravého potomka a u obou z nich pak také provézt reverzi. To se ale zase udělá líným vyhodnocením. Ještě si všimneme, že udělat reverzi dvakrát je jako ji neudělat vůbec.

Také budeme počítat minimum v každém podstromu. Všimneme si, že reverze ho nijak neovlivní, a tedy vzájemnou interakci reverzí a minim nemusíme nijak řešit.

Najít nejmenší prvek v úseku je pak jednoduché. Nejprve úsek ořízneme do jednoho treapu. Pak už víme, jakou má mít nejmenší prvek hodnotu. U každého vrcholu zvládneme určit, jestli se jedná o aktuální prvek, nebo hledané minimum leží v levém či pravém podstromu. Podstrom, ve kterém leží hledaný prvek, totiž musí mít příslušné minimum. Můžeme ho tedy vytvořit například funkci Split za nejmenším prvkem.

Další podobné struktury

Na závěr dodejme, že princip budování operací ze Split a Merge a ostatní triky z této kuchařky nejsou nijak specifické pro treapy. Dají se provozovat i s jinými stromovitými strukturami. Například se Splay stromy – ty jsou sice pracnější, ale zaručují složitost O(log n) amortizovaně. A pokud této složitosti chceme dosáhnout i v nejhorším případě, jde použít (a,b)-strom nebo červeno-černý strom, ale tam už jsou algoritmy pro Split a Merge značně komplikované.

Jiří Kalvoda & Martin Mareš