Árvores binárias de busca (BST) são eficientes quando balanceadas, mas podem degenerar em uma lista encadeada se os dados forem enseridos em ordem. Para resolver esse problema, surgem as árvores balanceadas, que mantêm a altura próxima de O(log n) através de rotações ou operações de divisão e mesclagem.

Neste artigo, exploramos duas variantes populares: o Treap (rotacional) e o FHQ Treap (não rotacional). Ambos combinam as propriedades de BST com a de um heap, atribuindo a cada nó uma prioridade aleatória. A árvore resultante satisfaz:

• Propriedade BST: valor do nó maior que todos os valores da subárvore esquerda e menor que todos da subárvore direita.
• Propriedade de heap (max-heap): a prioridade de cada nó é maior que a de seus filhos.

As operações suportadas são: inserir, remover, consultar a posição (rank) de um valor, obter o valor de uma dada posição, além de predecessor e sucessor.

Treap (Rotacional)

O Treap utiliza rotações (esquerda e direita) para manter o heap. Quando um nó filho tem prioridade maior que o pai, aplica-se uma rotação que sobe o filho e desce o pai, preservando a ordem BST.

Rotação direita: o nó y tem filho esquerdo x. Após a rotação, x sobe, y torna‑se filho direito de x, e o filho direito original de x passa a ser filho esquerdo de y. A rotação esquerda é o movimento inverso.

Estrutura do nó (C++):

struct Node {
    int ch[2];          // 0=esquerda, 1=direita
    int val, prio;      // valor e prioridade aleatória
    int sz, cnt;        // tamanho da subárvore, contagem de cópias
};
int tot, root;

Atualizar tamanho:

void pushup(int p) {
    sz[p] = sz[ch[p][0]] + sz[ch[p][1]] + cnt[p];
}

Novo nó:

int newNode(int v) {
    val[++tot] = v;
    prio[tot] = rand();
    sz[tot] = 1;
    cnt[tot] = 1;
    return tot;
}

Rotação:

void rotate(int &p, int d) {  // d=0: direita, d=1: esquerda
    int q = ch[p][d^1];
    ch[p][d^1] = ch[q][d];
    ch[q][d] = p;
    p = q;
    pushup(ch[p][d]);
    pushup(p);
}

Inserção:

void insert(int &p, int v) {
    if (!p) {
        p = newNode(v);
        return;
    }
    if (v == val[p]) {
        cnt[p]++;
    } else {
        int d = (v < val[p]) ? 0 : 1;
        insert(ch[p][d], v);
        if (prio[p] < prio[ch[p][d]])
            rotate(p, d^1);
    }
    pushup(p);
}

Remoção:

void remove(int &p, int v) {
    if (!p) return;
    if (v == val[p]) {
        if (cnt[p] > 1) {
            cnt[p]--; pushup(p);
            return;
        }
        if (!ch[p][0] || !ch[p][1]) {
            p = ch[p][0] + ch[p][1];
        } else {
            int d = (prio[ch[p][0]] > prio[ch[p][1]]) ? 1 : 0;
            rotate(p, d);
            remove(ch[p][d], v);
        }
    } else {
        int d = (v < val[p]) ? 0 : 1;
        remove(ch[p][d], v);
    }
    if (p) pushup(p);
}

Consultar rank (posição do valor):

int getRank(int p, int v) {
    if (!p) return 0;
    if (v == val[p]) return sz[ch[p][0]] + 1;
    if (v < val[p]) return getRank(ch[p][0], v);
    return sz[ch[p][0]] + cnt[p] + getRank(ch[p][1], v);
}

Obter valor por rank:

int getVal(int p, int k) {
    if (!p) return -1;
    if (k <= sz[ch[p][0]]) return getVal(ch[p][0], k);
    if (k <= sz[ch[p][0]] + cnt[p]) return val[p];
    return getVal(ch[p][1], k - sz[ch[p][0]] - cnt[p]);
}

Predecessor e sucessor (iterativos):

int pre(int v) {
    int p = root, ans = -INF;
    while (p) {
        if (val[p] < v) { ans = val[p]; p = ch[p][1]; }
        else p = ch[p][0];
    }
    return ans;
}

int nxt(int v) {
    int p = root, ans = INF;
    while (p) {
        if (val[p] > v) { ans = val[p]; p = ch[p][0]; }
        else p = ch[p][1];
    }
    return ans;
}

FHQ Treap (Não Rotacional)

O FHQ (ou Treap sem rotação) baseia‑se em duas operações fundamentais: split (dividir a árvore em duas) e merge (mesclar duas árvores). A estrutura do nó é semelhante, mas sem contagem de cópias (valores repetidos são nós distintos na implementação clássica).

Estrutura do nó:

struct Node {
    int l, r;
    int val, key;  // key = prioridade aleatória
    int sz;
} tr[N];
int root, tot;

Novo nó e atualização:

int newNode(int v) {
    tr[++tot] = {0, 0, v, rand(), 1};
    return tot;
}
void pushup(int p) {
    tr[p].sz = tr[tr[p].l].sz + tr[tr[p].r].sz + 1;
}

Split (por valor): divide a árvore em duas: x (valores ≤ val) e y (valores > val).

void split(int p, int val, int &x, int &y) {
    if (!p) { x = y = 0; return; }
    if (tr[p].val <= val) {
        x = p;
        split(tr[p].r, val, tr[p].r, y);
    } else {
        y = p;
        split(tr[p].l, val, x, tr[p].l);
    }
    pushup(p);
}

Merge: combina duas árvores onde todos os valores de x são menores que os de y.

int merge(int x, int y) {
    if (!x || !y) return x + y;
    if (tr[x].key > tr[y].key) {
        tr[x].r = merge(tr[x].r, y);
        pushup(x);
        return x;
    } else {
        tr[y].l = merge(x, tr[y].l);
        pushup(y);
        return y;
    }
}

Inserção:

void insert(int v) {
    int x, y;
    split(root, v, x, y);
    root = merge(merge(x, newNode(v)), y);
}

Remoção (de um nó com valor v):

void remove(int v) {
    int x, y, z;
    split(root, v, x, z);
    split(x, v-1, x, y);
    y = merge(tr[y].l, tr[y].r);  // descarta a raiz de y
    root = merge(merge(x, y), z);
}

Rank de v:

int getRank(int v) {
    int x, y;
    split(root, v-1, x, y);
    int res = tr[x].sz + 1;
    root = merge(x, y);
    return res;
}

Valor na posição k:

int getVal(int k) {
    int p = root;
    while (p) {
        if (tr[tr[p].l].sz + 1 == k) return tr[p].val;
        if (tr[tr[p].l].sz >= k) p = tr[p].l;
        else { k -= tr[tr[p].l].sz + 1; p = tr[p].r; }
    }
    return -1;
}

Predecessor e sucessor com split/merge:

int pre(int v) {
    int x, y;
    split(root, v-1, x, y);
    int p = x;
    while (tr[p].r) p = tr[p].r;
    root = merge(x, y);
    return tr[p].val;
}

int nxt(int v) {
    int x, y;
    split(root, v, x, y);
    int p = y;
    while (tr[p].l) p = tr[p].l;
    root = merge(x, y);
    return tr[p].val;
}

Conclusão

Ambas as implementações oferecem complexidade O(log n) esperada para todas as operações. O Treap rotacional é mais intuitivo para quem já conhece rotações de árvores, enquanto o FHQ Treap simplifica drasticamente a remoção e a obtenção de ordem estatística, além de ser facilmente extensível para suportar operações em intervalos.