Primeiro, entenderemos o árvore binária e árvore de pesquisa binária separadamente, e então veremos as diferenças entre uma árvore binária e uma árvore binária de pesquisa.

O que é uma árvore binária?

A Árvore binária é umPonteiro para o filho esquerdo:Ele armazena a referência do nó filho esquerdo.Ponteiro para o filho certo:Ele armazena a referência do nó filho direito.Elemento de dados:O elemento de dados é o valor dos dados que são armazenados pelo nó.

A árvore binária pode ser representada como:

Na figura acima, podemos observar que cada nó contém no máximo 2 filhos. Se algum nó não contiver filho esquerdo ou direito, o valor do ponteiro em relação a esse filho será NULL.

As terminologias básicas usadas em uma árvore binária são:

Nó raiz:O nó raiz é o primeiro ou o nó superior em uma árvore binária.Nó pai:Quando um nó está conectado a outro nó através de arestas, esse nó é conhecido como nó pai. Em uma árvore binária, o nó pai pode ter no máximo 2 filhos.Nó filho:Se um nó tiver seu antecessor, então esse nó é conhecido como nó filho .Nó da folha:O nó que não contém nenhum filho conhecido como Nó da folha .Nó interno:O nó que tem pelo menos 2 filhos é conhecido como nó interno .Profundidade de um nó:A distância do nó raiz até o nó fornecido é conhecida como profundidade de um nó . Fornecemos rótulos para todos os nós, como o nó raiz é rotulado com 0, pois não tem profundidade, os filhos dos nós raiz são rotulados com 1, os filhos do filho raiz são rotulados com 2.Altura:A maior distância do nó raiz ao nó folha é altura do nó .

Em uma árvore binária, existe uma árvore conhecida como árvore binária perfeita . É um árvore na qual todos os nós internos devem conter dois nós e todos os nós folha devem estar na mesma profundidade. No caso de uma árvore binária perfeita, o número total de nós existentes em uma árvore binária pode ser calculado usando a seguinte equação:

n = 2^m+1-1

onde n é o número de nós, m é a profundidade de um nó.

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

A Árvore de pesquisa binária é uma árvore que segue alguma ordem para organizar os elementos, enquanto a árvore binária não segue nenhuma ordem. Em uma árvore de pesquisa binária, o valor do nó esquerdo deve ser menor que o nó pai e o valor do nó direito deve ser maior que o nó pai.

Vamos entender o conceito de árvore de busca binária por meio de exemplos.

Na figura acima, podemos observar que o valor do nó raiz é 15, que é maior que o valor de todos os nós da subárvore esquerda. O valor do nó raiz é menor que os valores de todos os nós em uma subárvore direita. Agora, passamos para o filho esquerdo do nó raiz. 10 é maior que 8 e menor que 12; também satisfaz a propriedade da árvore de pesquisa binária. Agora, passamos para o filho direito do nó raiz; o valor 20 é maior que 17 e menor que 25; também satisfaz a propriedade da árvore de pesquisa binária. Portanto, podemos dizer que a árvore mostrada acima é a árvore binária de busca.

Agora, se alterarmos o valor de 12 para 16 na árvore binária acima, teremos que descobrir se ainda é uma árvore de pesquisa binária ou não.

O valor do nó raiz é 15, que é maior que 10, mas menor que 16, portanto, não satisfaz a propriedade da árvore de pesquisa binária. Portanto, não é uma árvore de pesquisa binária.

Operações na árvore de pesquisa binária

Podemos realizar operações de inserção, exclusão e pesquisa na árvore de pesquisa binária. Vamos entender como é realizada uma busca em uma busca binária. A árvore binária é mostrada abaixo na qual devemos realizar a operação de pesquisa:

Suponha que tenhamos que pesquisar 10 na árvore binária acima. Para realizar a pesquisa binária, consideraremos todos os inteiros em um array ordenado. Primeiro, criamos uma lista completa em um espaço de busca, e todos os números existirão no espaço de busca. O espaço de busca é marcado por dois ponteiros, ou seja, início e fim. A matriz da árvore binária acima pode ser representada como

Primeiro, calcularemos o elemento do meio e compararemos o elemento do meio com o elemento que será pesquisado. O elemento do meio é calculado usando n/2. O valor de n é 7; portanto, o elemento do meio é 15. O elemento do meio não é igual ao elemento pesquisado, ou seja, 10.

Nota: Se o elemento pesquisado for menor que o elemento intermediário, a pesquisa será realizada na metade esquerda; caso contrário, a pesquisa será feita na metade direita. No caso de igualdade, o elemento é encontrado.

Como o elemento a ser pesquisado é menor que o elemento intermediário, a pesquisa será realizada no array esquerdo. Agora a busca está reduzida à metade, conforme mostrado abaixo:

O elemento intermediário na matriz esquerda é 10, que é igual ao elemento pesquisado.

Complexidade de tempo

Em uma pesquisa binária, existem n elementos. Se o elemento do meio não for igual ao elemento pesquisado, então o espaço de busca é reduzido para n/2, e continuaremos reduzindo o espaço de busca em n/2 até encontrarmos o elemento. Na redução total, se passarmos de n para n/2 para n/4 e assim por diante, então será necessário log₂n passos.

Diferenças entre árvore binária e árvore de pesquisa binária