Árvore binária vs árvore de pesquisa binária: diferença entre árvore binária e árvore de pesquisa binária

Introdução

A classificação é o processo de organizar os dados em uma ordem sistemática para que possam ser analisados ​​de forma mais eficaz. O processo de identificação de um determinado registro é chamado de busca. Se os dados forem classificados corretamente em uma ordem específica, a pesquisa se tornará uma tarefa fácil e eficiente. Este artigo trata de uma das mais importantes estruturas de dados não lineares, ou seja, as árvores.

As árvores são usadas principalmente para representar dados, demonstrando uma relação hierárquica entre os elementos. Por exemplo, índice, árvore genealógica. Tecnicamente, uma árvore pode ser definida como um conjunto finito 'T' de um ou mais nós tal que um nó é atribuído como a raiz da árvore e os outros nós são divididos em n>=0 conjuntos disjuntos T1, T2, T3, T4 …. Tn e são chamados como subárvores ou filhos desse nó raiz.

O que é uma árvore binária?

Uma árvore binária é uma estrutura de dados não linear em que um nó pode ter 0, 1 ou 2 nós. Cada nó na árvore binária é denominado como um nó pai ou como um nó filho. O nó mais alto da Árvore Binária é chamado de nó raiz. Cada nó pai pode ter no máximo 2 nós filhos, que são o nó filho esquerdo e o nó filho direito.

Um nó em uma árvore binária tem três campos:

1. Elemento de Dados – Armazena o valor de dados que deve ser armazenado pelo nó.
2. Ponteiro para o filho esquerdo – Ele armazena a referência (ou endereço) para o nó filho esquerdo.
3. Ponteiro para o filho direito – Armazena a referência ao nó filho direito.

Desta forma, vários nós são combinados para construir uma Árvore Binária.

Uma árvore binária pode ser representada como:

Fonte

Da figura acima, o nó raiz 2 tem dois filhos (ou nós filhos), 7 e 5. 7 é chamado de nó filho esquerdo e 5 é chamado de nó filho direito. Dessa forma, cada um dos nós filhos atua como um nó pai para vários outros nós e juntos representam a Árvore Binária.

Confira: Tipos de Árvore Binária

Terminologias usadas em Árvore Binária

Nó : A representação básica de um ponto de terminação em uma árvore.

Nó Raiz : O nó mais alto de uma Árvore Binária.

Nó pai : se um nó está conectado a outro nó por meio de arestas, ele é conhecido como nó pai. Em uma árvore binária, um nó pai pode ter no máximo 2 nós filhos.

Nó filho : se um nó tem um predecessor, ele é conhecido como nó filho.

Nó Folha : Um nó que não possui nenhum nó filho é chamado de nó folha.

Profundidade de um nó : É a distância do nó raiz até aquele nó particular cuja profundidade deve ser medida.

Altura da árvore : É a maior distância do nó raiz ao nó folha.

Estas são algumas terminologias básicas de uma Árvore Binária. Com esta compreensão básica de uma Árvore Binária, vamos avançar para um avanço da Árvore Binária conhecida como Árvore de Busca Binária.

Leia também: Algoritmo de pesquisa binária: função, benefícios, complexidade de tempo e espaço

O que é uma árvore de pesquisa binária

Como o nome sugere, uma árvore de pesquisa binária ou BST é uma árvore usada na classificação, recuperação e pesquisa de dados. É também um tipo de estrutura de dados não linear em que os nós são organizados em uma ordem específica. Por isso, também é chamado de “ Árvore Binária Ordenada ”. Possui as seguintes propriedades:

• A subárvore esquerda de um nó possui nós que são apenas menores que a chave desse nó.
• A subárvore direita de um nó possui nós que são apenas maiores que a chave desse nó.
• Cada nó tem chaves distintas e duplicatas não são permitidas na Árvore de Pesquisa Binária.
• A subárvore esquerda e direita também deve ser uma árvore de busca binária.

Vamos visualizar este conceito para obter uma compreensão clara das Árvores de Pesquisa Binária.

Fonte

Na figura acima, vemos que o valor do nó raiz é 8. Com um exame mais minucioso, observa-se que todos os valores na subárvore esquerda são menores que o valor do nó raiz e todos os valores na subárvore direita têm valores que são maiores que o nó raiz. Além disso, observa-se que cada valor na Árvore de Pesquisa Binária é único e não há duplicatas. Assim, as propriedades da Binary Search Tree indicadas acima são verificadas.

Ainda em outro exemplo, vemos que, embora as subárvores esquerda e direita sejam árvores binárias de busca com valores únicos em toda a árvore. O valor no nó folha na subárvore esquerda é 12, que é maior que o valor do nó raiz, que é 12. Assim, isso não satisfaz a propriedade do BST e, portanto, não é uma Árvore de Pesquisa Binária.

Operação de busca em um BST –

Considere uma árvore de pesquisa binária com os valores fornecidos abaixo. Vamos entender como a operação de pesquisa é realizada para obter 9 da Árvore de Pesquisa Binária.

Fonte

Para realizar a busca binária, devemos inicialmente organizar todos os inteiros em um array ordenado. Isso é chamado de espaço de busca. Este espaço de busca deve consistir em dois ponteiros, chamados de ponteiros inicial e final. A matriz da árvore de pesquisa binária fornecida acima é representada como:

O primeiro passo é calcular o valor do meio do array e compará-lo com o valor a ser pesquisado, 9 no nosso caso. Isso é feito calculando n/2, onde n é o número total de elementos na matriz (BST) e é 6. Assim, o 3º elemento é o elemento do meio que é 5.

Agora que o elemento do meio é comparado com 9 e como não é igual (maior), a operação de busca será realizada no array direito. Desta forma, a operação de busca é reduzida à metade, conforme mostrado abaixo:

Na próxima etapa, o elemento do meio é calculado e encontrado como 9, que corresponde ao nosso elemento a ser pesquisado.

Árvore Binária vs Árvore de Pesquisa Binária –

Agora que temos uma compreensão básica da Árvore Binária e das Árvores de Pesquisa Binária, vamos resumir rapidamente algumas das diferenças entre ambas.

Conclusão

Assim, inferimos que, embora tanto a Árvore Binária quanto a Árvore de Busca Binária tenham uma estrutura hierárquica comum com uma coleção de nós, elas apresentam diversas diferenças em sua aplicação. Uma árvore binária é uma estrutura básica com uma regra simples de que nenhum pai deve ter mais de 2 filhos, enquanto a árvore de busca binária é uma variante da árvore binária seguindo uma ordem específica com a qual os nós devem ser organizados.

Se você está curioso para aprender sobre árvore binária vs árvore de busca binária, confira o Diploma PG em Ciência de Dados do IIIT-B & upGrad, que é criado para profissionais que trabalham e oferece mais de 10 estudos de caso e projetos, workshops práticos práticos, orientação com a indústria especialistas, 1-on-1 com mentores do setor, mais de 400 horas de aprendizado e assistência de trabalho com as principais empresas.

Aprenda cursos de ciência de dados online das melhores universidades do mundo. Ganhe Programas PG Executivos, Programas de Certificado Avançado ou Programas de Mestrado para acelerar sua carreira.