A árvore Splay é uma estrutura de dados balanceada que suporta operações eficientes em conjuntos e sequências. Diferente de outras árvores binárias de busca, ela mantém a propriedade de que o percurso in-order em uma sequência mantida correspnode à própria sequência. A complexidade amortida das operações como inserção, remoção e busca é O(log n), garantida por análise de potencial.

O princípio fundamental das árvores Splay é mover o nó acessado para a raiz após cada operação, usando rotações. Isso otimiza o acesso frequente a determinados nós, adaptando-se a padrões de acesso.

Rotações

As rotações em árvores Splay são semelhantes às de árvores Treap, mas incluem rotações simples e duplas. Rotações simples são rotações à esquerda ou à direita, enquanto rotações duplas combinam múltiplas rotações para balancear a árvore.

Rotação Simples

Uma rotação simples altera a estrutura local da árvore para mover um nó para cima. O código a seguir implementa uma rotação genérica usando operações bit a bit para simplificar a lógica.

const int MAX_NOS = 100005;

struct No {
    int filhos[2], pai;
    int valor, contagem, tamanho;
#define esq (arvore[pos].filhos[0])
#define dir (arvore[pos].filhos[1])
} arvore[MAX_NOS];
int totalNos, raiz;

int criarNo(int val) {
    int id = ++totalNos;
    arvore[id].valor = val;
    arvore[id].contagem = arvore[id].tamanho = 1;
    return id;
}

int obterPosicao(int pos) {
    return pos == arvore[arvore[pos].pai].filhos[1];
}

void atualizarTamanho(int pos) {
    arvore[pos].tamanho = arvore[esq].tamanho + arvore[dir].tamanho + arvore[pos].contagem;
}

void conectar(int pos, int novoPai, int direcao) {
    arvore[pos].pai = novoPai;
    arvore[novoPai].filhos[direcao] = pos;
}

void rotacaoSimples(int pos) {
    int pai = arvore[pos].pai;
    int avo = arvore[pai].pai;
    int direcao = obterPosicao(pos);
    conectar(pos, avo, obterPosicao(pai));
    conectar(arvore[pos].filhos[direcao ^ 1], pai, direcao);
    conectar(pai, pos, direcao ^ 1);
    atualizarTamanho(pai);
    atualizarTamanho(pos);
}

Rotações Duplas

Rotações duplas são aplicadas quando o nó alvo e seu pai estão no mesmo lado (ajuste isomórfico) ou em lados opostos (ajuste anisomórfico) em relação ao avô. O objetivo é balancear a árvore mais eficientemente.

Operação Splay

A operação Splay move um nó para uma posição alvo (geralmente a raiz) usando rotações duplas repetidamente. O código a seguir implementa essa operação, garantindo que o nó seja acessado frequentemente permaneça próximo à raiz.

void splay(int pos, int alvo) {
    if (!alvo) raiz = pos;
    while (arvore[pos].pai != alvo) {
        if (arvore[arvore[pos].pai].pai != alvo) {
            if (obterPosicao(pos) ^ obterPosicao(arvore[pos].pai))
                rotacaoSimples(pos);
            else
                rotacaoSimples(arvore[pos].pai);
        }
        rotacaoSimples(pos);
    }
}

Operações de Árvore de Busca Binária

As operações padrão de inserção, busca de predecessor/sucessor e remoção são semelhantes às de outras árvores balanceadas, mas seguidas de uma operação Splay no nó acessado.

Inserção

A inserção adiciona um novo nó e o move para a raiz usando Splay.

void inserir(int &pos, int val, int pai) {
    if (!pos) {
        pos = criarNo(val);
        arvore[pos].pai = pai;
        splay(pos, 0);
        return;
    }
    if (val < arvore[pos].valor)
        inserir(esq, val, pos);
    else if (val > arvore[pos].valor)
        inserir(dir, val, pos);
    else
        arvore[pos].contagem++;
    atualizarTamanho(pos);
}

Busca de Predecessor e Sucessor

Para encontrar o predecsesor ou sucessor de um valor, percorremos a árvore e aplicamos Splay no nó resultante para otimizar futuros acessos.

int obterPredecessor(int pos, int val) {
    if (!pos) return -1;
    if (arvore[pos].valor >= val) return obterPredecessor(esq, val);
    int candidato = obterPredecessor(dir, val);
    if (candidato == -1 || arvore[pos].valor > arvore[candidato].valor) {
        if (pos == raiz) splay(pos, 0);
        return pos;
    } else {
        if (candidato == raiz) splay(candidato, 0);
        return candidato;
    }
}

int obterSucessor(int pos, int val) {
    if (!pos) return -1;
    if (arvore[pos].valor <= val) return obterSucessor(dir, val);
    int candidato = obterSucessor(esq, val);
    if (candidato == -1 || arvore[pos].valor < arvore[candidato].valor) {
        if (pos == raiz) splay(pos, 0);
        return pos;
    } else {
        if (candidato == raiz) splay(candidato, 0);
        return candidato;
    }
}

Remoção

Para remover um nó, primeiro movemos ele para a raiz com Splay. Se a contagem for maior que 1, decrementamos; caso contrário, removemos o nó e mesclamos as subárvores.

Manutenção de Informações

Árvores Splay podem manter informações adicionais, como marcações de atraso para operações em intervalos. Um exemplo clássico é a inversão de intervalos, onde nós são rotulados para indicar inversões pendentes, semelhante a técnicas usadas em árvores de segmentos.

Para implementar operações como inversão de intervalos, utilizamos uma marcação de atraso que é propagada durante as rotações e acessos, garantindo que as operações sejam aplicadas de forma eficiente.