Treap (Cartesiaanse boom)

Specifieker is een treap een datastructuur die paren $(X, Y)$ in een binaire boom opslaat, zodanig dat het een binaire zoekboom is op basis van $X$ en een binaire heap op basis van $Y$.

Als een knoop van de boom de waarden $(X0, Y0)$ bevat, dan hebben alle knopen in de linker subboom $X \leq X0$, alle knopen in de rechter subboom $X0 \leq X$, en alle knopen in zowel de linker als de rechter subboom $Y \leq Y_0$.

Een treap wordt ook vaak aangeduid als een "Cartesiaanse boom", omdat het eenvoudig in een Cartesiaans vlak kan worden ingebed. Treaps zijn in 1989 voorgesteld door Raimund Siedel en Cecilia Aragon.

Voordelen van deze datastructuur

In deze implementatie zijn de $X$-waarden de sleutels (en tegelijkertijd de waarden die in de treap worden opgeslagen), en de $Y$-waarden worden prioriteiten genoemd. Zonder prioriteiten zou de treap een reguliere binaire zoekboom op $X$ zijn. Eén set $X$-waarden zou dan kunnen corresponderen met veel verschillende bomen, waarvan sommige gedegenereerd zijn (bijvoorbeeld in de vorm van een gekoppelde lijst), waardoor de operaties extreem traag worden (de belangrijkste operaties zouden een complexiteit van $O(N)$ hebben).

Tegelijkertijd maken prioriteiten (wanneer deze uniek zijn) het mogelijk om de boom die wordt geconstrueerd eenduidig te specificeren (dit is onafhankelijk van de volgorde waarin waarden worden toegevoegd), wat bewezen kan worden met een overeenkomstige stelling. Als de prioriteiten willekeurig worden gekozen, verkrijgt men gemiddeld niet-gedegenereerde bomen, wat een complexiteit van $O(\log N)$ garandeert voor de belangrijkste operaties. Daarom is een andere naam voor deze datastructuur de "gerandomiseerde binaire zoekboom".

Operaties

Een treap biedt de volgende operaties:

• Insert (X,Y) in $O(\log N)$: Voegt een nieuwe knoop toe aan de boom. Een mogelijke variant is om alleen $X$ mee te geven en $Y$ willekeurig te genereren binnen de operatie.
• Search (X) in $O(\log N)$: Zoekt naar een knoop met de opgegeven sleutelwaarde $X$. De implementatie is hetzelfde als voor een gewone binaire zoekboom.
• Erase (X) in $O(\log N)$: Zoekt naar een knoop met de opgegeven sleutelwaarde $X$ en verwijdert deze uit de boom.
• Build ($X1$, ..., $XN$) in $O(N)$: Bouwt een boom vanuit een lijst met waarden. Dit kan in lineaire tijd gebeuren (ervan uitgaande dat $X1, ..., XN$ gesorteerd zijn).
• Union ($T1$, $T2$) in $O(M \log (N/M))$: Voegt twee bomen samen, ervan uitgaande dat alle elementen verschillend zijn. Dezelfde complexiteit is haalbaar als dubbele elementen tijdens het samenvoegen moeten worden verwijderd.
• Intersect ($T1$, $T2$) in $O(M \log (N/M))$: Vindt de doorsnede van twee bomen (d.w.z. hun gemeenschappelijke elementen). De implementatie van deze operatie wordt hier niet behandeld.

Daarnaast kan een treap, omdat het een binaire zoekboom is, andere operaties implementeren, zoals het vinden van het $K$-de grootste element of het vinden van de index van een element.

Implementatiebeschrijving

Wat betreft de implementatie bevat elke knoop $X$, $Y$ en pointers naar de linker ($L$) en rechter ($R$) kinderen. Alle vereiste operaties worden geïmplementeerd met behulp van slechts twee hulpoperaties: Split en Merge.

Split

Split (T, X) scheidt boom $T$ in twee subbomen $L$ en $R$ (de retourwaarden van split), zodanig dat $L$ alle elementen bevat met sleutel $XL \le X$, en $R$ alle elementen bevat met sleutel $XR > X$. Deze operatie heeft een complexiteit van $O(\log N)$ en wordt geïmplementeerd via een schone recursie:

1. Als de waarde van de wortelknoop (R) $\le X$ is, dan bestaat $L$ ten minste uit R->L en R. We roepen vervolgens split op R->R, en noteren het resultaat als L' en R'. Uiteindelijk bevat $L$ ook L', terwijl $R = R'$.
2. Als de waarde van de wortelknoop (R) $> X$ is, dan bestaat $R$ ten minste uit R en R->R. We roepen vervolgens split op R->L, en noteren het resultaat als L' en R'. Uiteindelijk is $L = L'$, terwijl $R$ ook R' bevat.

Het split-algoritme is dus:

• Bepaal bij welke subboom de wortelknoop zou horen (links of rechts).
• Roep recursief split op een van de kinderen.
• Creëer het uiteindelijke resultaat door de recursieve split-aanroep te hergebruiken.

Merge

Merge (T1, T2) combineert twee subbomen $T1$ en $T2$ en geeft de nieuwe boom terug. Deze operatie heeft ook een complexiteit van $O(\log N)$. Er wordt vanuit gegaan dat $T1$ and $T2$ geordend zijn (alle sleutels $X$ in $T1$ zijn kleiner dan de sleutels in $T2$). We moeten deze bomen combineren zonder de volgorde van prioriteiten $Y$ te schenden. Hiervoor kiezen we de boom met de hoogste prioriteit $Y$ in de wortelknoop als de nieuwe wortel, en roepen we recursief Merge aan voor de andere boom en de overeenkomstige subboom van de geselecteerde wortelknoop.

Insert

De implementatie van Insert (X, Y) wordt nu duidelijk. Eerst dalen we af in de boom (zoals in een reguliere binaire zoekboom op $X$) en stoppen we bij de eerste knoop waarin de prioriteitswaarde kleiner is dan $Y$. We hebben de plek gevonden waar we het nieuwe element invoegen. Vervolgens roepen we Split (T, X) aan op de subboom die begint bij de gevonden knoop, en gebruiken we de geretourneerde subbomen $L$ and $R$ als linker- en rechterkinderen van de nieuwe knoop.

Als alternatief kan insert worden gedaan door de initiële treap te splitsen op $X$ en twee merges uit te voeren met de nieuwe knoop.

Erase

De implementatie van Erase (X) is ook helder. Eerst dalen we af in de boom (zoals in een reguliere binaire zoekboom op $X$) op zoek naar het element dat we willen verwijderen. Zodra de knoop is gevonden, roepen we Merge aan op de kinderen en plaatsen we de retourwaarde van de operatie op de plek van het element dat we verwijderen.

Als alternatief kunnen we de subboom die $X$ bevat isoleren met twee split-operaties en de resterende treaps samenvoegen.

Build

We implementeren de Build-operatie met een complexiteit van $O(N \log N)$ door $N$ Insert-aanroepen te doen.

Union

Union (T1, T2) heeft een theoretische complexiteit van $O(M \log (N/M))$, maar in de praktijk werkt het zeer goed. Stel zonder verlies van algemeenheid dat $T1 \rightarrow Y > T2 \rightarrow Y$, wat betekent dat de wortel van $T1$ de wortel van het resultaat zal zijn. Om het resultaat te krijgen, moeten we de bomen $T1 \rightarrow L$, $T1 \rightarrow R$ and $T2$ samenvoegen in twee bomen die kinderen van de $T1$-wortel kunnen zijn. Hiervoor roepen we Split (T2, T1->X) aan, waardoor $T2$ wordt gesplitst in twee delen $L$ en $R$, die we vervolgens recursief combineren met de kinderen van $T_1$: Union (T1 -> L, L) and Union (T1 -> R, R), om zo de linker- en rechtersubbomen van het resultaat te verkrijgen.

Implementatie

struct item {
    int key, prior;
    item *l, *r;
    item () { }
    item (int key) : key(key), prior(rand()), l(NULL), r(NULL) { }
    item (int key, int prior) : key(key), prior(prior), l(NULL), r(NULL) { }
};
typedef item* pitem;

Dit is onze definitie van een item. Let op de twee kinder-pointers, een integer sleutel (voor de BST) en een integer prioriteit (voor de heap). De prioriteit wordt toegewezen met een willekeurige getallengenerator.

void split (pitem t, int key, pitem & l, pitem & r) {
    if (!t)
        l = r = NULL;
    else if (t->key <= key)
        split (t->r, key, t->r, r),  l = t;
    else
        split (t->l, key, l, t->l),  r = t;
}

t is de treap die gesplitst moet worden, en key is de BST-waarde waarop gesplitst wordt. Let op dat we de resultaatwaarden nergens teruggeven; in plaats daarvan worden de output-treaps geschreven via l en r, bijvoorbeeld:

pitem l = nullptr, r = nullptr;
split(t, 5, l, r);

Deze split-functie kan lastig te begrijpen zijn, omdat deze zowel pointers (pitem) als referenties naar die pointers (pitem &l) bevat. Laten we in woorden begrijpen wat de functieaanroep split(t, k, l, r) beoogt: "splits treap $t$ op waarde $k$ in twee treaps, en bewaar de linker treap in $l$ en de rechter treap in $r$".

Wanneer de waarde van de wortelknoop $\le$ key is, roepen we split (t->r, key, t->r, r) aan, wat betekent: "splits treap t->r (rechter subboom van $t$) op waarde key en bewaar de linker subboom in t->r en de rechter subboom in r". Daarna stellen we l = t. Let nu op dat de l resultaatwaarde t->l, t alsmede t->r (het resultaat van de recursieve aanroep) bevat, allemaal al in de juiste volgorde samengevoegd!

Wanneer de waarde van de wortelknoop groter is dan key, roepen we split (t->l, key, l, t->l) aan, wat betekent: "splits treap t->l (linker subboom van $t$) op waarde key en bewaar de linker subboom in l en de rechter subboom in t->l". Daarna stellen we r = t. Let nu op dat de r resultaatwaarde t->l (het resultaat van de recursieve aanroep), t alsmede t->r bevat, allemaal al in de juiste volgorde samengevoegd!

Als je nog steeds moeite hebt om de implementatie te begrijpen, kun je deze inductief bekijken: probeer de recursieve aanroepen niet telkens opnieuw te ontleden. Neem aan dat de split-implementatie correct werkt op een lege treap, probeer hem dan uit voor een treap met één knoop, dan een treap met twee knopen, enzovoort.

void insert (pitem & t, pitem it) {
    if (!t)
        t = it;
    else if (it->prior > t->prior)
        split (t, it->key, it->l, it->r),  t = it;
    else
        insert (t->key <= it->key ? t->r : t->l, it);
}

void merge (pitem & t, pitem l, pitem r) {
    if (!l || !r)
        t = l ? l : r;
    else if (l->prior > r->prior)
        merge (l->r, l->r, r),  t = l;
    else
        merge (r->l, l, r->l),  t = r;
}

void erase (pitem & t, int key) {
    if (t->key == key) {
        pitem th = t;
        merge (t, t->l, t->r);
        delete th;
    }
    else
        erase (key < t->key ? t->l : t->r, key);
}

pitem unite (pitem l, pitem r) {
    if (!l || !r)  return l ? l : r;
    if (l->prior < r->prior)  swap (l, r);
    pitem lt, rt;
    split (r, l->key, lt, rt);
    l->l = unite (l->l, lt);
    l->r = unite (l->r, rt);
    return l;
}

Onderhoud van subboomgroottes

Om de functionaliteit van de treap uit te breiden, is het vaak nodig om het aantal knopen in de subboom van elke knoop op te slaan — het veld int cnt in de item-structuur. Bijvoorbeeld, dit kan worden gebruikt om het $K$-de grootste element van de boom te vinden in $O(\log N)$, of om de index van het element in de gesorteerde lijst te vinden met dezelfde complexiteit. De implementatie van deze operaties zal hetzelfde zijn als voor de reguliere binaire zoekboom.

Wanneer een boom verandert (knopen worden toegevoegd of verwijderd, etc.), moet cnt van sommige knopen dienovereenkomstig worden bijgewerkt. We maken twee functies: cnt() geeft de huidige waarde van cnt terug of 0 als de knoop niet bestaat, en updcnt() werkt de waarde van cnt voor deze knoop bij, ervan uitgaande dat voor de kinderen $L$ and $R$ de waarden van cnt al zijn bijgewerkt. Het is voldoende om aanroepen van updcnt() aan het einde van insert, erase, split and merge toe te voegen om de cnt-waarden up-to-date te houden.

int cnt (pitem t) {
    return t ? t->cnt : 0;
}

void upd_cnt (pitem t) {
    if (t)
        t->cnt = 1 + cnt(t->l) + cnt (t->r);
}

Een Treap bouwen in $O(N)$ in offline modus

Gegeven een gesorteerde lijst met sleutels is het mogelijk om een treap sneller te construeren dan door de sleutels één voor één in te voegen, wat $O(N \log N)$ kost. Omdat de sleutels gesorteerd zijn, kan een gebalanceerde binaire zoekboom eenvoudig in lineaire tijd worden geconstrueerd. De heap-waarden $Y$ worden willekeurig geïnitialiseerd en kunnen vervolgens onafhankelijk van de sleutels $X$ worden "ge-heapified" om de heap in $O(N)$ te bouwen.

void heapify (pitem t) {
    if (!t) return;
    pitem max = t;
    if (t->l != NULL && t->l->prior > max->prior)
        max = t->l;
    if (t->r != NULL && t->r->prior > max->prior)
        max = t->r;
    if (max != t) {
        swap (t->prior, max->prior);
        heapify (max);
    }
}

pitem build (int * a, int n) {
    // Constructeer een treap op waarden {a[0], a[1], ..., a[n - 1]}
    if (n == 0) return NULL;
    int mid = n / 2;
    pitem t = new item (a[mid], rand ());
    t->l = build (a, mid);
    t->r = build (a + mid + 1, n - mid - 1);
    heapify (t);
    upd_cnt(t);
    return t;
}

Opmerking: het aanroepen van upd_cnt(t) is alleen nodig als je de subboomgroottes nodig hebt.

De bovenstaande aanpak levert altijd een perfect gebalanceerde boom op, wat over het algemeen goed is voor praktische doeleinden, maar ten koste gaat van het behoud van de prioriteiten die oorspronkelijk aan elke knoop waren toegewezen. Daarom is deze aanpak niet haalbaar om het volgende probleem op te lossen:

acmsguru - Cartesian Tree Gegeven een sequentie van paren $(xi, yi)$, construeer een Cartesiaanse boom op deze paren. Alle $xi$ en alle $yi$ zijn uniek.

Let op dat in dit probleem prioriteiten niet willekeurig zijn, waardoor het één voor één invoegen van vertices een kwadratische oplossing kan opleveren. Een van de mogelijke oplossingen is om voor elk element de dichtstbijzijnde elementen links en rechts te vinden die een kleinere prioriteit hebben dan dit element. Van deze twee elementen moet degene met de grootste prioriteit de ouder van het huidige element zijn.

Dit probleem is in lineaire tijd oplosbaar met een minimale stack-modificatie. De onderstaande constructie gebruikt de min-heap conventie voor prioriteiten (in tegenstelling tot de max-heap conventie van de reguliere treap-implementatie hierboven) en gaat ervan uit dat item is uitgebreid met een parent-pointer p geïnitialiseerd op nullptr:

void connect(auto from, auto to) {
    vector<pitem> st;
    for(auto it: ranges::subrange(from, to)) {
        while(!st.empty() && st.back()->prior > it->prior) {
            st.pop_back();
        }
        if(!st.empty()) {
            if(!it->p || it->p->prior < st.back()->prior) {
                it->p = st.back();
            }
        }
        st.push_back(it);
    }
}

pitem build(int *x, int *y, int n) {
    vector<pitem> nodes(n);
    for(int i = 0; i < n; i++) {
        nodes[i] = new item(x[i], y[i]);
    }
    connect(nodes.begin(), nodes.end());
    connect(nodes.rbegin(), nodes.rend());
    for(int i = 0; i < n; i++) {
        if(nodes[i]->p) {
            if(nodes[i]->p->key < nodes[i]->key) {
                nodes[i]->p->r = nodes[i];
            } else {
                nodes[i]->p->l = nodes[i];
            }
        }
    }
    return nodes[min_element(y, y + n) - y];
}

Impliciete Treaps

Een impliciete treap is een eenvoudige modificatie van de reguliere treap en is een zeer krachtige datastructuur. In feite kan een impliciete treap worden beschouwd als een array met de volgende procedures (allemaal in $O(\log N)$ in de online modus):

• Het invoegen van een element in de array op elke gewenste locatie.
• Het verwijderen van een willekeurig element.
• Het vinden van de som, het minimum / maximum element, etc. over een willekeurig interval.
• Optelling of het inkleuren (painting) over een willekeurig interval.
• Het omkeren (reversing) van elementen over een willekeurig interval.

Het idee is dat de sleutels de null-based indices van de elementen in de array zouden moeten zijn. We slaan deze waarden echter niet expliciet op (anders zou bijvoorbeeld het invoegen van een element wijzigingen in de sleutel veroorzaken in $O(N)$ knopen van de boom).

Let op dat de sleutel van een knoop het aantal knopen is dat kleiner is dan deze (zo'n knopen kunnen niet alleen in de linker subboom aanwezig zijn, maar ook in de linker subbomen van de voorouders). Specifieker is de impliciete sleutel voor een knoop $T$ het aantal vertices cnt(T -> L) in de linker subboom van deze knoop plus soortgelijke waarden cnt(P -> L) + 1 voor elke voorouder $P$ van de knoop $T$, indien $T$ zich in de rechter subboom van $P$ bevindt.

Het is nu duidelijk hoe de impliciete sleutel van de huidige knoop snel berekend kan worden. Omdat we bij alle operaties bij elke knoop komen door in de boom af te dalen, kunnen we deze som gewoon accumuleren en aan de functie doorgeven. Als we naar de linker subboom gaan, verandert de geaccumuleerde som niet; als we naar de rechter subboom gaan, neemt deze toe met cnt(T -> L) + 1.

Hier zijn de nieuwe implementaties van Split and Merge:

void merge (pitem & t, pitem l, pitem r) {
    if (!l || !r)
        t = l ? l : r;
    else if (l->prior > r->prior)
        merge (l->r, l->r, r),  t = l;
    else
        merge (r->l, l, r->l),  t = r;
    upd_cnt (t);
}

void split (pitem t, pitem & l, pitem & r, int key, int add = 0) {
    if (!t)
        return void( l = r = 0 );
    int cur_key = add + cnt(t->l); //impliciete sleutel
    if (key <= cur_key)
        split (t->l, l, t->l, key, add),  r = t;
    else
        split (t->r, t->r, r, key, add + 1 + cnt(t->l)),  l = t;
    upd_cnt (t);
}

In de bovenstaande implementatie zal, na de aanroep van split(T, T1, T2, k), de boom $T1$ bestaan uit de eerste $k$ elementen van $T$ (elementen met een impliciete sleutel kleiner dan $k$) en $T2$ uit de rest.

Overweg nu de implementatie van diverse operaties op impliciete treaps:

• Element invoegen: Stel we willen een element invoegen op positie pos. We verdelen de treap in twee delen, die corresponderen met arrays $[0..pos-1]$ and $[pos..sz]$; we roepen split(T, T1, T2, pos) aan. Vervolgens combineren we boom $T1$ met de nieuwe vertex via merge(T1, T1, new item). Ten slotte voegen we $T1$ and $T_2$ weer samen tot $T$ via merge(T, T1, T2).
• Element verwijderen: Deze operatie is nog eenvoudiger: vind het te verwijderen element $T$, voer een merge uit van de kinderen $L$ and $R$, en vervang element $T$ door het resultaat van de merge.
• Som / minimum, etc. vinden over een interval:

1. Voeg een extra veld $F$ toe aan de item-structuur om de waarde van de doelfunctie voor de subboom van deze knoop op te slaan. Dit veld is eenvoudig te onderhouden, vergelijkbaar met de subboomgroottes.
2. Voor een query over interval $[A; B]$ roepen we split(T, T2, T3, B+1) aan, en vervolgens split(T2, T1, T2, A). Daarna bestaat $T2$ alleen uit de elementen in het interval $[A; B]$. Het antwoord staat in veld $F$ van de wortel van $T2$. Daarna moet de boom worden hersteld via merge(T, T1, T2) and merge(T, T, T3).

• Optelling / inkleuren over een interval: We handelen dit vergelijkbaar af, maar in plaats van veld $F$ slaan we een veld add op. Voor elke operatie moeten we deze waarde correct "pushen" (wijzigen van $T \rightarrow L \rightarrow add$ and $T \rightarrow R \rightarrow add$, en add opschonen in de parent-knoop).
• Omkeren over een interval: Ook dit is vergelijkbaar: we voegen een boolean flag rev toe en toggelen deze wanneer de subboom van de huidige knoop moet worden omgekeerd. "Pushen" betekent hier: de kinderen van deze knoop omwisselen en de flag voor hen toggelen.

Hier is een voorbeeldimplementatie van de impliciete treap met de reverse-functie over een interval.

typedef struct item * pitem;
struct item {
    int prior, value, cnt;
    bool rev;
    pitem l, r;
};

int cnt (pitem it) {
    return it ? it->cnt : 0;
}

void upd_cnt (pitem it) {
    if (it)
        it->cnt = cnt(it->l) + cnt(it->r) + 1;
}

void push (pitem it) {
    if (it && it->rev) {
        it->rev = false;
        swap (it->l, it->r);
        if (it->l)  it->l->rev ^= true;
        if (it->r)  it->r->rev ^= true;
    }
}

void merge (pitem & t, pitem l, pitem r) {
    push (l);
    push (r);
    if (!l || !r)
        t = l ? l : r;
    else if (l->prior > r->prior)
        merge (l->r, l->r, r),  t = l;
    else
        merge (r->l, l, r->l),  t = r;
    upd_cnt (t);
}

void split (pitem t, pitem & l, pitem & r, int key, int add = 0) {
    if (!t)
        return void( l = r = 0 );
    push (t);
    int cur_key = add + cnt(t->l);
    if (key <= cur_key)
        split (t->l, l, t->l, key, add),  r = t;
    else
        split (t->r, t->r, r, key, add + 1 + cnt(t->l)),  l = t;
    upd_cnt (t);
}

void reverse (pitem t, int l, int r) {
    pitem t1, t2, t3;
    split (t, t1, t2, l);
    split (t2, t2, t3, r-l+1);
    t2->rev ^= true;
    merge (t, t1, t2);
    merge (t, t, t3);
}

void output (pitem t) {
    if (!t)  return;
    push (t);
    output (t->l);
    printf ("%d ", t->value);
    output (t->r);
}

Literatuur

• Blelloch, Reid-Miller "Fast Set Operations Using Treaps"

Oefenopdrachten

• SPOJ - Ada and Aphids
• SPOJ - Ada and Harvest
• Codeforces - Radio Stations
• SPOJ - Ghost Town
• SPOJ - Arrangement Validity
• SPOJ - All in One
• Codeforces - Dog Show
• Codeforces - Yet Another Array Queries Problem
• SPOJ - Mean of Array
• SPOJ - TWIST
• SPOJ - KOILINE
• CodeChef - The Prestige
• Codeforces - T-Shirts
• Codeforces - Wizards and Roads
• Codeforces - Yaroslav and Points
• Codeforces - KiaKio and Energy Intervals