Árvore Binária de Busca

Motivação

As operações de inserção, remoção e busca em estruturas de dados costumam ter custos complementares, proveniente de um tradeoff na hora de implementação.

Operação	Lista Duplamente Encadeada	Vetor Não Ordenado	Vetor Ordenado	Árvore Binária de Busca
Inserção e Remoção	\(O(1)\)	\(O(1)\)	\(O(n)\)	\(O(log\ n)\)
Busca	\(O(n)\)	\(O(n)\)	\(O(n\cdot log\ n)\)	\(O(log\ n)\)

Tabela 1: Custo das Operações. Fonte: [1]

A inserção e remoção em vetores não ordenados pode ter custo \(O(1)\) ao inserir sempre no final e remover fazendo a troca com a última posição.

As Árvores Binárias de Busca, na sua versão mais sofisticada, oferecem operações de inserção, remoção e busca com custo \(O(log\ n)\).

Definição

Uma árvore binária tal que cada nó \(r\) com subárvores esquerda \(T_e\) e direita \(T_d\) satisfaz:

• \(e<r, \forall\ e \in T_e\)

• \(d>r, \forall\ d \in T_d\)

é uma árvore binária de busca.

Figura 1: Exemplo de árvore binária de busca. Fonte: [1]

Propriedades

Uma árvore binária de busca satisfaz a seguinte propriedade:

A impressão dos elementos em um percurso em-ordem (esquerda-raiz-direita) gera uma lista ordenada.

No exemplo da Figura 1, o percurso em ordem gera a seguinte saída: 1, 3, 4, 5, 7, 8, 10, 12, 13, 14.

O percurso em ordem é feito da seguinte maneira:

// Em ordem visita os nós na ordem: esquerda, raiz, direita.
void in_ordem(p_no raiz)
{
    if (raiz != NULL)
    {
        in_ordem(raiz->esq);
        printf("%d ", raiz->dado);
        in_ordem(raiz->dir);
    }
}

A complexidade do algoritmo de percurso em ordem é \(O(n)\), onde \(n\) é a quantidade de nós de uma árvore, uma vez que o função é executada \(2\cdot n\) vezes.

Implementação

typedef struct No
{
    int chave;
    struct No *esq, *dir;
} No;

typedef No *p_no;

// Inicialização
p_no criar_arvore();
void destruir_arvore(p_no raiz);

p_no inserir(p_no raiz, int chave);
p_no remover(p_no raiz, int chave);
p_no buscar(p_no raiz, int chave);
p_no buscar_iterativo(p_no raiz, int chave);

p_no minimo(p_no raiz);
p_no maximo(p_no raiz);

p_no sucessor(p_no raiz);

p_no criar_arvore()
{
    p_no raiz = malloc(sizeof(No));
    return raiz;
}

// A destruição tem que ser feita
// das folhas para cima.
void destruir_arvore(p_no raiz)
{
    if (raiz != NULL)
    {
        if (raiz->esq != NULL)
            destruir_arvore(raiz->esq);
        if (raiz->dir != NULL)
            destruir_arvore(raiz->dir);
    }
    free(raiz);
}

Inserção e Remoção

Antes de fazer a inserção, devemos determinar onde inserir o valor, fazendo uma busca por ele. Então, inserimos ele na posição ele deveria estar.

O algoritmo insere na árvore recursivamente e devolve um ponteiro para a raiz da nova árvore.

p_no inserir(p_no raiz, int chave)
{

    if (raiz == NULL)
    {
        raiz = malloc(sizeof(No));
        raiz->chave = chave;
        raiz->esq = raiz->dir = NULL;
        return raiz;
    }
    if (chave < raiz->chave)
        raiz->esq = inserir(raiz->esq, chave);
    else
        raiz->dir = inserir(raiz->dir, chave);
    return raiz;
}

p_no remover_sucessor(p_no raiz)
{
    p_no min = raiz->dir;
    p_no pai = raiz;
    while (min->esq != NULL)
    {
        pai = min;
        min = min->esq;
    }
    if (pai->esq == min)
        pai->esq = min->dir;
    else
        pai->dir = min->dir;
    raiz->chave = min->chave;
}

p_no remover(p_no raiz, int chave)
{
    if (raiz != NULL)
    {
        if (chave < raiz->chave)
            raiz->esq = remover(raiz->esq, chave);
        else if (chave > raiz->chave)
            raiz->dir = remover(raiz->dir, chave);
        else if (raiz->esq == NULL)
            return raiz->dir;
        else if (raiz->dir == NULL)
            return raiz->esq;
        else
            remover_sucessor(raiz);
    }
    return raiz;
}

Busca

A ideia é semelhante à busca binária, ou o valor procurado está na raiz da árvore, ou é menor, ou é maior. Se for menor, estará na subárvore da esquerda, se for maior, na da direita.

p_no buscar(p_no raiz, int chave)
{
    if (raiz != NULL)
    {
        if (raiz->chave == chave)
            return raiz;
        if (raiz->chave > chave)
            return buscar(raiz->esq, chave);
        else
            return buscar(raiz->dir, chave);
    }
    return NULL;
}

p_no buscar_iterativo(p_no raiz, int chave)
{
    while (raiz != NULL && chave != raiz->chave)
        if (chave < raiz->chave)
            raiz = raiz->esq;
        else
            raiz = raiz->dir;
    return raiz;
}

A complexidade da busca em uma árvore de n níveis, se a árvore estiver balanceada, é \(O(log n)\), e no pior caso a árvore assemelha-se à uma lista encadeada, o que faz a busca ter complexidade \(O(n^2)\). Isso ocorre quando os dados estão ordenados, então um novo nó sempre será inserido do mesmo lado, esquerdo, caso decrescente, direito, quando crescente.

No caso médio, a árvore tende a ser balanceada, já que cada elemento inserido tem 50% de chance de estar à esquerda ou à direita da raiz.

Mínimo

Basta andar a árvore sempre à esquerda, até encontrar um nó que não tenha filhos a esquerda.

p_no minimo(p_no raiz)
{
    p_no minimo = raiz;
    while (minimo->esq != NULL)
        minimo = minimo->esq;
    return minimo;
}

p_no minimo_rec(p_no raiz)
{
    if (raiz == NULL || raiz->esq == NULL)
        return raiz;
    return minimo_rec(raiz->esq);
}

Máximo

Basta andar a árvore sempre à direita, até encontrar um nó que não tenha filhos a direita.

p_no maximo(p_no raiz)
{
    p_no maximo = raiz;
    while (maximo->dir != NULL)
        maximo = maximo->dir;
    return maximo;
}

p_no maximo_rec(p_no raiz)
{
    if (raiz == NULL || raiz->dir == NULL)
        return raiz;
    return maximo_rec(raiz->dir);
}

Sucessor

// Retorna o próximo nó na ordenação.
p_no sucessor(p_no raiz)
{
    if (raiz != NULL && raiz->dir != NULL)
        return minimo(raiz->dir);
    return NULL;
}

Referências

[1] Árvores Binárias de Busca - Notas de aula do professor Rafael C. S. Schouery, disponíveis no link.