Árvore binária de busca

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
NoFonti.svg
Este artigo ou se(c)ção cita fontes fiáveis e independentes, mas que não cobrem todo o conteúdo. Por favor, adicione mais referências e insira-as corretamente no texto ou no rodapé. Trechos sem fontes poderão ser removidos.
Encontre fontes: Googlenotícias, livros, acadêmicoYahoo!Bing.
Uma árvore binária de busca de tamanho 9 e profundidade 3, com raiz 8 e folhas 1, 4, 7 e 13.

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 flexível, permitindo busca binária.[1]

  • Nós - são todos os itens guardados na árvore
  • Raiz - é o nó do topo da árvore (no caso da figura acima, a raiz é o nó 8)
  • Filhos - são os nós que vem depois dos outros nós (no caso da figura acima, o nó 6 é filho do 3)
  • Pais - são os nós que vem antes dos outros nós (no caso da figura acima, o nó 10 é pai do 14)
  • Folhas - são os nós que não têm filhos; são os últimos nós da árvore (no caso da figura acima, as folhas são 1, 4, 7 e 13)

Operações[editar | editar código-fonte]

Operações em uma árvore binária requerem comparações entre nós. Essas comparações são feitas com chamadas a um comparador, que é uma subrotina que calcula a ordem total (ordem linear) em dois valores quaisquer. Esse comparador pode ser explícita ou implicitamente definido, dependendo da linguagem em que a árvore binária de busca está implementada.[2]

Busca[editar | editar código-fonte]

Buscando um valor na árvore binária.

A busca em uma árvore binária por um valor específico pode ser um processo recursivo ou iterativo. Essa explicação usará 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.[2] Segue abaixo o algoritmo de busca implementado na linguagem Python:

# 'no' refere-se ao nó-pai, neste caso
def arvore_binaria_buscar(no, valor):
    if no is None:
        # valor não encontrado
        return None
    else:
        if valor == no.valor:
            # valor encontrado
            return no.valor
        elif valor < no.valor:
            # busca na subárvore esquerda
            return arvore_binaria_buscar(no.filho_esquerdo, valor)
        elif valor > no.valor:
            # busca na subárvore direita
            return arvore_binaria_buscar(no.filho_direito, valor)

Essa operação requer O(log n) de tempo nos casos comuns, mas necessita O(n) de tempo no pior caso, quando a árvore desequilibrada assemelha-se a uma lista ligada (árvore degenerada).

Inserção[editar | editar código-fonte]

A inserção começa com uma busca, procurando pelo valor, mas se não for encontrado, procuram-se as subárvores da esquerda ou direita, como na busca. Eventualmente, alcança-se a folha, inserindo-se então o valor nesta posição. Ou seja, a raiz é examinada e 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.[2] Abaixo, um algoritmo de inserção em Python:

def arvore_binaria_inserir(no, chave, valor):
    if no is None:
        return TreeNode(None, chave, valor, None)
    if chave == no.chave:
        return TreeNode(no.filho_esquerdo, chave, valor, no.filho_direito)
    if chave < no.chave:
        return TreeNode(arvore_binaria_inserir(no.filho_esquerdo, chave, valor), no.chave, no.valor, no.filho_direito)
    else:
        return TreeNode(no.filho_esquerdo, no.chave, no.valor, arvore_binaria_inserir(no.filho_direito, chave, valor))

Esta operação requer O (log n) vezes para o caso médio e necessita de Ômega (n) no pior caso. A fim de introduzir um nó novo na árvore, seu valor é primeiro comparado com o valor da raiz. Se seu valor for menor 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.

Exclusão[editar | editar código-fonte]

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 na folha[editar | editar código-fonte]

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

Excluindo o nó folha de valor 40.

Exclusão de um nó com um filho[editar | editar código-fonte]

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

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

Exclusão de um nó com dois filhos[editar | editar código-fonte]

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).

Exluindo 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. Ao excluir, ou mesmo ao incluir, um nó, pode haver o desbalanceamento da árvore, que pode ser 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))

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.

Transversal[editar | editar código-fonte]

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):

  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

Pós-ordem:

  1. Percorre a subárvore esquerda em pós-ordem
  2. Percorre a subárvore direita em pós-ordem
  3. Visita a raiz

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 se visite cada nó.

Ordenação[editar | editar código-fonte]

Uma árvore binária de busca pode ser usada para executar um simples algoritmo de ordenação. Para fazer isto, são introduzidos todos os valores desejados, classificado-se depois em uma árvore binária de busca, 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_transversal(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 lhe alimentar uma lista ordenada de valores, de forma 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))))).

Ver também[editar | editar código-fonte]

Outros projetos Wikimedia também contêm material sobre este tema:
Wikilivros Livros e manuais no Wikilivros
Commons Imagens e media no Commons

Referências

  1. Gilberg, R.; Forouzan, B.. Data Structures: A Pseudocode Approach With C++ (em inglês). Pacific Grove, CA: Brooks/Cole, 2001. Capítulo: 8. p. 339. ISBN 0-534-95216-X
  2. a b c Binary search trees (em inglês). Visitado em 12 de maio de 2010.

Ligações externas[editar | editar código-fonte]