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

#python #algorithms

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:

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:

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.

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;

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:

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:

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

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.
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.
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:

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:

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

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.

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.

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: