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

Uma árvore de pesquisa binária é uma das várias estruturas de dados que nos ajudam a organizar e classificar os dados. É uma maneira eficiente de armazenar dados em uma hierarquia e é muito flexível.

Neste artigo, examinaremos mais de perto como ele funciona - junto com suas propriedades e aplicativos.

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

Uma árvore de pesquisa binária é uma estrutura de dados composta de nós - semelhante a listas vinculadas. Pode haver dois tipos de nós: um pai e um filho. O nó raiz é o ponto inicial da estrutura que se ramifica em dois nós filhos, chamados de nó esquerdo e nó direito.

Cada nó só pode ser referenciado por seu pai, e podemos atravessar os nós da árvore dependendo da direção. A árvore de pesquisa binária tem três propriedades principais:

1. O nó esquerdo é menor que seu pai.
2. O nó certo é maior que seu pai.
3. As subárvores esquerda e direita devem ser Árvores Binárias de Busca.

Uma árvore de busca binária perfeita é alcançada quando todos os níveis são preenchidos e cada nó tem um nó filho esquerdo e direito.

Relacionado: Bibliotecas de ciência de dados para Python que todo cientista de dados deve usar

Operações básicas de uma árvore de pesquisa binária

Agora que você tem uma ideia melhor do que é uma árvore de pesquisa binária, podemos observar suas operações básicas a seguir.

1. Operação de Pesquisa

A pesquisa nos permite localizar um determinado valor presente na árvore. Podemos usar dois tipos de pesquisas: pesquisa em largura (BFS) e pesquisa em profundidade (DFS). A pesquisa em amplitude é um algoritmo de pesquisa que começa no nó raiz e atravessa horizontalmente, lado a lado, até que o objetivo seja encontrado. Cada nó é visitado uma vez durante esta pesquisa.

A pesquisa em profundidade, por outro lado, atravessa a árvore verticalmente - começando no nó raiz e descendo em um único galho. Se o objetivo for encontrado, a operação termina. Mas se não, ele e procura os outros nós.

2. Operação de Inserção

A operação de inserção utiliza a operação de pesquisa para determinar o local onde o novo nó deve ser inserido. O processo começa no nó raiz e a pesquisa começa até que o destino seja alcançado. Existem três casos a serem considerados com a inserção.

• Caso 1: quando nenhum nó existe. O nó a ser inserido se tornará o nó raiz.

• Caso 2: não há filhos. Nesse caso, o nó será comparado ao nó raiz. Se for maior, se tornará a criança certa; caso contrário, ele se tornará o filho esquerdo.

• Caso 3: quando a raiz e seus filhos estão presentes. O novo nó será comparado a cada nó em seu caminho para determinar qual nó ele visitará em seguida. Se o nó for maior do que o nó raiz, ele percorrerá a subárvore direita ou esquerda. Da mesma forma, as comparações são feitas em cada nível para determinar se ele irá para a direita ou para a esquerda até chegar ao seu destino.

3. Excluir operação

A operação de exclusão é usada para remover um nó específico da árvore. A exclusão é considerada complicada, pois após a remoção de um nó, a árvore deve ser reorganizada de acordo. Existem três casos principais a serem considerados:

• Caso 1: Excluindo um nó folha. Um nó folha é um nó sem filhos. Este é o mais fácil de remover, pois não afeta nenhum outro nó; simplesmente atravessamos a árvore até alcançá-la e excluí-la.

• Caso 2: Excluindo um nó com um filho. Excluir um pai com um nó resultará no filho assumindo sua posição e todos os nós subsequentes irão subir um nível. Não haverá mudança na estrutura das subárvores.

• Caso 3: Excluindo um nó com dois filhos. Quando temos que remover um nó com dois filhos, devemos primeiro encontrar um nó subsequente que pode assumir sua posição. Dois nós podem substituir o nó removido, o sucessor ou predecessor em ordem. O sucessor em ordem é o filho mais à esquerda da subárvore direita, e o predecessor em ordem é o filho mais à direita da subárvore esquerda. Copiamos o conteúdo do sucessor / predecessor para o nó e excluímos o sucessor / predecessor em ordem.

Relacionado: Como construir estruturas de dados com classes JavaScript ES6

Como atravessar uma árvore de pesquisa binária

Traversal é o processo pelo qual navegamos em uma árvore de pesquisa binária. Isso é feito para localizar um item específico ou para imprimir um contorno da árvore. Sempre partimos do nó raiz e temos que seguir as arestas para chegar aos outros nós. Cada nó deve ser considerado uma subárvore, e o processo é repetido até que todos os nós sejam visitados.

• Transversal em ordem: Percorrer em ordem produzirá um mapa em ordem crescente. Com este método, começamos da subárvore esquerda e continuamos para a subárvore raiz e direita.

• Transversal da pré-encomenda: Neste método, o nó raiz é visitado primeiro, seguido pela subárvore esquerda e pela subárvore direita.

• Traversal pós-pedido: Essa travessia envolve visitar o nó raiz por último. Começamos na subárvore esquerda, depois na subárvore direita e, em seguida, no nó raiz.

Aplicativos do mundo real

Então, como utilizamos algoritmos de árvore de pesquisa binária? Como pode ser presumido, eles são extremamente eficientes na busca e classificação. A maior força das árvores binárias é sua estrutura organizada. Ele permite que a pesquisa seja feita em velocidades notáveis, cortando a quantidade de dados que precisamos analisar pela metade por passagem.

As árvores de pesquisa binárias nos permitem manter com eficiência um conjunto de dados que muda dinamicamente de uma forma organizada. Para aplicativos que têm dados inseridos e removidos com frequência, eles são muito úteis. Os mecanismos de videogame usam um algoritmo baseado em árvores conhecidas como partição de espaço binário para ajudar a renderizar objetos de maneira ordenada. O Microsoft Excel e a maioria dos softwares de planilha usam árvores binárias como estrutura de dados básica.

Você pode se surpreender ao saber que o código Morse usa uma árvore de pesquisa binária para codificar dados. Outra razão importante pela qual as árvores de pesquisa binárias são tão úteis são suas múltiplas variações. Sua flexibilidade levou à criação de inúmeras variantes para resolver todos os tipos de problemas. Quando usadas corretamente, as árvores de busca binárias são um grande trunfo.

Árvores de pesquisa binárias: o ponto de partida perfeito

Uma das principais maneiras de avaliar a experiência de um engenheiro é por meio de seu conhecimento e aplicação de estruturas de dados. As estruturas de dados são úteis e podem ajudar a criar um sistema mais eficiente. Árvores de busca binárias são uma ótima introdução às estruturas de dados para qualquer desenvolvedor que esteja começando.

15 métodos de array de JavaScript que você deve dominar hoje

Quer entender os arrays JavaScript, mas não consegue dominá-los? Verifique nossos exemplos de array de JavaScript para orientação.

Leia a seguir

Sobre o autor