Árvore binária de busca

	Outros projetos Wikimedia também contêm material sobre este tema:
<img alt="Wikilivros" src="//upload.wikimedia.org/wikipedia/commons/thumb/f/fa/Wikibooks-logo.svg/21px-Wikibooks-logo.svg.png" decoding="async" width="21" height="21" class="mw-file-element" data-file-width="300" data-file-height="300">	Livros e manuais no Wikilivros
<img alt="Commons" src="//upload.wikimedia.org/wikipedia/commons/thumb/4/4a/Commons-logo.svg/21px-Commons-logo.svg.png" decoding="async" width="21" height="28" class="mw-file-element" data-file-width="1024" data-file-height="1376">	Imagens e media no Commons

Árvore binária de busca
Tipo	Árvore
Ano	1960
Inventado por	P.F. Windley, A.D. Booth, A.J.T. Colin, e T.N. Hibbard
Complexidade de Tempo em Notação big O

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 permitir busca binária.^[1]

Conceitos básicos

Árvore binária de busca de cardinalidade 9 e altura 4, com raiz 8 e folhas 1, 4, 7 e 13

Definição^[2]

Seja S = {s₁, s₂, ..., s_n} um conjunto de chaves tais que s₁ < s₂ ... s_n. Seja k um valor dados. Deseja-se verificar se k $\in$ S e identificar o índice i tal que k = s_i.

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

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

T possui n nós. Cada nó u armazena uma chave distinta s_j $\in$ S e tem como rótulo o valor r(u) = s_j.
Para cada nó v de T r(v₁) < r(v) e r(v₂) > r(v), onde v₁ pertence à subárvore esquerda de v e v₂ pertence à subárvore direita de v.

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

Elementos

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)

Complexidade^[3]

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^[3]

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

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 poderá ser O(log n) em algumas situações, mas necessita O(n) de tempo no pior caso, quando a árvore assumir a forma de lista ligada (árvore ziig-zag).^[2]

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

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.

Remoção de nó com um filho

Excluindo-o, o filho sobe para a posição do 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).

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.

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.

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

Árvore Binária de Busca

Usando a ABB acima, os resultados serão os seguintes:

Pré-ordem => 8, 3, 1, 6, 4, 7, 10, 14, 13

Ordem simétrica => 1, 3, 4, 6, 7, 8, 10, 13, 14 (chaves ordenadas)

Pós-ordem => 1, 4, 7, 6, 3, 13, 14, 10, 8

Ordenação

Uma árvore binária de busca pode ser usada para ordenação de chaves. Para fazer isto, basta inserir todos os valores desejados na ABB e executar o percurso em ordem simétrica.

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

Criar ABB tem complexidade O(n²) no pior caso. A geração de um vetor de chaves ordenadas tem complexidade O(n). O algoritmo de ordenação terá complexidade final O(n²) no pior caso.

Cabe observar que há algoritmos de ordenação dedicados com complexidade O(n.log n), com desempenho superior ao proposto neste tópico.

Ver também

Referências

↑ Gilberg, R.; Forouzan, B. (2001). «8». Data Structures: A Pseudocode Approach With C++ (em inglês). Pacific Grove, CA: Brooks/Cole. p. 339. ISBN 0-534-95216-X
↑ ^a ^b Swarcfiter, Jayme Luiz (1994). Estruturas de Dados e seus Algoritmos. Rio de Janeiro: LTC. pp. 91–97
↑ ^a ^b Cormen, Thomas H.; et al. (2009). Introduction to Algorithms. Massachusetts: MIT Press. pp. 286–307

Ligações externas

«An introduction to binary trees from Stanford» (em inglês)
«Árvores Binárias de Busca (IME/USP)»
«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)

[1] Gilberg, R.; Forouzan, B. (2001). «8». Data Structures: A Pseudocode Approach With C++ (em inglês). Pacific Grove, CA: Brooks/Cole. p. 339. ISBN 0-534-95216-X

[:0-2] Swarcfiter, Jayme Luiz (1994). Estruturas de Dados e seus Algoritmos. Rio de Janeiro: LTC. pp. 91–97

[:1-3] Cormen, Thomas H.; et al. (2009). Introduction to Algorithms. Massachusetts: MIT Press. pp. 286–307

[1]

[2]

[3]

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