Estruturando dados: Árvore binária de busca

Olá, seja muito bem vindo(a), anteriormente conhecemos sobre estrutura de dados hierárquicos: https://programacao-descomplicada.blogspot.com/2022/11/estruturando-dados-o-que-e-uma.html e também sobre formas de percorrer estruturas de árvores: https://programacao-descomplicada.blogspot.com/2022/11/estrutrando-dados-formas-de-percorrer.html. 

  Agora, nós iremos conhecer um pouco sobre as árvores binárias de busca, que nada mais é do que uma árvore com noção de ordem. Nesse caso, os dados armazenados na árvore precisam ser comparáveis. Sendo assim, para todo nó da árvore, o filho à esquerda contém nós menores que o seu pai, e o filho da direita contém nós maiores que o seu pai, sendo essa a propriedade que define uma árvore de busca. 

  Na imagem acima podemos ver um exemplo de árvore binária de busca. Esse tipo de árvore tem como base a ideia do algoritmo de busca binária, que permite uma procura, inserção e remoção rápidas dos nós. Sendo esperado que em uma árvore desse tipo, eu caminhe para um lado ou para outro descartando metade dela. 

  Exemplificando isso, digamos que eu esteja buscando o dado 30 na árvore da imagem acima, eu começo pelo nó-raiz (40), e vou para o lado esquerdo (20) que é menor que 30, daí eu chego onde eu quero porque o lado direito do nó 20 é um dado maior que ele, achamos o nosso 30 sem precisar caminhar pelo lado direito da árvore.

  Logicamente, pela noção de ordem da árvore binária de busca, o elemento mínimo se encontra do lado esquerdo e o elemento máximo, no direito. Reparando na nossa imagem anterior, vemos que o mínimo e o máximo são as folhas, 10 e 70, que estão do lado esquerdo e direito respectivamente.

  Para inserir elementos na árvore binária de busca, começamos do nó-raiz da árvore e descemos de modo recursivo, procurando pelo local certo para inserir o novo nó. Exemplificando, temos um nó-raiz 8, o próximo dado seria o 4, ele ficaria a esquerda de 8, pois é menor que ele. Agora temos o dado 6, ele seria o nó filho à direita do 4, pois ele é maior que ele.

  No caso da remoção de um dado, teríamos os seguintes casos: no caso de um nó vazio, não há nada para remover nele, no caso de um nó a ser removido ser um nó folha, removemos a folha, no caso de um nó a ser removido ter um filho, temos que conectar o filho com o pai do nó que será removido. Ainda, se o nó a ser removido tiver dois filhos, primeiro pegamos o sucessor e colocamos no local do nó a ser removido antes de efetuar a remoção. Deletando o nó 20 da nossa imagem, primeiro o 30 iria para o seu lugar e o 20 seria removido após isso. 

  Vou ficando por aqui, espero que você tenha conhecido sobre árvores binárias de busca, ainda temos que pensar na construção dos códigos, pois até o momento estamos aprendendo de forma teórica. Para isso, pretendo usar a linguagem python, pois atualmente estou utilizando ela nos estudos de estrutura de dados. Um abraço e até a próxima.

Artigo Original: https://programacao-descomplicada.blogspot.com/2022/11/estruturando-dados-arvore-binaria-de.html