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

Índice:

Anonim

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

A árvore de busca binária é um algoritmo avançado usado para analisar o nó, seus ramos esquerdo e direito, que são modelados em uma estrutura de árvore e retornam o valor. O BST é desenvolvido na arquitetura de um algoritmo de busca binária básico; portanto, permite pesquisas, inserções e remoções mais rápidas de nós. Isso torna o programa muito rápido e preciso.

Neste tutorial de Estrutura de Dados, você aprenderá:

  • O que é uma árvore de pesquisa binária?
  • Atributos da árvore de pesquisa binária
  • Por que precisamos de uma árvore de busca binária?
  • Tipos de árvores binárias
  • Como funciona a árvore de pesquisa binária?
  • Termos Importantes

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 um máximo de dois subnós ou subárvores nos lados esquerdo e direito.
  • Cada subárvore, também conhecida como árvore de pesquisa binária, possui sub-ramificações à direita e à esquerda de si mesmas.
  • 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 do que as chaves de seu nó pai
  • Da mesma forma, as chaves dos nós da subárvore esquerda têm valores menores do que as chaves dos seus nós pais.

  1. Existe o nó principal ou nível principal 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 do que o nó pai
  3. A subárvore esquerda tem valores que o nó pai

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

  • Os dois principais fatores que tornam a árvore de pesquisa binária uma solução ótima para quaisquer problemas do mundo real são velocidade e precisão.
  • Devido ao fato de que a pesquisa binária está em um formato semelhante a um ramo 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 deve fazer para localizar o elemento desejado.
  • Além disso, no caso do elemento a ser pesquisado ser maior ou menor que o nó pai, o nó sabe em qual lado da árvore pesquisar. O motivo é 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 autocompletar e gráficos.
  • O algoritmo suporta com eficiência operações como pesquisa, inserção e exclusão.

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, direcionando 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, existe o mesmo nível de cada subnó.

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 valores com a raiz e seus outros nós filhos na subárvore esquerda ou direita de acordo.

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:

  • Pesquisa: 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 tem sua própria estrutura e método de execução / análise, mas o mais complexo de todos é a operação Delete.

Operação de Pesquisa

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

  1. O elemento a ser pesquisado é 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 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, olhe na subárvore filha certa
  5. 10 corresponde ao valor no nó, 10 = 10, retorna o valor ao usuário.

Operação de Inserção

Esta é uma operação muito direta. Primeiro, o nó raiz é inserido e, em seguida, o próximo valor é comparado com o nó raiz. Se o valor for maior que a raiz, 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 devem ser inseridos em um BST da esquerda para a direita
  2. Insira 12 como o nó raiz e compare os próximos valores 7 e 9 para inserir de acordo na subárvore 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 filho direito de 12, 5 <12 e 5 <7, portanto, coloque-o como filho esquerdo de 7.
    1. Agora compare 10, 10 é <12 e 10 é> 7 e 10 é> 9, coloque 10 como subárvore direita de 9.

Excluir operações

Excluir é a mais avançada e complexa entre todas as outras operações. Existem vários casos tratados para exclusão no BST.

  • Caso 1 - Nó com zero filhos: esta é a situação mais fácil, basta deletar o nó que não tem mais filhos à direita ou à esquerda.
  • Caso 2 - Nó com um filho: depois de excluir o nó, simplesmente conecte seu nó filho com o 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 - Em ordem predecessora: você precisa excluir o nó com dois filhos e substituí-lo pelo maior valor na subárvore esquerda do nó excluído
    • 3b - In Order Successor: 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 iremos 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 tem 1 filho, como você pode ver no diagrama que 9 tem 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ê excluirá o nó 12 que tem dois filhos
  2. A exclusão do nó ocorrerá com base na regra do predecessor, 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. Visualize a nova estrutura do BST após a exclusão de 12

  1. 1 Exclua um nó 12 que tem 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

Termos Importantes

  • Inserir - Insere um elemento em uma árvore / cria uma árvore.
  • Pesquisar - Pesquisa um elemento em uma árvore.
  • Pré-encomenda Traversal - Percorre uma árvore de maneira pré-encomenda.
  • Inorder Traversal - Percorre uma árvore de maneira ordenada.
  • Postorder Traversal - atravessa uma árvore de maneira pós-ordem.

Resumo

  • O BST é um algoritmo de nível avançado que executa várias operações com base 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 do que o nó raiz.
  • Cada nó pode ter zero, um ou dois filhos.
  • Uma árvore de pesquisa binária facilita as operações primárias como pesquisa, inserção e exclusão.
  • Sendo o Delete o mais complexo, há 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.