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

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 um relacionamento 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 do nó pai
• Da mesma forma, as chaves dos nós da subárvore esquerda têm valores menores do que as chaves do nó pai.

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

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

• Os dois principais fatores que tornam a árvore de pesquisa binária uma solução ideal para qualquer problema do mundo real são velocidade e 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 qual lado da árvore procurar. A razão é que 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 nas árvores estão cheios de possíveis exceções do último nível. Da mesma forma, todos os nós estão cheios, direcionados para a extrema esquerda.
• Árvore binária completa: todos os nós possuem 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, existe o mesmo nível de cada subnó.

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

• Pesquisar: pesquisa o elemento da árvore binária
• Inserir: adiciona um elemento à árvore binária
• Excluir: exclui 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

Sempre inicie a análise da árvore no nó raiz e, em seguida, vá para a subárvore direita ou esquerda do nó raiz, dependendo do elemento a ser localizado ser menor ou maior que a raiz.

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

Pseudocódigo para pesquisa no 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 root, ele será adicionado à subárvore direita, e se for menor que a raiz, será adicionado à subárvore esquerda.

1. Existe uma lista de 6 elementos que precisam ser inseridos em um BST na ordem da esquerda para a direita
2. Insira 12 como o nó raiz e compare os próximos valores 7 e 9 para inserir adequadamente nas subárvores direita e esquerda
3. Compare os valores restantes 19, 5 e 10 com o nó raiz 12 e coloque-os de acordo. 19> 12 coloque-o como o filho direito de 12, 5 <12 e 5 <7, portanto, coloque-o como filho esquerdo de 7. Agora compare 10, 10 é <12 e 10 é> 7 e 10 é> 9, coloque 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 um BST, existem alguns casos, ou seja, excluir uma raiz ou excluir um nó folha. Além disso, após excluir uma raiz, precisamos pensar no 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 fácil, basta excluir o nó que não possui mais filhos à direita ou à esquerda.
• Caso 2 – Nó com um filho: depois de 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 de acordo com as duas regras a seguir
• 3a – No Predecessor do Pedido: você precisa excluir o nó com dois filhos e substituí-lo pelo maior valor na subárvore esquerda do nó excluído
• 3b – Sucessor do pedido: você precisa excluir o nó com dois filhos e substituí-lo pelo maior valor na subárvore direita do nó excluído

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

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

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

1. 1 Exclua um nó 12 que possui dois filhos
2. 2 A exclusão do nó ocorrerá com base na regra In Order Successor, o que significa que o maior elemento na subárvore direita de 12 irá substituí-lo
3. 3 Exclua o nó 12 e substitua-o por 19, pois é o maior valor na subárvore direita
4. 4 Visualize a nova estrutura do BST após a exclusão de 12

Pseudocódigo 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 to the root #we're deleting the successor
    	free(newNode)
    else
    	free(y)

Termos importantes

• Inserir: Insere um elemento em uma árvore/cria uma árvore.
• Pesquisar: Pesquisa um elemento em uma árvore.
• Preorder Traversal: percorre uma árvore de maneira pré-encomendada.
• Inorder Traversal: percorre uma árvore de maneira ordenada.
• Postorder Traversal: percorre uma árvore de maneira pós-ordem.

Resumo

• BST é um algoritmo de nível avançado que executa diversas operações baseadas na comparação dos valores do nó com o nó raiz.
• Qualquer um dos pontos em uma hierarquia pai-filho representa o nó. Pelo menos um nó pai ou raiz permanece presente o tempo todo.
• Existem uma subárvore esquerda e uma subárvore direita. A subárvore esquerda contém valores menores que o nó raiz. No entanto, a subárvore direita contém um valor maior que o nó raiz.
• Cada nó pode ter zero, um ou dois filhos.
• Uma árvore de pesquisa binária facilita operações primárias como pesquisar, inserir e excluir.
• Excluir sendo o mais complexo tem vários casos, por exemplo, um nó sem filho, um nó com um filho e um nó com dois filhos.
• O algoritmo é utilizado em soluções do mundo real, como jogos, dados de preenchimento automático e gráficos.