Árvore de busca binária

Origem: Wikipédia, a enciclopédia livre.

Representação de uma Árvore de busca binária

Em ciência da computação, a árvore de busca binária ou árvore de pesquisa binária é uma árvore binária onde todos os nós são valores, todo nó a esquerda contêm uma sub-árvore com os valores menores ao nó raiz da sub-árvore e todos os nós da sub-árvore a direita contêm somente valores maiores ao nó raiz. (Esta é a forma padrão, podendo ser invertida as sub-árvores dependendo da aplicação). Os valores são relevantes na árvore de busca binária. O objetivo desta árvore é estruturar os dados de forma flexível permitindo pesquisa binária. Segundo o livro Estruturas de Dados e seus Algoritmos - LTC - Cada nó tem um valor para cada campo chave diferente. Por tanto a figura ilustrativa está errada, o valor 7 não poderia estar repetido.

[editar] Busca

Para a busca em uma árvore binária por um valor específico começamos examinando a raiz. Se o valor for igual a raiz, o valor existe na árvore. Se o valor for menor do que a raiz, então deve buscar na sub-árvore da esquerda, e assim recursivamente em todos os nós da sub-árvore.

Similarmente, se o valor for maior do que a raiz, então deve buscar na sub-árvore da direita. Até alcançar o nó folha da árvore, encontrando ou não o valor requerido.

Abaixo um algoritmo de busca em linguagem Python:

def arvore_de_busca_binaria(nó_arvore, valor):
    if nó_arvore is None: return None  # falhou
    esquerda, nó_valor, direita = nó_arvore.esquerda, nó_arvore.valor, nó_arvore.direita

    if nó_valor > valor:
        return arvore_de_busca_binaria(esquerda, valor)
    elif valor > nó_valor:
        return arvore_de_busca_binaria(direita, valor)
    else:
        return nó_valor

Outra implementação em Linguagem de programação C:

int buscar(tArvore *a, int elem)
{
  if (a == NULL)
    return 0;
  else if (a->centro < elem)
    return buscar(a->hDireita, elem);
  else if (a->centro > elem)
    return buscar(a->hEsquerda, elem);
  else
    return 1;
}

Outra implementação em Perl:

sub binary_search {
  my ($array, $word) = @_;
  my ($low, $high) = ( 0, @$array - 1 );
  while ( $low <= $high ) {
    my $try = int( ($low+$high) /2 );
    $low = $try+1, next if $array->[$try] lt $word;
    $high = $try-1, next if $array->[$try] gt $word;
    return $try;
  }
  return;
}

Esta operação efetua O(log n) operações no caso médio e O(n) no pior caso, quando a árvore está desequilibrada, assemelhando-se a uma lista ligada. Neste caso, a árvore é considerada uma árvore degenerada.

[editar] Inserção

A inserção começa com uma busca; procurando pelo valor, mas se não for encontrado, procuraremos as sub-árvores da esquerda ou direita como na busca. Eventualmente, alcançaremos a folha, e então inserimos o valor nesta posição. Ou seja nós examinamos a raiz e introduzimos um nó novo na sub-árovore da esquerda se o valor novo é menor do que a raiz, ou na sub-árovore da direita se o valor novo for maior do que a raiz.

Abaixo um algoritmo de inserção em Python:

def arvore_binaria_de_insercao(nó_arvore, valor):
    if nó_arvore is None: return (None, valor, None)
    esquerda, nó_valor, direita = nó_arvore.esquerda, nó_arvore.valor, nó_arvore.direita

    if nó_valor > valor:
        return TreeNode(arvore_binaria_de_insercao(esquerda, valor), nó_valor, direita)
    else:
        return TreeNode(esquerda, nó_valor, arvore_binaria_de_insercao(direita, valor))

Outra implementação em Linguagem de programação C:

void inserir(tArvore **a, int elem)
{
  if (*a == NULL)
  {
    *a = (tArvore *) malloc(sizeof(tArvore));
    (*a)->centro = elem;
    (*a)->hEsquerda =  NULL;
    (*a)->hDireita = NULL;
  }
  else if ((*a)->centro < elem)
    inserir(&(*a)->hDireita, elem);
  else if ((*a)->centro > elem)
    inserir(&(*a)->hEsquerda, elem);
}

Esta operação requer O(log n) vezes para o caso médio e necessita de Omega(n) no pior caso.

Uma outra maneira de explicar a inserção é que a fim de introduzir um nó novo na árvore, seu valor é primeiro comparado com o valor da raiz. Se seu valor for menos do que a raiz, é comparado então com o valor do filho da esquerda da raiz. Se seu valor for maior, está comparado com o filho da direita da raiz. Este processo continua até que o nó novo esteja comparado com um nó da folha, e então adiciona-se o filho da direita ou esquerda, dependendo de seu valor.

[editar] Exclusã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:

Exclusão de folha: Excluindo uma folha é simples, somente remova-o da árvore.
Exclusão de um nó com um filho: Excluindo-o e o filho sobe para a posição do pai.
Exclusão de um nó com dois filhos: Aí pode-se operar de duas maneiras diferentes. Pode-se substituir o valor do nó a ser retirado pelo valor sucessor (o nó mais a esquerda da sub-árvore direita) ou pelo valor antecessor (o nó mais a direita da sub-árvore esquerda), e aí remove-se o nó sucessor (ou antecessor).

No exemplo acima, o nó de valor 7 está para ser removido, e possui como antecessor imediato o valor 6 e como sucessor imediato o valor 9. Assim sendo, na exclusão, qualquer um dos dois valores pode substituir o valor do nó a ser removido, como pode ser visto na figura.

Ao excluir um nó, ou mesmo ao incluir um nó, pode haver o desbalanceamento da árvore, sendo corrigido, por exemplo, com o balanceamento AVL.

Exemplo de algoritmo de exclusão em Python:

def exclusao_em _arvore_binaria(nó_arvore, valor):
    if nó_arvore is None: return None # Valor não encontrado
    esquerda, nó_valor, direita = nó_arvore.esquerda, nó_arvore.valor, nó_arvore.direita
    if nó_valor == valor:
        if esquerda is None: 
            return direita
        elif direita is None: 
            return esquerda
        else:
            valor_max, novo_esquerda = busca_max(esquerda)
            return TreeNode(novo_esquerda, valor_max, direita)
    elif valor < nó_valor:
        return TreeNode(exclusao_em _arvore_binaria(esquerda, valor), nó_valor, direita)
    else:
        return TreeNode(esquerda, nó_valor, exclusao_em _arvore_binaria(direita, valor))

def busca_max(nó_arvore):
    esquerda, nó_valor, direita = nó_arvore.esquerda, nó_arvore.valor, nó_arvore.direita
    if direita is None: return (nó_valor, esquerda)
    else:
        (valor_max, novo_direita) = busca_max(direita)
        return (valor_max, (esquerda, nó_valor, novo_direita))

Outra implementação em Linguagem de programação C:

void excluir(tArvore **a, int elem)
{
  void rebuscar(tArvore **a, tArvore **aux);
  tArvore *aux;

  if (*a == NULL)
    return;

  if ((*a)->centro < elem)
    excluir(&(*a)->hDireita, elem);
  else if ((*a)->centro > elem)
    excluir(&(*a)->hEsquerda, elem);
  else if ((*a)->centro == elem)
  {
    aux = *a;
    if ((*a)->hEsquerda == NULL)
      *a = (*a)->hDireita;
    else if ((*a)->hDireita == NULL)
      *a = (*a)->hEsquerda;
    else
      rebuscar(&(*a)->hEsquerda, &aux);

    free(aux);
  }
}

void rebuscar(tArvore **a, tArvore **aux)
{
  if ((*a)->hDireita == NULL)
  {
    (*aux)->centro = (*a)->centro;
    *aux = *a;
  }
  else
    rebuscar(&(*a)->hDireita, aux);
}

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

[editar] Transversal

Algoritmo de busca transversal.

def arvore_binaria_transversal(nó_arvore):
    if nó_arvore is None: return
    esquerda, nó_valor, direita = nó_arvore
    arvore_binaria_transversal(esquerda)
    visite(nó_valor)
    arvore_binaria_transversal(direita)

Árvore tranversal requer O(n) vezes, desde que visitando cada nó.

[editar] Percurso

Em uma árvore binária de busca pode-se fazer os três percursos que faz para uma árvore binária qualquer (percursos em inordem, preordem e posordem). Uma característica interessante é quando se faz um percurso em ordem em uma árvore binária de busca. Ao efetuar esse percurso, os valores dos nós aparecem em ordem crescente.

A operação "Percorre"

Objetivo. Percorrer a árvore numa dada ordem enumerando os seus nós. Quando um nó é enumerado, dizemos que ele foi "visitado".

Recursão: Caso trivial: Percorrer uma árvore vazia: nada é feito.

Caso mais simples que o problema original:

Pré-ordem (ou profundidade):

  1. Visita a raiz;
  2. Percorre a sub-árvore esquerda em pré-ordem;
  3. Percorre a sub-árvore direita em pré-ordem.

Ordem Simétrica:

  1. Percorre a sub-árvore esquerda em ordem simétrica;
  2. Visita a raiz;
  3. Percorre a sub-árvore direita em ordem simétrica.

Pos-ordem:

  1. Percorre a sub-árvore esquerda em pos-ordem;
  2. Percorre a sub-árvore direita em pos-ordem;
  3. Visita a raiz.

[editar] Ordenação

Uma árvore de busca binária pode ser usada para executar um simples algoritmo de ordenação. Para fazer isto, é introduzido todos os valores desejados e depois é classificado em uma árvore de busca binária, atravessando-a em ordem, construindo um novo resultado:

def criar_arvore_binaria(valor):
    arvore = None
    for v in valor:
        arvore = arvore_binaria_de_insercao(arvore, v)
    return arvore

def arvore_binaria_transversa(nó_arvore):
    if nó_arvore is None: return []
    else:
        esquerda, valor, direita = nó_arvore
        return (arvore_binaria_transversal(esquerda) + [valor] + arvore_binaria_transversal(direita))

No pior caso criar_arvore_binaria é O(n²) se você lhe alimentar uma lista ordenada de valores, isto é semelhante a uma lista ligada . Para o exemplo, o criar_arvore_binaria([ 1, 2, 3, 4, 5]) rende a árvore (None, 1, (None, 2, (None, 3, (None, 4 (None, 5, None))))).