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:
E para realizar o processo de exclusão é só localizar o sucessor e realizar as devidas trocas, dessa maneira:
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)