Árvore de pesquisa binária (BST) com exemplo

O que é uma árvore de pesquisa binária?

A Árvore Binária de Busca (BST, na sigla em inglês) é um algoritmo avançado usado para analisar um nó, seus ramos esquerdo e direito, modelados em uma estrutura de árvore, e retornar o valor. A BST é baseada na arquitetura de um algoritmo básico de busca binária; portanto, permite buscas, inserções e remoções de nós mais rápidas. Isso torna o programa realmente rápido e preciso.

Atributos da árvore de pesquisa binária

Um BST é feito de vários nós e consiste nos seguintes atributos:

• Os nós da árvore são representados em uma relação pai-filho.
• Cada nó pai pode ter zero nós filhos ou no máximo dois subnós ou subárvores nos lados esquerdo e direito.
• Cada subárvore, também conhecida como árvore de pesquisa binária, possui subramos à direita e à esquerda de si mesma.
• Todos os nós estão vinculados a pares de valores-chave.
• As chaves dos nós presentes na subárvore esquerda são menores que as chaves de seu nó pai.
• Da mesma forma, as chaves dos nós presentes na subárvore direita são maiores que as chaves de seu nó pai.

1. Existe o nó principal ou nível pai 11. Abaixo dele, existem nós/ramos esquerdos e direitos com seus próprios valores-chave.
2. A subárvore direita possui valores-chave maiores que o nó pai.
3. A subárvore esquerda possui valores-chave menores que o nó pai.

Por que precisamos de uma árvore de pesquisa binária?

• Os dois principais fatores que fazem de uma árvore de busca binária uma solução ideal para qualquer problema do mundo real são a velocidade e a precisão.
• Devido ao fato da busca binária estar em formato de ramificação com relações pai-filho, o algoritmo sabe em qual local da árvore os elementos precisam ser pesquisados. Isso diminui o número de comparações de valores-chave que o programa precisa fazer para localizar o elemento desejado.
• Além disso, caso o elemento a ser pesquisado seja maior ou menor que o nó pai, o nó sabe em qual lado da árvore pesquisar. Isso ocorre porque a subárvore esquerda é sempre menor que o nó pai, e a subárvore direita tem valores sempre iguais ou maiores que o nó pai.
• O BST é comumente utilizado para implementar pesquisas complexas, lógicas de jogo robustas, atividades de preenchimento automático e gráficos.
• O algoritmo oferece suporte eficiente a operações como pesquisar, inserir e excluir.

Tipos de árvores binárias

Três tipos de árvores binárias são:

• Árvore binária completa: Todos os níveis da árvore estão preenchidos, com uma possível exceção no último nível. Da mesma forma, todos os nós estão preenchidos, apontando para a extrema esquerda.
• Árvore binária completa: Todos os nós têm 2 nós filhos, exceto a folha.
• Árvore binária balanceada ou perfeita: Na árvore, todos os nós têm dois filhos. Além disso, cada subnó possui o mesmo nível.

Saiba mais sobre o Árvore binária na estrutura de dados se você estiver interessado.

Como funciona a árvore de pesquisa binária?

A árvore sempre tem um nó raiz e outros nós filhos, à esquerda ou à direita. O algoritmo executa todas as operações comparando os valores com a raiz e seus outros nós filhos na subárvore esquerda ou direita, respectivamente.

Dependendo do elemento a ser inserido, pesquisado ou excluído, após a comparação, o algoritmo pode facilmente descartar a subárvore esquerda ou direita do nó raiz.

O BST oferece principalmente os três tipos de operações a seguir para seu uso:

• Pesquisa: Busca o elemento na árvore binária.
• Inserção: Adiciona um elemento à árvore binária.
• Excluir: Remove o elemento de uma árvore binária.

Cada operação possui sua própria estrutura e método de execução/análise, mas a mais complexa de todas é a operação Delete.

Pesquisar Operação

A análise da árvore deve sempre começar pelo nó raiz e, em seguida, prosseguir para a subárvore direita ou esquerda do nó raiz, dependendo se o elemento a ser localizado é menor ou maior que a raiz.

1. O elemento a ser pesquisado é o 10.
2. Compare o elemento com o nó raiz 12, 10 < 12, portanto você se move para a subárvore esquerda. Não há necessidade de analisar a subárvore direita.
3. Agora compare o nó 10 com o nó 7; 10 > 7, então mova-se para a subárvore direita.
4. Em seguida, compare 10 com o próximo nó, que é 9; se 10 > 9, procure no filho da subárvore direita.
5. 10 corresponde ao valor no nó, 10 = 10, retorna o valor ao usuário.

Apelido Code para pesquisar em BST

search(element, root)
    if !root
        return -1
    if root.value == element
        return 1
    if root.value < element
        search(element, root.right)
    else
        search(element, root.left)

inserção Operação

Esta é uma operação muito simples. Primeiro, o nó raiz é inserido e, em seguida, o próximo valor é comparado com o nó raiz. Se o valor for maior que o da raiz, ele é adicionado à subárvore direita; se for menor, é adicionado à subárvore esquerda.

1. Existe uma lista de 6 elementos que precisam ser inseridos em uma BST (Árvore Binária de Busca) na ordem da esquerda para a direita.
2. Insira 12 como nó raiz e compare os valores seguintes, 7 e 9, para inseri-los adequadamente nas subárvores direita e esquerda.
3. Compare os valores restantes 19, 5 e 10 com o nó raiz 12 e posicione-os de acordo. 19 > 12, posicione-o como filho direito de 12; 5 < 12 e 5 < 7, portanto, posicione-o como filho esquerdo de 7. Agora compare 10: 10 é < 12, 10 é > 7 e 10 é > 9, posicione 10 como subárvore direita de 9.

Pseudocódigo para inserir um nó no BST

insert (element, root)
    Node x = root
    Node y = NULL
    while x:
        y = x
        if x.value < element.value
            x = x.right
        else
            x = x.left
    if y.value < element
        y.right = element
    else
        y.left = element

Apagar Operações

Para excluir um nó de uma BST, existem alguns casos, como excluir a raiz ou excluir um nó folha. Além disso, após excluir a raiz, precisamos considerar o nó raiz.

Digamos que queremos excluir um nó folha, podemos simplesmente excluí-lo, mas se quisermos excluir uma raiz, precisamos substituir o valor da raiz por outro nó. Vejamos o seguinte exemplo:

• Caso 1 – Nó com zero filhos: Esta é a situação mais simples, basta excluir o nó que não possui mais filhos à direita ou à esquerda.
• Caso 2 – Nó com um filho: Após excluir o nó, basta conectar seu nó filho ao nó pai do valor excluído.
• Caso 3 – Nó com dois filhos: Esta é a situação mais difícil e funciona com base nas seguintes duas regras:
  • 3a – Predecessor em ordem: Você precisa excluir o nó com dois filhos e substituí-lo pelo maior valor na subárvore esquerda do nó excluído.
  • 3b – Sucessor em Ordem: Você precisa excluir o nó com dois filhos e substituí-lo pelo menor valor na subárvore direita do nó excluído.

1. Este é o primeiro caso de exclusão, no qual você exclui um nó que não possui filhos. Como você pode ver no diagrama, os nós 19, 10 e 5 não possuem filhos. Mas vamos excluir o nó 19.
2. Exclua o valor 19 e remova o link do nó.
3. Veja a nova estrutura da BST sem o 19.

1. Este é o segundo caso de exclusão, no qual você exclui um nó que possui 1 filho. Como você pode ver no diagrama, o nó 9 possui um filho.
2. Exclua o nó 9 e substitua-o por seu filho 10, e adicione um link de 7 para 10.
3. Veja a nova estrutura da BST sem o 9.

1. Aqui você irá excluir o nó 12, que possui dois filhos.
2. A exclusão do nó ocorrerá com base na regra de predecessores em ordem, o que significa que o maior elemento na subárvore esquerda de 12 elementos o substituirá.
3. Exclua o nó 12 e substitua-o por 10, pois este é o maior valor na subárvore esquerda.
4. Veja a nova estrutura da BST após a exclusão do elemento 12.

1. Exclua o nó 12 que possui dois filhos.
2. A exclusão do nó ocorrerá com base na regra de Sucessor em Ordem, o que significa que o menor elemento na subárvore direita de 12 elementos o substituirá.
3. Exclua o nó 12 e substitua-o por 19, pois este é o menor valor na subárvore direita.
4. Veja a nova estrutura da BST após a exclusão do elemento 12.

Apelido Code para excluir um nó

delete (value, root):
    Node x = root
    Node y = NULL
    # searching the node
    while x:
        y = x
        if x.value < value
            x = x.right
        else if x.value > value
            x = x.left
        else if value == x
            break
    # if the node is not null, then replace it with successor
    if y.left or y.right:
        newNode = GetInOrderSuccessor(y)
        root.value = newNode.value
        # after copying the value of successor, delete the successor
        free(newNode)
    else
        free(y)

Termos importantes

• Inserção: Insere um elemento em uma árvore / cria uma árvore.
• Pesquisa: Busca um elemento em uma árvore.
• Pré-encomendar Traversal: Percorre uma árvore de forma pré-ordenada.
• Percurso em ordem: Percorre uma árvore de forma ordenada.
• Percurso pós-ordem: Percorre uma árvore de forma pós-ordem.

Perguntas Frequentes