Treap-rakenne

Treap on puurakenne, jonka avulla voimme esittää taulukon niin, että voimme tehokkaasti jakaa taulukon kahdeksi taulukoksi sekä yhdistää kaksi taulukkoa taulukoksi. Molemmat operaatiot toimivat tehokkaasti ajassa O(log n).

Jokainen treapin solmu sisältää kaksi arvoa: alkion sisällön sekä satunnaisen painon. Solmun vasemman alipuun lapset ovat ennen solmua taulukossa, ja solmun oikean alipuun lapset ovat solmun jälkeen taulukossa. Lisäksi solmut on järjestetty niin, että kunkin solmun paino on pienempi tai yhtä suuri kuin solmun lapsen paino. Satunnaisten painojen ansiosta treapin korkeus on käytännössä vain O(log n).

Seuraavassa on esimerkkinä treap, joka vastaa taulukkoa [1,2,3,4,5,6,7,8]:

Treapissa on kaksi perusoperaatiota: split ja merge. Operaatio split jakaa taulukon kahteen osaan niin, että vasen osa sisältää k ensimmäistä alkiota. Esimerkiksi kun jaamme taulukon [1,2,3,4,5,6,7,8] osiksi [1,2,3,4] ja [5,6,7,8], tulos on seuraava:

Operaatio merge puolestaan yhdistää kaksi taulukkoa yhdeksi taulukoksi. Esimerkiksi voimme yhdistää äsken jakamamme taulukot toisinpäin niin, että saamme taulukon [5,6,7,8,1,2,3,4]:

Kuinka sitten toteuttaa treap? Seuraava koodi antaa hyvän pohjan, jossa on treapin luonti sekä operaatiot split ja merge. Koodi toteuttaa yllä olevan esimerkin.

#include <iostream>

using namespace std;

struct node {
    node *left, *right;
    int weight, size, value;
    node (int v) {
        left = right = NULL;
        weight = rand();
        size = 1;
        value = v;
    }
};

int size(node *treap) {
    if (treap == NULL) return 0;
    return treap->size;
}

void split(node *treap, node *&left, node *&right, int k) {
    if (treap == NULL) {
        left = right = NULL;
    } else {
        if (size(treap->left) < k) {
            split(treap->right, treap->right, right, k-size(treap->left)-1);
            left = treap;
        } else {
            split(treap->left, left, treap->left, k);
            right = treap;
        }
        treap->size = size(treap->left)+size(treap->right)+1;
    }
}

void merge(node *&treap, node *left, node *right) {
    if (left == NULL) treap = right;
    else if (right == NULL) treap = left;
    else {
        if (left->weight < right->weight) {
            merge(left->right, left->right, right);
            treap = left;
        } else {
            merge(right->left, left, right->left);
            treap = right;
        }
        treap->size = size(treap->left)+size(treap->right)+1;
    }
}

void print(node *treap) {
    if (treap == NULL) return;
    print(treap->left);
    cout << treap->value << " ";
    print(treap->right);
}

int main() {
    // luo treap taulukolle [1,2,3,4,5,6,7,8]
    node *treap = NULL;
    merge(treap,treap,new node(1));
    merge(treap,treap,new node(2));
    merge(treap,treap,new node(3));
    merge(treap,treap,new node(4));
    merge(treap,treap,new node(5));
    merge(treap,treap,new node(6));
    merge(treap,treap,new node(7));
    merge(treap,treap,new node(8));
    print(treap);
    cout << "\n";
    // jaa taulukko osiin [1,2,3,4] ja [5,6,7,8] ja
    // yhdistä ne uudestaan taulukoksi [5,6,7,8,1,2,3,4]
    node *left, *right;
    split(treap,left,right,4);
    merge(treap,right,left);
    print(treap);
    cout << "\n";
}