Estruturas de dados: árvore binária

1. Introdução às Árvores Binárias

Uma árvore binária é uma estrutura de dados hierárquica composta por nós, onde cada nó possui no máximo dois filhos: esquerdo e direito. Essa estrutura é fundamental na computação por sua eficiência em operações de busca, inserção e remoção.

Terminologia básica:
- Nó raiz: o nó no topo da árvore, sem pai
- Nó folha: nó sem filhos (ambos os ponteiros nulos)
- Altura: número máximo de arestas da raiz até a folha mais distante
- Profundidade: número de arestas da raiz até um nó específico

Propriedades:
- Grau: número de filhos de um nó (0, 1 ou 2)
- Árvore estritamente binária: cada nó tem 0 ou 2 filhos
- Árvore completa: todos os níveis estão preenchidos, exceto possivelmente o último
- Árvore cheia: todos os nós folha estão no mesmo nível

Aplicações práticas:
- Expressões aritméticas (árvores de expressão)
- Codificação de Huffman para compressão
- Árvores binárias de busca (BST) para indexação
- Representação de hierarquias (sistemas de arquivos, menus)

2. Representação em C

A representação clássica utiliza uma estrutura com dado e dois ponteiros:

typedef struct No {
    int dado;
    struct No* esquerda;
    struct No* direita;
} No;

Funções auxiliares para criação e liberação:

No* criaNo(int valor) {
    No* novo = (No*)malloc(sizeof(No));
    if (novo == NULL) {
        printf("Erro de alocacao!\n");
        exit(1);
    }
    novo->dado = valor;
    novo->esquerda = NULL;
    novo->direita = NULL;
    return novo;
}

void liberaArvore(No* raiz) {
    if (raiz == NULL) return;
    liberaArvore(raiz->esquerda);
    liberaArvore(raiz->direita);
    free(raiz);
}

3. Percursos em Árvores Binárias

Os percursos definem a ordem de visitação dos nós. Implementações recursivas:

void preOrdem(No* raiz) {
    if (raiz == NULL) return;
    printf("%d ", raiz->dado);
    preOrdem(raiz->esquerda);
    preOrdem(raiz->direita);
}

void emOrdem(No* raiz) {
    if (raiz == NULL) return;
    emOrdem(raiz->esquerda);
    printf("%d ", raiz->dado);
    emOrdem(raiz->direita);
}

void posOrdem(No* raiz) {
    if (raiz == NULL) return;
    posOrdem(raiz->esquerda);
    posOrdem(raiz->direita);
    printf("%d ", raiz->dado);
}

Exemplo de saída para a árvore com raiz 10, filho esquerdo 5 e direito 15:
- Pré-ordem: 10 5 15
- Em ordem: 5 10 15
- Pós-ordem: 5 15 10

4. Operações Básicas de Inserção

Para árvores binárias de busca (BST), a inserção segue o critério de ordenação: valores menores vão para a esquerda, maiores para a direita.

No* inserir(No* raiz, int valor) {
    if (raiz == NULL) {
        return criaNo(valor);
    }

    if (valor < raiz->dado) {
        raiz->esquerda = inserir(raiz->esquerda, valor);
    } else if (valor > raiz->dado) {
        raiz->direita = inserir(raiz->direita, valor);
    } else {
        printf("Valor %d ja existe na arvore.\n", valor);
    }

    return raiz;
}

Tratamento de duplicatas: a implementação acima ignora valores repetidos. Em aplicações que permitem duplicatas, pode-se armazenar contadores ou inserir sempre à esquerda.

5. Operações de Busca e Remoção

Busca recursiva:

No* buscar(No* raiz, int valor) {
    if (raiz == NULL || raiz->dado == valor) {
        return raiz;
    }

    if (valor < raiz->dado) {
        return buscar(raiz->esquerda, valor);
    } else {
        return buscar(raiz->direita, valor);
    }
}

Remoção — o caso mais complexo. Três cenários:

No* encontrarMinimo(No* raiz) {
    while (raiz->esquerda != NULL) {
        raiz = raiz->esquerda;
    }
    return raiz;
}

No* remover(No* raiz, int valor) {
    if (raiz == NULL) return NULL;

    if (valor < raiz->dado) {
        raiz->esquerda = remover(raiz->esquerda, valor);
    } else if (valor > raiz->dado) {
        raiz->direita = remover(raiz->direita, valor);
    } else {
        // Caso 1: nó folha
        if (raiz->esquerda == NULL && raiz->direita == NULL) {
            free(raiz);
            return NULL;
        }
        // Caso 2: um filho
        else if (raiz->esquerda == NULL) {
            No* temp = raiz->direita;
            free(raiz);
            return temp;
        } else if (raiz->direita == NULL) {
            No* temp = raiz->esquerda;
            free(raiz);
            return temp;
        }
        // Caso 3: dois filhos
        else {
            No* sucessor = encontrarMinimo(raiz->direita);
            raiz->dado = sucessor->dado;
            raiz->direita = remover(raiz->direita, sucessor->dado);
        }
    }
    return raiz;
}

6. Altura e Balanceamento

Cálculo recursivo da altura:

int altura(No* raiz) {
    if (raiz == NULL) return -1;
    int altEsq = altura(raiz->esquerda);
    int altDir = altura(raiz->direita);
    return (altEsq > altDir ? altEsq : altDir) + 1;
}

Fator de balanceamento (diferença entre altura da subárvore esquerda e direita):
- Valor entre -1 e 1: árvore balanceada
- Fora desse intervalo: necessidade de rotações

Árvores AVL são BSTs auto-balanceadas que mantêm o fator de balanceamento em cada nó, realizando rotações (simples ou duplas) após inserções e remoções para garantir altura O(log n).

7. Exemplo Completo em C

#include <stdio.h>
#include <stdlib.h>

typedef struct No {
    int dado;
    struct No* esquerda;
    struct No* direita;
} No;

No* criaNo(int valor) {
    No* novo = (No*)malloc(sizeof(No));
    novo->dado = valor;
    novo->esquerda = NULL;
    novo->direita = NULL;
    return novo;
}

No* inserir(No* raiz, int valor) {
    if (raiz == NULL) return criaNo(valor);
    if (valor < raiz->dado)
        raiz->esquerda = inserir(raiz->esquerda, valor);
    else if (valor > raiz->dado)
        raiz->direita = inserir(raiz->direita, valor);
    return raiz;
}

void emOrdem(No* raiz) {
    if (raiz == NULL) return;
    emOrdem(raiz->esquerda);
    printf("%d ", raiz->dado);
    emOrdem(raiz->direita);
}

void liberaArvore(No* raiz) {
    if (raiz == NULL) return;
    liberaArvore(raiz->esquerda);
    liberaArvore(raiz->direita);
    free(raiz);
}

int main() {
    No* raiz = NULL;
    int valores[] = {50, 30, 70, 20, 40, 60, 80};
    int n = sizeof(valores) / sizeof(valores[0]);

    for (int i = 0; i < n; i++) {
        raiz = inserir(raiz, valores[i]);
    }

    printf("Percurso em ordem: ");
    emOrdem(raiz);
    printf("\n");

    printf("Altura da arvore: %d\n", altura(raiz));

    liberaArvore(raiz);
    return 0;
}

8. Considerações Finais

Complexidade temporal das operações em BST:
- Melhor caso (árvore balanceada): O(log n) para busca, inserção e remoção
- Pior caso (árvore degenerada): O(n) — equivalente a uma lista encadeada
- Caso médio: O(log n) para inserções aleatórias

Comparação com outras estruturas:
- Listas encadeadas: O(n) para busca, O(1) para inserção no início
- Arrays ordenados: O(log n) para busca binária, O(n) para inserção/remoção
- BST: boa alternativa para operações dinâmicas de busca

Próximos passos recomendados:
1. Implementar árvores AVL para garantir balanceamento
2. Estudar árvores rubro-negras (Red-Black Trees)
3. Explorar árvores B para bancos de dados
4. Comparar com tabelas hash para busca por chave exata

O domínio de árvores binárias é essencial para qualquer programador C que deseje construir sistemas eficientes de manipulação de dados hierárquicos.

Referências