Árvores Binárias de Busca (ABB)
Uma Árvore Binária de Busca é uma estrutura de dados em árvore que satisfaz a seguinte propriedade: para qualquer nó p, todos os valores presentes em sua subárvore esquerda são estritamente menores que o valor de p, e todos os valores em sua subárvore direita são estritamente maiores.
Essa propriedade permite a implementação eficiente de diversas operações fundamentais:
- Inserção e remoção de elementos;
- Consulta da posição (rank) de um valor específico;
- Consulta do valor que ocupa uma determinada posição (rank);
- Busca pelo predecessor (maior valor menor que x) e sucessor (menor valor maior que x).
Para n nós, a complexidade ótima para essas operações é O(log n), o que corresponde à altura esperada de uma ABB construída com inserções aleatórias. No entanto, se os dados forem inseridos em ordem crescente ou decrescente, a árvore degenera em uma lista encadeada, elevando a complexidade para O(n). Árvores balanceadas surgem para garantir que a altura seja mantida em O(log n), assegurando a eficiência das operações.
O Conceito de Treap com Rotações
O nome "Treap" é uma combinação de "Tree" (Árvore) e "Heap". A estrutura utiliza um Heap para controlar a altura da Árvore Binária de Busca. Além da chave de busca tradicional, cada nó recebe uma prioridade aleatória. Através de operações de rotação, a árvore é ajusatda para satisfazer simultaneamente duas condições:
- As chaves obedecem à propriedade da Árvore Binária de Busca.
- As prioridades aleatórias obedecem à propriedade de um Heap (geralmente um max-heap ou min-heap).
Como as prioridades são atribuídas de forma aleatória, a altura da árvore tende a ser O(log n) com alta probabilidade, mantendo a complexidade das operações dentro desse limite.
Para manter a propriedade do Heap durante inserções e remoções, utilizamos rotações. As rotações (à esquerda e à direita) alteram a relação de parentesco entre um nó e seu filho, modificando a estrutura da árvore sem violar a ordem relativa das chaves da ABB. Essa é a essência do Treap com rotações.
Implementação Prática
Estrutura do Nó e Funções Auxiliares
Cada nó precisa armazenar os índices de seus filhos (esquerda e direita), a chave de busca (key), a conatgem de ocorrências dessa chave (count), o tamanho total da subárvore (size) e a prioridade aleatória (priority). Utilizamos alocação estática via arrays para maior eficiência.
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <algorithm>
using namespace std;
const int MAX_NODES = 100005;
const int INF = 1e9 + 5;
struct TreapNode {
int left, right;
int key, count, size, priority;
} tree[MAX_NODES];
int nodeCount = 0;
int root = 0;
int createNode(int key) {
int idx = ++nodeCount;
tree[idx].key = key;
tree[idx].count = 1;
tree[idx].size = 1;
tree[idx].priority = rand();
tree[idx].left = tree[idx].right = 0;
return idx;
}
void updateSize(int idx) {
if (idx) {
tree[idx].size = tree[tree[idx].left].size + tree[tree[idx].right].size + tree[idx].count;
}
}
Operações de Rotação
As rotações ajustam a árvore para manter a propriedade do Heap. A rotação à direita promove o filho esquerdo, e a rotação à esquerda promove o filho direito.
void rotateRight(int &idx) {
int leftChild = tree[idx].left;
tree[idx].left = tree[leftChild].right;
tree[leftChild].right = idx;
idx = leftChild;
updateSize(tree[idx].right);
updateSize(idx);
}
void rotateLeft(int &idx) {
int rightChild = tree[idx].right;
tree[idx].right = tree[rightChild].left;
tree[rightChild].left = idx;
idx = rightChild;
updateSize(tree[idx].left);
updateSize(idx);
}
Inserção e Remoção
A inserção segue o caminho da ABB. Ao encontrar a posição, o nó é criado. Se a prioridade do novo nó violar a propriedade do Heap em relação ao pai, uma rotação é aplicada. A remoção segue lógica similar: se o nó a ser removido tem dois filhos, ele é rotacionado para baixo até se tornar uma folha ou ter apenas um filho, facilitando a exclusão.
void insertNode(int &idx, int key) {
if (!idx) {
idx = createNode(key);
return;
}
if (tree[idx].key == key) {
tree[idx].count++;
} else if (key < tree[idx].key) {
insertNode(tree[idx].left, key);
if (tree[tree[idx].left].priority > tree[idx].priority) {
rotateRight(idx);
}
} else {
insertNode(tree[idx].right, key);
if (tree[tree[idx].right].priority > tree[idx].priority) {
rotateLeft(idx);
}
}
updateSize(idx);
}
void removeNode(int &idx, int key) {
if (!idx) return;
if (tree[idx].key == key) {
if (tree[idx].count > 1) {
tree[idx].count--;
updateSize(idx);
return;
}
if (!tree[idx].left) {
idx = tree[idx].right;
} else if (!tree[idx].right) {
idx = tree[idx].left;
} else {
if (tree[tree[idx].left].priority > tree[tree[idx].right].priority) {
rotateRight(idx);
removeNode(tree[idx].right, key);
} else {
rotateLeft(idx);
removeNode(tree[idx].left, key);
}
}
} else if (key < tree[idx].key) {
removeNode(tree[idx].left, key);
} else {
removeNode(tree[idx].right, key);
}
updateSize(idx);
}
Consultas de Rank, K-ésimo, Predecessor e Sucessor
Essas operações exploram o tamanho das subárvores (size) para navegar pela árvore de forma aáloga a uma busca binária.
int findRank(int idx, int key) {
if (!idx) return 1;
if (key == tree[idx].key) return tree[tree[idx].left].size + 1;
if (key > tree[idx].key) return tree[tree[idx].left].size + tree[idx].count + findRank(tree[idx].right, key);
return findRank(tree[idx].left, key);
}
int findKth(int idx, int k) {
if (!idx) return 0;
int leftSize = tree[tree[idx].left].size;
if (k <= leftSize) return findKth(tree[idx].left, k);
if (k <= leftSize + tree[idx].count) return tree[idx].key;
return findKth(tree[idx].right, k - leftSize - tree[idx].count);
}
int findPredecessor(int idx, int key) {
if (!idx) return -INF;
if (tree[idx].key < key) {
return max(tree[idx].key, findPredecessor(tree[idx].right, key));
}
return findPredecessor(tree[idx].left, key);
}
int findSuccessor(int idx, int key) {
if (!idx) return INF;
if (tree[idx].key > key) {
return min(tree[idx].key, findSuccessor(tree[idx].left, key));
}
return findSuccessor(tree[idx].right, key);
}
Aplicações e Exemplos
Exemplo 1: Template de Árvore Balanceada Padrão
Implementação clássica que suporta as seis operações básicas. O uso de srand(time(0)) garante a aleatoriedade das prioridades.
int main() {
srand(time(0));
int n, opt, x;
scanf("%d", &n);
while (n--) {
scanf("%d%d", &opt, &x);
switch (opt) {
case 1: insertNode(root, x); break;
case 2: removeNode(root, x); break;
case 3: printf("%d\n", findRank(root, x)); break;
case 4: printf("%d\n", findKth(root, x)); break;
case 5: printf("%d\n", findPredecessor(root, x)); break;
case 6: printf("%d\n", findSuccessor(root, x)); break;
}
}
return 0;
}
Exemplo 2: Template com Processamento Online
Variante que exige processamento online, onde as consultas são mascaradas com o XOR da última resposta. Requer o uso de long long para evitar overflow.
int main() {
srand(time(0));
long long n, m, opt, x;
long long lastAns = 0, totalAns = 0;
scanf("%lld%lld", &n, &m);
while (n--) {
scanf("%lld", &x);
insertNode(root, x);
}
while (m--) {
scanf("%lld%lld", &opt, &x);
x ^= lastAns;
switch (opt) {
case 1: insertNode(root, x); break;
case 2: removeNode(root, x); break;
case 3: totalAns ^= (lastAns = findRank(root, x)); break;
case 4: totalAns ^= (lastAns = findKth(root, x)); break;
case 5: totalAns ^= (lastAns = findPredecessor(root, x)); break;
case 6: totalAns ^= (lastAns = findSuccessor(root, x)); break;
}
}
printf("%lld", totalAns);
return 0;
}
Exemplo 3: Problema do Black Box
Um cenário restrito que exige apenas inserções e consultas do K-ésimo elemento, processando as inserções de forma acumulativa conforme os índices de consulta são atingidos.
int main() {
srand(time(0));
int n, m, pos = 0, p = 1, x;
int in[200005];
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &in[i]);
}
while (m--) {
scanf("%d", &x);
while (p <= x) {
insertNode(root, in[p++]);
}
printf("%d\n", findKth(root, ++pos));
}
return 0;
}