DEV Community

Mateus Costa
Mateus Costa

Posted on

Um resumo sobre: árvore binária de busca.

Introdução:

Uma árvore binária combina as vantagens de duas estruturas:

  • Um vetor ordenado e uma lista encadeada.

Vantagens:

  • Busca rápida como um vetor ordenado;
  • Inserção e exclusão é rápida como uma lista encadeada;

Olhe a representação de duas árvores, a primeira é a árvore do sistema operacional Linux e a segunda é uma árvore do HTML:

Image description

Vamos falar agora mais especificamente sobre a árvore binária:

  • Ela consiste em nós conectados por arestas;
  • Esse tipo de árvores tem no máximo dois filhos (um filho à esquerda e outra à direita);
  • Mas também pode ter um ou nenhum filho.

Repare na imagem:

Image description

Existem algumas terminologias que também precisamos saber:

  • Caminho: que liga um nó até o outro. Lembre-se que a aresta é a conexão direta entre dois nós adjacentes e o caminho é uma sequência de arestas que conectam dois nós diferentes em uma árvore;
  • Raiz: é o nó na parte superior, no caso da figura acima, a raiz é o número 2. Lembrando que há apenas uma raiz em uma árvore e deve haver somente um caminho da raiz até qualquer outro nó. Olhe esse exemplo de um grafo, que não é uma árvore:
  • Pai: qualquer nó, exceto a raiz, tem uma aresta acima dele que sobe para outro nó. Esse nó de cima é chamado de pai do nó;
  • Filho: o nó pode ter um ou dois nós ligados diretamente abaixo dele, esses nós que estão abaixo, são os filhos do nó de cima;
  • Folha: é um nó que não tem filhos;
  • Subárvore: qualquer nó pode ser considerado a raiz de uma subárvore, que consiste em seus filhos(na imagem acima podemos considerar uma subárvore em que a raiz é o 7, ou outra subárvore que a raiz é o nó número 5);
  • Visitando: um nó é visitado quando o controle do programa chega ao nó, em geral para a finalidade de executar alguma operação no nó;
  • Percorrendo: visitar todos os nós em alguma ordem específica;
  • Níveis: refere-se quantas gerações o nó está da raiz;
  • Chaves: valor utilizado para buscar um item.

Image description

Dentro da árvore binária, existe um tipo específico, que é a árvore binária de busca:

  • O filho à esquerda do pai, tem que ter uma chave menor que o pai e o filho à direita de um nó tem que ter uma chave maior ou igual ao seu pai;

Image description

Vamos analisar a partir de agora como funciona a inserção, a pesquisa e a exclusão neste tipo de estrutura.

Inserção:

  • O local para inserir deve ser encontrado;
  • Segue-se o caminho da raiz até o devido nó, que será o pai do novo nó;
  • Quando o pai for localizado, o novo nó será conectado como seu filho à direita ou à esquerda(dependendo da chave do novo nó ser maior ou menor que o pai);
  • Para um melhor visualização, crie sua árvore acessando este link;
  • Em relação ao Big-O, para a inserção é O(log n) para caso médio e O(n) para o pior caso.

Veja na imagem um algoritmo de inserção em uma árvore binária feito em python:

Image description

Pesquisa:
Para realizarmos a pesquisa em uma árvore binária, nós iremos procurar nas sub árvores direita e esquerda. É possível ter uma melhor visualização acessando este link. Já em termos do Big-O, teremos O(log n) em casos médios e O(n) no pior caso.

Aqui está um algoritmo de pesquisa feito em python para a pesquisa de um nó em uma árvore binária:

Image description

Existem três principais ordens para visitar uma árvore binária:

  1. Pré-ordem (Pre-order): Começando pela raiz da árvore, visite cada nó primeiro antes de visitar seus filhos. Em outras palavras, a visita começa pelo nó raiz, depois visita o filho esquerdo e, em seguida, visita o filho direito. A ordem de visita é: raiz, filho esquerdo, filho direito.
  2. Em-ordem (In-order): Visite o filho esquerdo, depois a raiz e, em seguida, o filho direito. A ordem de visita é: filho esquerdo, raiz, filho direito. Essa ordem é especialmente útil quando a árvore binária representa uma expressão matemática, onde a ordem de precedência dos operadores é levada em consideração. Retorna os números em ordem crescente.
  3. Pós-ordem (Post-order): Visite cada filho antes de visitar a raiz. Em outras palavras, a visita começa pelo filho esquerdo, depois visita o filho direito e, em seguida, visita a raiz. A ordem de visita é: filho esquerdo, filho direito, raiz. Essas ordens de visita podem ser usadas para resolver problemas específicos, dependendo das necessidades da aplicação.

Algoritmo em python representando a pré-ordem, ordem e pós-ordem, respectivamente:

Image description

Image description

Image description

Exclusão:
Para excluir um dado em uma árvore binária de busca, existem alguns cenários:

  • O nó a ser apagado é uma folha (maneira mais simples);
  • O nó a ser apagado tem um filho;
  • O nó a ser apagado tem dois filhos (maneira mais difícil)

Dessa maneira, para o processo de exclusão, precisamos primeiro pesquisar o elemento que queremos apagar e depois identificar em qual dos três casos ele se encaixa. Aqui um algoritmos que representa a parte da pesquisa:

Image description

A segunda parte, caso o nó a ser apagado fosse uma folha:

Image description

A segunda parte caso o nó a ser apagado tiver somente um filho:
Neste caso, nós iremos cortá-lo e conectar o filho dele com o pai. Além disso, iremos verificar se ele não possui filho à direita ou à esquerda.
Para uma melhor visualização acesse este link.

Image description

A segunda parte caso o nó a ser apagado possuir dois filhos:

  • Ele deve ser substituído pelo seu sucessor em ordem (direita esquerda). Para melhor visualização, lembre de utilizar o link anterior.
  • Neste exemplo, se excluirmos o número 66, o que irá entrar no lugar dele será o sucessor em ordem, que é o 73. O próximo, maior que ele.

Image description

Primeiro passo que iremos fazer neste processo é encontrar o sucessor, com isso iremos fazer uma função para encontrar o sucessor de um número. O função será esta:

Image description

Image description

E para realizar o processo de exclusão é só localizar o sucessor e realizar as devidas trocas, dessa maneira:

Image description

O código completo para exclusão, inserção e pesquisa, está neste link.

Caso tenha alguma sugestão sobre o tema, mande mensagem. Será muito bom evoluir com sua ajuda! Obrigado por chegar até aqui e espero ter ajudado!

Este resumo é baseado no curso: Estruturas de dados e algoritmos em python

Top comments (0)