Estrutura de dados 4 - Árvore binária

Fonte.

E encerrando a introdução — mas não o assunto, que é bem extenso e conta com vários aprofundamentos — a estrutura de dados com grande estilo, vamos falar sobre árvores binárias. Mais especificamente, árvores binárias de busca.


Índice - Estruturas de dados

1 - Lista encadeada
2 - Pilha
3 - Fila
4 - Árvore binária

Definição de árvore binária

Na computação, sempre que falamos em árvore, visualize um conjunto hierárquico de elementos. Na prática, temos uma árvore invertida: no topo dela há um nó que corresponde a raíz, e abaixo estão os demais nós das árvores — seus filhos. Uma árvore é binária quando cada nó possui no máximo dois filhos e cada filho tem um único pai:

Basicamente o que você precisa saber é o seguinte:

- Nó: Cada um dos elementos da árvore;
- Raiz: O topo da árvore;
- Filho esquerdo de um nó: O nó descendente à esquerda do nó considerado;
- Filho direito de um nó: O nó descendente à direita do nó considerado;
- Pai de um nó: O nó diretamente acima do nó considerado;
- Folha: Um nó sem filhos.

Como veremos a seguir, árvores binárias são muito úteis na elaboração de algoritmos eficientes de busca e inserção, bem como algoritmos de grafos de modo geral. O principal modo de observar esse poder em ação é analisando árvores de busca binária, então a partir de agora vamos nos aprofundar nesse tipo. Há mais coisas a saber sobre árvores binárias, mas por hora paramos aqui.

Definição de árvore binária de busca

Uma árvore binária de busca é uma árvore binária que obedece às duas seguintes propriedades:

Dado um nó qualquer, todo nó descendente direito é maior do que este nó;
Dado um nó qualquer, todo nó descendente esquerdo é maior do que este nó.

Mas como determinar esse maior e menor? Utilizamos um campo para comparações que geralmente chamamos "chave". Quando impomos essa restrição, torna-se bem rápido vasculhar pela árvore e inserir novas informações — daí o "busca". Para nossa implementação simples, veremos as seguintes operações:

- Inicializar árvore;
- Inserir um novo nó;
- Buscar um elemento na árvore;
- Imprimir o conteúdo da árvore;
- Verificar o tamanho da árvore.

Implementação de árvore binária de busca em C

Primeiro, vamos à inicialização:


typedef int tipoElem;


typedef struct no {
        tipoElem dado;
        struct no *esq;
        struct no *dir;
} No;


No * novoNo(tipoElem conteudo) {
     No *no = malloc(sizeof(No));
     no->dado = conteudo;
     no->esq = no->dir = NULL;
     return no;
}

Para simplificar as coisas, ao invés de inserirmos um campo chave além do campo dado, como faríamos em situações complexas, vamos considerar que o próprio dado serve como critério de comparação. Dito isso, o resto não parece deixar margens a dúvidas: cada nó possui um filho esquerdo e um filho direito, de modo que inicialmente esses ponteiros são nulos.

Agora vejamos como funciona o algoritmo de inserção:


No * inserir(No *arv, tipoElem elem) {
     if(arv == NULL)
            return novoNo(elem);
     else {
          if(elem <= arv->dado)
                  arv->esq = inserir(arv->esq, elem);
          else
              arv->dir = inserir(arv->dir, elem);
          
          return arv;
     }
}

De imediato surge algo estranho: uma função de inserção que retorna alguma coisa? Sim, pois isso facilita o raciocínio recursivo. Muitos algoritmos envolvendo árvores binárias de busca são recursivos por natureza, por ser o modo mais intuitivo de lidar com elas.

• Solução trivial: A árvore representada pelo nó é nula. Nesse caso, devolvemos um novo nó contendo o elemento passado como argumento.

• Recursão: Precisamos localizar a posição adequada do elemento na árvore. Se o dado for menor que o da raíz, vamos olhar na esquerda; se for maior, vamos olhar na direita. A recursão termina justamente quando o nó passado como argumento for nulo. Quando essa situação chegar, significa que já passamos por todos os nós e é aí onde precisamos colocar o novo nó.

Não surpreendentemente, o algoritmo de busca também é recursivo:


No * busca(No *arv, tipoElem alvo) {
    if(arv == NULL || arv->dado == alvo)
           return arv;
    else if(alvo > arv->dado)
         return busca(arv->dir, alvo);
    else
        return busca(arv->esq, alvo);
}

• Caso base: A árvore é nula ou o elemento alvo está na raiz. Se a árvore é nula, devolvemos nulo; se o elemento alvo está na raiz, devolvemos a raiz. Portanto, só precisamos devolver a árvore.

• Recursão: O elemento não está na raiz, mas é menor ou maior do que o dado na raiz? Se for maior, procuramos à direita; se for menor, procuramos à esquerda. A recursão termina quando encontrarmos o elemento em algum nó ou atravessarmos a árvore inteira e não conseguimos localizá-lo.

Impressão de uma árvore:


void imprimirArvore(No *raiz) {
     if(raiz != NULL) {
               imprimirArvore(raiz->esq);
               printf("%d\n", raiz->dado);
               imprimirArvore(raiz->dir);
     }
}

A ordem de impressão é do menor elemento ao maior. Em outras palavras, devemos percorrer a árvore pela esquerda e depois pela direita, como mostra a função. É um algoritmo simples, mas talvez um pouco difícil de visualizar. Sugiro então fazer alguns testes com uma árvore qualquer à respeito do comportamento da função. Por último, ficamos com o tamanho:


int tamanho(No *raiz) {
    if(raiz == NULL)
            return 0;
    else {
         return( 1 + tamanho(raiz->esq) + tamanho(raiz->dir) );
    }
}

• Caso base: A raiz passada como argumento é nulo. Nesse caso, o tamanho é zero.

• Recursão: Se a raiz não é nula, sabemos que o tamanho é pelo menos 1. A esse valor somamos o tamanho da sub-árvore à esquerda e o tamanho da sub-árvore à direita. Claro que cada sub-árvore terá uma raiz, então podemos aplicar o mesmo raciocínio recursivamente, até que a raiz seja nula.

Aplicações e exercícios de árvores

Árvores são a base para muitos algoritmos e estruturas de dados relacionados à manipulação de dados, como o heap (por consequência o heapsort) e a fila prioritária. Podemos utilizar árvores para resolver vários problemas relacionados a grafos, como o algoritmo de Dijkstra, que surgem em problemas de roteamento.

• Será que ele é?: Dada uma árvore binária, verifique se respeita as condições de uma árvore binária de busca.

• Pensamentos profundos: Dado um nó qualquer, verifique sua profundidade. A profundidade do nó x é a distância, ou seja, o número de nós, entre x e a raiz.

• Arrancando o mal pela raiz: Escreva uma função que remova a raiz de uma árvore binária de busca. Naturalmente, ela precisa continuar sendo uma árvore binária de busca após a remoção.

• Troca-troca: Dada uma árvore, faça uma função que troque a posição dos filhos de cada nó: o filho da esquerda torna-se o da direita, e vice-versa.

Fontes

Binary trees
Estruturas de dados: árvores binárias
Estruturas de dados: árvores de busca
Tree (data structure) - Wikipedia