Treap

Treap é uma estrutura de dados que combina uma árvore binária(binary tree) e uma binary heap (tree + heap $\Rightarrow$ Treap).

Mais especificamente, treap é uma estrutura de dados que armazena pares (X, Y) em uma binary tree de forma que seja uma binary search tree por X e uma binary heap por Y. Assumindo que todos os X e Y sejam diferentes, podemos ver que, se algum nó da árvore contém valores ($X_0$, $Y_0$), todos os nós na subárvore esquerda terão $X < X_0$, todos os nós na subárvore direita terão $X > X_0$, e todos os nós nas subárvores esquerda e direita têm $Y < Y_0$.

Treaps foram propostas por Siedel e Aragon em 1989.

Vantagens dessa organização de dados

Nessa implementação os valores X são as chaves (e ao mesmo tempo os valores armazenados na treap), e os valores Y são chamados de prioridades. Sem as prioridades, a treap seria uma binary search tree normal por X, e um conjunto de valores X poderia corresponder a muitas árvores diferentes, algumas delas degeneradas (por exemplo, na forma de uma linked list), e, portanto, seria extremamente lento (as operações principais teriam complexidade $O(N)$).

Ao mesmo tempo, as prioridades permitem especificar exclusivamente a árvore que será construída (isso não depende da ordem em que os valores são adicionados), o que pode ser comprovado usando um teorema correspondente. Se você escolher as prioridades de maneira aleatória, você obterá árvores não degeneradas em média, o que garantirá a complexidade $O(\log N)$ para as operações principais. Daí surge outro nome para essa estrutura de dados - randomized binary search tree.

Operações

Uma treap fornece as seguintes operações:

Além disso, devido ao fato de uma treap ser uma binary search tree, é possível implementar outras operações, como encontrar o K-ésimo maior elemento ou localizar o índice de um elemento.

Descrição

Em termos de implementação, cada nó contém X, Y e ponteiros para os nós filhos da esquerda (L) e direita (R).

Implementaremos todas as operações necessárias usando apenas duas operações auxiliares: Split e Merge.

Split (T, X) separa a árvore T em 2 subárvores L e R (no qual são os valores de retorno de split) assim, L contém todos os elementos com chave $X_L < X$, e R contém todos os elementos com chave $X_R > X$. Essa operação tem complexidade $O (\log N)$ e é implementada usando uma recursão.

Merge ($T_1$, $T_2$) combina duas subárvores $T_1$ e $T_2$ e retorna a nova árvore. Essa operação também possui complexidade $O (\log N)$. Ela funciona sob a suposição de que $T_1$ e $T_2$ estão ordenadas (todas as chaves X em $T_1$ são menores que as chaves em $T_2$). Portanto, precisamos combinar essas árvores sem violar a ordem das prioridades Y. Para fazer isso, escolhemos como raiz a árvore que tem maior prioridade Y no nó raiz, e recursivamente chamamos Merge para a outra árvore e a subtree correspondente do nó raiz selecionado.

Implementação de Insert (X, Y). Primeiro descemos na árvore (como em uma binary search tree regular por X), e paramos no primeiro nó em que o valor da prioridade é menor que Y. Encontramos o local onde iremos inserir o novo elemento. Em seguida, chamamos Split (T, X) na subtree começando do nó encontrado, usamos as subtrees retornadas L e R como filhos esquerdo e direito do novo nó.

Implementação de Erase (X). Primeiro descemos na árvore (como em uma binary search tree regular por X), procurando o elemento que queremos excluir. Depois que o nó é encontrado, chamamos Merge em seus filhos e colocamos o valor de retorno da operação no local do elemento que estamos deletando.

Nós implementamos a operação Build com complexidade $O (N \log N)$ usando $N$ chamadas com Insert.

Union ($T_1$, $T_2$) tem complexidade teórica de $O (M \log (N / M))$, mas na prática funciona muito bem, provavelmente com uma constante oculta muito pequena. Vamos assumir, sem perda de generalidade, que $T_1 \rightarrow Y > T_2 \rightarrow Y$, ou seja, a raiz de $T_1$ será a raiz do resultado. Para obter o resultado, precisamos mesclar as árvores $T_1 \rightarrow L$, $T_1 \rightarrow R$ e $T_2$ em duas árvores que podem ser filhas da raiz de $T_1$. Para fazer isso, chamamos Split ($T_2$, $T_1\rightarrow X$), dividindo assim $T_2$ em duas partes L e R, que depois combinamos recursivamente com os filhos de $T_1$: Union ($T_1 \rightarrow L$, $L$) e Union ($T_1 \rightarrow R$, $R$), obtendo assim as subárvores esquerda e direita do resultado.

Implementação

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

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

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 (it->key < t->key ? t->l : t->r, 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)
        merge (t, t->l, t->r);
    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;
}

Mantendo os tamanhos das subtrees

Para estender a funcionalidade do treap, geralmente é necessário armazenar o número de nós na subárvore de cada nó - (contador)int cnt na estrutura item. Por exemplo, ele pode ser usado para encontrar o K-ésimo maior elemento da árvore em $O (\log N)$, ou para encontrar o índice do elemento na lista ordenada com a mesma complexidade. A implementação dessas operações será a mesma para uma binary search tree normal.

Quando uma árvore muda (nós são adicionados ou removidos etc.), o cnt de alguns nós deve ser atualizado de acordo. Criaremos duas funções: cnt() retornará o valor atual de cnt ou 0 se o nó não existir, e upd_cnt() irá atualizar o valor de cnt para esse nó, assumindo que, para seus filhos L e R seus valores de cnt já foram atualizados. Evidentemente, é suficiente adicionar chamadas de upd_cnt() ao final de insert, erase, split e merge para manter os valores de cnt atualizados.

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);
}

Construindo uma Treap em $O (N)$ (modo offline)

Dada uma lista ordenada de chaves, é possível construir uma treap mais rápido do que inserindo as chaves uma por vez, o que leva $O(N \log N)$. Como as chaves estão ordenadas, uma binary search tree balanceada pode ser construída em tempo linear. Os valores heap $Y$ são inicializados aleatoriamente e, em seguida, podem ser "ordenados"(heapified - heap sort) independentemente das chaves $X$ para construir o heap em $O(N)$.

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) {
    // Construir uma treap com os valores {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);
    return t;
}

Também é possível calcular os tamanhos das subárvores com essa abordagem. Basta chamar upd_cnt(t) antes de retornar da função build.

Treaps Implícitas

Treap implícita é uma modificação simples do treap regular, que é uma estrutura de dados muito poderosa. De fato, a treap implícita pode ser considerada como uma array com os seguintes procedimentos implementados (todos em $O (\log N)$ - modo online):

A idéia é que as chaves sejam índices dos elementos na array. Mas não armazenaremos esses valores explicitamente (caso contrário, por exemplo, a inserção de um elemento causaria alterações nas chaves dos $O (N)$ nós da árvore).

Observe que a chave de um nó é o número de nós menor que ele (esses nós podem estar presentes não apenas na subárvore esquerda, mas também nas subárvores esquerdas de seus ancestrais). Mais especificamente, a chave implícita para algum nó T é o número de vértices $cnt (T \rightarrow L)$ na subárvore esquerda desse nó, mais os valores semelhantes $cnt (P \rightarrow L) + 1$ para cada ancestral P do nó T, se T estiver na subárvore direita de P.

Como em todas as operações chegamos a qualquer nó descendo na árvore, podemos apenas acumular essa soma e passá-la para a função. Se formos para a subárvore esquerda, a soma acumulada não será alterada; se formos para a subárvore direita, ela aumentará em $cnt (T \rightarrow L) +1$.

Aqui estão as novas implementações de Split e 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); //chave implícita
    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);
}

Agora, vamos considerar a implementação de várias operações em treaps implícitas:

Aqui está um exemplo de implementação da treap implícita com reversão no intervalo. Para cada nó, armazenamos o campo chamado value que é o valor real do elemento da array na posição atual. Também fornecemos a implementação da função output(), que gera uma array que corresponde ao estado atual da treap implícita.

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);
}

Referências

Problemas