Programar em C/Árvores binárias de Busca

Em Ciência da computação, uma árvore binária de busca (ou árvore binária de pesquisa) é uma estrutura de dados de árvore binária baseada em nós, onde todos os nós da subárvore esquerda possuem um valor numérico inferior ao nó raiz e todos os nós da subárvore direita possuem um valor superior ao nó raiz (esta é a forma padrão, podendo as subárvores serem invertidas, dependendo da aplicação).

O objetivo desta árvore é estruturar os dados de forma a pesquisa binária.

Conceitos Básicos

Definição

Seja S = {s1, s2, ..., sn} um conjunto de chaves tais que s1 < s2 ... sn. Seja k um valor dados. Deseja-se verificar se k {\displaystyle \in } \in S e identificar o índice i tal que k = si.

A Árvore Binária de Busca (ABB) resolve os problemas propostos.

Uma ABB é uma árvore binária rotulada T com as seguintes propriedades:

• T possui n nós. Cada nó u armazena uma chave distinta sj {\displaystyle \in } \in S e tem como rótulo o valor r(u) = sj.
• Para cada nó v de T r(v1) < r(v) e r(v2) > r(v), onde v1 pertence à subárvore esquerda de v e v2 pertence à subárvore direita de v.

Dado o conjunto S com mais de um elemento, existem várias ABB que resolvem o problema.

//Demonstração |Parte do código em Linguagem C - Verificando se a arvore binária está ordenada

int contarNos(Arvore *a){
   if(a == NULL)
        return 0;
   else
        return 1 + contarNos(a->esq) + contarNos(a->dir);
}

int Verificar_Ordem(Arvore *a){
      int vetor_ordenacao[contarNos(a)];
      if(a != NULL){
            Verificar_Ordem(a->esq);
            vetor_ordenacao[i]=a->info;
            i++;

            Verificar_Ordem(a->dir);
      }

      for(i=0;i<=(contarNos(a));i++)
      {
            if(vetor_ordenacao[i]<=vetor_ordenacao[i+1])
                  continue;
            else
                  return 1;
      }
      return 0;
}

Elementos

• Nós - são todos os itens guardados na árvore
• Raiz - é o nó do topo da árvore.
• Filhos - são os nós que vem depois dos outros nós.
• Folhas - são os nós que não têm filhos; são os últimos nós da árvore.

Complexidade

A complexidade das operações sobre ABB depende diretamente da altura da árvore. Uma árvore binária de busca com chaves aleatórias uniformemente distribuídas tem altura O(log n). No pior caso, uma ABB poderá ter altura O(n). Neste caso a árvore é chamada de árvore zig-zag e corresponde a uma degeneração da árvore em lista encadeada. Em função da observação anterior, a árvore binária de busca é de pouca utilidade para ser aplicada em problemas de busca em geral. Daí o interesse em árvores balanceadas, cuja altura seja O(log n) no pior caso

Operações

Busca

A busca em uma árvore binária por um valor específico pode ser um processo recursivo ou iterativo. Será apresentado um método recursivo.

A busca começa examinando o nó raiz. Se a árvore está vazia, o valor procurado não pode existir na árvore. Caso contrário, se o valor é igual a raiz, a busca foi bem sucedida. Se o valor é menor do que a raiz, a busca segue pela subárvore esquerda. Similarmente, se o valor é maior do que a raiz, a busca segue pela subárvore direita. Esse processo é repetido até o valor ser encontrado ou a subárvore ser nula (vazia). Se o valor não for encontrado até a busca chegar na subárvore nula, então o valor não deve estar presente na árvore.

Desta forma se consegue utilizar a vantagem da arvore binária estar ordenada.

//funcao que localiza um determinado noh na arvore ordenada - Arvore de busca

int buscar_ordenada(Arvore *a, int num)
{
      int direita, esquerda;
      if(a==NULL)
            return 0;
      if(a->info==num) //Localizou o noh
      {
            return 1;
      }
      if(num<a->info) //Percorre pela esquerda, caso o numero seja menor do que a raiz
      {
            esquerda=buscar_ordenada(a->esq,num);
      }
      else
      {
            direita=buscar_ordenada(a->dir,num);
      }
      return esquerda+direita;
      }

Inserção

A busca do local a ser inserido o novo nó se inicia examinando a raiz. Se a árvore está vazia, é inserido o nó. Caso contrário, se o valor é menor do que a raiz, a percurso segue pela sub-árvore a esquerda. Introduz-se um nó novo na subárvore da esquerda se o valor novo for menor do que a raiz, ou na subárvore da direita se o valor novo for maior do que a raiz.

Arvore * inserir_noh(Arvore *a, int num)
{
      if(a==NULL) //Se não houver nó
      {
            a = (Arvore *) malloc(sizeof(Arvore)); //cria
            a->info=num; //Insere o valor
            a->esq=NULL; //Cria filho esquerdo
            a->dir=NULL; //Cria filho direito
      }
      else if(num<a->info) //Se o numero for menor do que a raiz, percorre a esquerda.
      {
            a->esq = inserir_noh(a->esq,num);
      }
      else
      {
            a->dir = inserir_noh(a->dir,num);
      }
      return a;
}

Remoção

A exclusão de um nó é um processo mais complexo. Para excluir um nó de uma árvore binária de busca, há de se considerar três casos distintos para a exclusão:

Remoção na folha

A exclusão na folha é a mais simples, basta removê-lo da árvore.

Excluindo o nó folha de valor 40.

Remoção de nó com um filho

Excluindo-o, o filho sobe para a posição do pai.

Exclusão do nó pai,: o filho sobe para pai.

Remoção de nó com dois filhos

Neste caso, pode-se operar de duas maneiras diferentes. Pode-se substituir o valor do nó a ser retirado pelo valor sucessor (o nó mais à esquerda da subárvore direita) ou pelo valor antecessor (o nó mais à direita da subárvore esquerda), removendo-se aí o nó sucessor (ou antecessor).

Excluindo um nó do lado direito.

No exemplo acima, o nó de valor 30 está para ser removido, e possui como sucessor imediato o valor 35 (nó mais à esquerda da sua sub-árvore direita). Assim sendo, na exclusão, o valor 35 será promovido no lugar do nó a ser excluído, enquanto a sua sub-árvore (direita) será promovida para sub-árvore esquerda do 40, como pode ser visto na figura.

Embora esta operação não percorra sempre a árvore até uma folha, esta é sempre uma possibilidade; assim, no pior caso, requer o tempo proporcional à altura da árvore, visitando-se cada nó somente uma única vez.

Aplicações

Percursos em ABB

Em uma árvore binária de busca podem-se fazer os três percursos que se fazem para qualquer árvore binária (percursos em inordem, pré-ordem e pós-ordem). É interessante notar que, quando se faz um percurso em ordem em uma árvore binária de busca, os valores dos nós aparecem em ordem crescente. A operação "Percorre" tem como objetivo percorrer a árvore numa dada ordem, enumerando os seus nós. Quando um nó é enumerado, diz-se que ele foi "visitado".

Pré-ordem (ou profundidade): Visita a raiz Percorre a subárvore esquerda em pré-ordem Percorre a subárvore direita em pré-ordem

Ordem Simétrica: Percorre a subárvore esquerda em ordem simétrica Visita a raiz Percorre a subárvore direita em ordem simétrica

Pós-ordem: Percorre a subárvore esquerda em pós-ordem Percorre a subárvore direita em pós-ordem Visita a raiz

Ver Também

• Árvore Binária
• Árvore AVL
• Árvore B
• Árvore Geral

Ligações externas

• Árvores Binárias de Busca (IME/USP)
• Dicionário de Algoritmos e Estrutura de Dados - Capítulo de árvore binária de busca