Árvore binária de busca

Origem: Wikipédia, a enciclopédia livre.
(Redirecionado de Árvore de busca binária)
Á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
Algoritimo Caso Médio Pior Caso
Espaço O(n) O(n)
Busca O(log n) O(n)
Inserção O(log n) O(n)
Remoção O(log n) O(n)

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

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

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

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

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:

  1. T possui n nós. Cada nó u armazena uma chave distinta sj S e tem como rótulo o valor r(u) = sj.
  2. 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.

Elementos[editar | editar código-fonte]

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

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

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

Remoçã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

Remoção de 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

Remoção de 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.

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

Percursos em ABB[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
Á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[editar | editar código-fonte]

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

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


Obtida de "https://pt.wikipedia.org/w/index.php?title=Árvore_binária_de_busca&oldid=67412290"