Árvore binária de busca

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.

• 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

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.

Busca

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

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

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

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

Exclusão de um nó com um filho

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

Exclusão de um 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).

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

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

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_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 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

• Commons
• Wikilivros

• Árvore (estrutura de dados)
• Árvore AVL
• Árvore B
• Árvore binária
• Árvore Patricia
• Estrutura de dados
• Tabela de dispersão
• Trie

Ligações externas

• Instituto de Ciências Matemáticas de São Carlos (em português)
• An introduction to binary trees from Stanford (em inglês)
• Dicionário de Algoritmos e Estrutura de Dados - Capítulo de árvore binária de busca (em inglês)
• Exemplo de árvore binária de busca em Python (em inglês)