Conceitos e Implementação de Árvores de Busca Binária e Treap

Árvore de Busca Binária (BST)

Uma Árvore de Busca Binária é uma estrutura de dados hierárquica onde cada nó contém uma chave, e mantém a propriedade de que todas as chaves na subárvore esquerda são menores que a chave do nó, e todas na subárvore direita são maiores. Uma característica notável é que uma travessia em ordem resulta em uma sequência ordenada das chaves.

Propriedades

Para qualquer nó, as chaves na subárvore esquerda são menores que a chave do nó, e as na subárvore direita são maiores.
A travessia em ordem produz uma sequência ordenada das chaves, por exemplo, para uma árvore com chaves 1 a 11, a travessia é 1,2,3,4,5,6,7,8,9,10,11.

Operações Básicas

As operações em uma BST incluem inserção, remoção, busca por rank, busca pelo k-ésimo menor elemento, predecessor e sucessor. No caso ideal, essas operações têm complexidade O(log n), mas podem degenerar para O(n) se a árvore se tornar uma lista encadeada devido a dados desbalanceados.

Treap

Um Treap é uma estrutura de dados híbrida que combina as propriedades de uma Árvore de Busca Binária (BST) com as de um Heap. Cada nó possui uma chave para manter a ordem BST e uma prioridade aleatória para manter a propriedade de heap, o que ajuda a evitar a degeneração em uma lista encadeada.

Propriedades

Satisfaz a propriedade BST com base nas chaves dos nós.
Satisfaz a propriedade de heap (por exemplo, heap máximo) com base nas prioridades aleatórias atribuídas aos nós.
As prioridades são geradas aleatoriamente para garantir balanceamento probabilístico, reduzindo a chance de degeneração.

Operações Suportadas

As operações em um Treap incluem inserção, remoção, busca por rank, busca pelo k-ésimo menor elemento, predecessor e sucessor, todas com complexidade esperada O(log n) devido à priorização aleatória.

Manutenção e Implementação

Informação do Nó

struct No {
    int esquerda, direita, valor, tamanho, contagem;
    unsigned prioridade;
} nos[MAX];

Inserção com Rotações

Para manter tanto a propriedade BST quanto a de heap, utilizamos rotações: rotação à direita (zig) e rotação à esquerda (zag). Essas operações reorganizam a árvore sem violar a propriedade BST.

void atualizarTamanho(int u) {
    if (!u) return;
    nos[u].tamanho = nos[nos[u].esquerda].tamanho + nos[nos[u].direita].tamanho + nos[u].contagem;
}

void rotacionarDireita(int &y) {
    int x = nos[y].esquerda;
    nos[y].esquerda = nos[x].direita;
    nos[x].direita = y;
    atualizarTamanho(y);
    atualizarTamanho(x);
    y = x;
}

void rotacionarEsquerda(int &y) {
    int x = nos[y].direita;
    nos[y].direita = nos[x].esquerda;
    nos[x].esquerda = y;
    atualizarTamanho(y);
    atualizarTamanho(x);
    y = x;
}

Inserção de um Elemento

int criarNo(int v) {
    nos[++totalNos] = {0, 0, v, 1, 1, gerarPrioridade()};
    return totalNos;
}

void inserir(int &raiz, int v) {
    if (!raiz) {
        raiz = criarNo(v);
        atualizarTamanho(raiz);
        return;
    }
    if (v == nos[raiz].valor) {
        nos[raiz].contagem++;
        atualizarTamanho(raiz);
        return;
    } else if (v < nos[raiz].valor) {
        inserir(nos[raiz].esquerda, v);
        if (nos[nos[raiz].esquerda].prioridade < nos[raiz].prioridade) {
            rotacionarDireita(raiz);
        }
    } else {
        inserir(nos[raiz].direita, v);
        if (nos[nos[raiz].direita].prioridade < nos[raiz].prioridade) {
            rotacionarEsquerda(raiz);
        }
    }
    atualizarTamanho(raiz);
}

Remoção de um Elemento

void remover(int &raiz, int v) {
    if (!raiz) return;
    if (v == nos[raiz].valor) {
        if (nos[raiz].contagem > 1) {
            nos[raiz].contagem--;
            atualizarTamanho(raiz);
            return;
        } else if (!nos[raiz].esquerda && !nos[raiz].direita) {
            raiz = 0;
            return;
        } else if (!nos[raiz].direita || (nos[raiz].esquerda && nos[nos[raiz].esquerda].prioridade > nos[nos[raiz].direita].prioridade)) {
            rotacionarDireita(raiz);
            remover(nos[raiz].direita, v);
        } else {
            rotacionarEsquerda(raiz);
            remover(nos[raiz].esquerda, v);
        }
    } else if (v < nos[raiz].valor) {
        remover(nos[raiz].esquerda, v);
    } else {
        remover(nos[raiz].direita, v);
    }
    atualizarTamanho(raiz);
}

Busca por Rank e k-ésimo Elemento

int buscarRank(int raiz, int v) {
    if (!raiz) return 1;
    if (v == nos[raiz].valor) {
        return nos[nos[raiz].esquerda].tamanho + 1;
    } else if (v < nos[raiz].valor) {
        return buscarRank(nos[raiz].esquerda, v);
    } else {
        return nos[nos[raiz].esquerda].tamanho + nos[raiz].contagem + buscarRank(nos[raiz].direita, v);
    }
}

int buscarKEsimo(int raiz, int k) {
    if (!raiz) return -1;
    if (k <= nos[nos[raiz].esquerda].tamanho) {
        return buscarKEsimo(nos[raiz].esquerda, k);
    }
    k -= nos[nos[raiz].esquerda].tamanho;
    if (k <= nos[raiz].contagem) {
        return nos[raiz].valor;
    }
    k -= nos[raiz].contagem;
    return buscarKEsimo(nos[raiz].direita, k);
}

Predecessor e Sucessor

int buscarPredecessor(int raiz, int v) {
    int resposta = -INF;
    while (raiz) {
        if (v <= nos[raiz].valor) {
            raiz = nos[raiz].esquerda;
        } else {
            resposta = nos[raiz].valor;
            raiz = nos[raiz].direita;
        }
    }
    return resposta;
}

int buscarSucessor(int raiz, int v) {
    int resposta = INF;
    while (raiz) {
        if (v >= nos[raiz].valor) {
            raiz = nos[raiz].direita;
        } else {
            resposta = nos[raiz].valor;
            raiz = nos[raiz].esquerda;
        }
    }
    return resposta;
}

Exemplo Completo em C++

#include <iostream>
#include <chrono>
using namespace std;

const int MAX_NOS = 200005;
const int INF = 0x3f3f3f3f;

static unsigned semente = (unsigned)chrono::steady_clock::now().time_since_epoch().count();
unsigned gerarPrioridade() {
    semente ^= semente << 12;
    semente ^= semente >> 5;
    semente ^= semente << 11;
    return semente;
}

struct No {
    int esquerda, direita, valor, tamanho, contagem;
    unsigned prioridade;
} nos[MAX_NOS];

int totalNos = 0;
int raizArvore = 0;

int criarNo(int v) {
    nos[++totalNos] = {0, 0, v, 1, 1, gerarPrioridade()};
    return totalNos;
}

void atualizarTamanho(int u) {
    if (!u) return;
    nos[u].tamanho = nos[nos[u].esquerda].tamanho + nos[nos[u].direita].tamanho + nos[u].contagem;
}

void rotacionarDireita(int &y) {
    int x = nos[y].esquerda;
    nos[y].esquerda = nos[x].direita;
    nos[x].direita = y;
    atualizarTamanho(y);
    atualizarTamanho(x);
    y = x;
}

void rotacionarEsquerda(int &y) {
    int x = nos[y].direita;
    nos[y].direita = nos[x].esquerda;
    nos[x].esquerda = y;
    atualizarTamanho(y);
    atualizarTamanho(x);
    y = x;
}

void inserir(int &raiz, int v) {
    if (!raiz) {
        raiz = criarNo(v);
        atualizarTamanho(raiz);
        return;
    }
    if (v == nos[raiz].valor) {
        nos[raiz].contagem++;
        atualizarTamanho(raiz);
        return;
    } else if (v < nos[raiz].valor) {
        inserir(nos[raiz].esquerda, v);
        if (nos[nos[raiz].esquerda].prioridade < nos[raiz].prioridade) {
            rotacionarDireita(raiz);
        }
    } else {
        inserir(nos[raiz].direita, v);
        if (nos[nos[raiz].direita].prioridade < nos[raiz].prioridade) {
            rotacionarEsquerda(raiz);
        }
    }
    atualizarTamanho(raiz);
}

void remover(int &raiz, int v) {
    if (!raiz) return;
    if (v == nos[raiz].valor) {
        if (nos[raiz].contagem > 1) {
            nos[raiz].contagem--;
            atualizarTamanho(raiz);
            return;
        } else if (!nos[raiz].esquerda && !nos[raiz].direita) {
            raiz = 0;
            return;
        } else if (!nos[raiz].direita || (nos[raiz].esquerda && nos[nos[raiz].esquerda].prioridade > nos[nos[raiz].direita].prioridade)) {
            rotacionarDireita(raiz);
            remover(nos[raiz].direita, v);
        } else {
            rotacionarEsquerda(raiz);
            remover(nos[raiz].esquerda, v);
        }
    } else if (v < nos[raiz].valor) {
        remover(nos[raiz].esquerda, v);
    } else {
        remover(nos[raiz].direita, v);
    }
    atualizarTamanho(raiz);
}

int buscarRank(int raiz, int v) {
    if (!raiz) return 1;
    if (v == nos[raiz].valor) {
        return nos[nos[raiz].esquerda].tamanho + 1;
    } else if (v < nos[raiz].valor) {
        return buscarRank(nos[raiz].esquerda, v);
    } else {
        return nos[nos[raiz].esquerda].tamanho + nos[raiz].contagem + buscarRank(nos[raiz].direita, v);
    }
}

int buscarKEsimo(int raiz, int k) {
    if (!raiz) return -1;
    if (k <= nos[nos[raiz].esquerda].tamanho) {
        return buscarKEsimo(nos[raiz].esquerda, k);
    }
    k -= nos[nos[raiz].esquerda].tamanho;
    if (k <= nos[raiz].contagem) {
        return nos[raiz].valor;
    }
    k -= nos[raiz].contagem;
    return buscarKEsimo(nos[raiz].direita, k);
}

int buscarPredecessor(int raiz, int v) {
    int resposta = -INF;
    while (raiz) {
        if (v <= nos[raiz].valor) {
            raiz = nos[raiz].esquerda;
        } else {
            resposta = nos[raiz].valor;
            raiz = nos[raiz].direita;
        }
    }
    return resposta;
}

int buscarSucessor(int raiz, int v) {
    int resposta = INF;
    while (raiz) {
        if (v >= nos[raiz].valor) {
            raiz = nos[raiz].direita;
        } else {
            resposta = nos[raiz].valor;
            raiz = nos[raiz].esquerda;
        }
    }
    return resposta;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    while (n--) {
        int operacao, x;
        cin >> operacao >> x;
        if (operacao == 1) {
            inserir(raizArvore, x);
        } else if (operacao == 2) {
            remover(raizArvore, x);
        } else if (operacao == 3) {
            cout << buscarRank(raizArvore, x) << endl;
        } else if (operacao == 4) {
            cout << buscarKEsimo(raizArvore, x) << endl;
        } else if (operacao == 5) {
            cout << buscarPredecessor(raizArvore, x) << endl;
        } else if (operacao == 6) {
            cout << buscarSucessor(raizArvore, x) << endl;
        }
    }
    return 0;
}

Tags: BST Treap C++ Estruturas de Dados árvores binárias de busca

Publicado em 6-27 06:47

Doido Dev

Conceitos e Implementação de Árvores de Busca Binária e Treap

Árvore de Busca Binária (BST)

Propriedades

Operações Básicas

Treap

Propriedades

Operações Suportadas

Manutenção e Implementação

Informação do Nó

Inserção com Rotações

Inserção de um Elemento

Remoção de um Elemento

Busca por Rank e k-ésimo Elemento

Predecessor e Sucessor

Exemplo Completo em C++

Tags em Destaque