Um resumo sobre: árvore binária de busca.
Tags: python, algorithms
Published: 2023-03-12 23:46:39

**<u>Introdução:</u>**

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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/013yirfhjuq5b70k5tdk.png)


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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/lo2ql45kh4x4vxkc5mfx.png)


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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/65l3k1hrbiz44iu2due7.png)


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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/13adc8yikwdskiqnuqub.png)

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

**<u>Inserção:</u>**

- 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](https://visualgo.net/en/bst);
- 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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/4badw9tcrw26mykfqrpa.png)

**<u>Pesquisa:</u>**
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](https://visualgo.net/en/bst). 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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/xkw38zhj11qnjuqb8oe5.png)

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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/38l1o8a1mjmxvtjsntyu.png)

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/m5cwyfjvd10a6pveivvs.png)

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/o9j5cyyslvk039xz44zq.png)

**<u>Exclusão:</u>**
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 **<u>pesquisar</u>** 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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/jnn16z44kwr00xp5d4wa.png)

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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/td6wsibvy9w0zsykd2nw.png)

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](https://visualgo.net/en/bst).

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/cqclm0try3isrmbo6tv3.png)

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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/cyj704q2t7i27dmwezrd.png)

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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/llscqd61xdhnmho5g0wg.png)


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/n9vy3yqdb4yhiuber6os.png)

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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ogeyegv06fxzh7i1whbt.png)

O código completo para exclusão, inserção e pesquisa, está [neste link](https://colab.research.google.com/drive/1vIqgazfAZmjlh77yY1Djub6cta75ijNx?usp=sharing). 

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](https://www.udemy.com/course/estrutura-de-dados-e-algoritmos-python-guia-completo/)