Existem vários tipos de árvores, no entanto, as árvores binárias são as mais utilizadas na computação, porque quando ordenadas, permitem que pesquisas, inclusões e exclusões de dados em sua estrutura sejam extremamente rápidas.
As árvores binárias possuem um nó superior também chamado de raiz que aponta para outros nós, chamados de nós filhos, que podem ser pais de outros nós.
Pode ser caracterizada por
* Não ter elemento algum (Árvore Vazia)
* Ter um elemento distinto, denominado raiz, com dois filhos, denominados subárvore esquerda e subárvore direita.
Inserção de elemento
* Se ainda não há nó raiz, então o novo elemento será o próprio nó raiz
* Se há nó raiz, então compare o novo elemento com o nó raiz
** caso o novo elemento seja menor que o nó raiz, ele vai ser inserido na subárvore da esquerda
** caso o novo elemento seja maior que o nó raiz, ele será inserido na subárvore da direita
Observação: se a subárvore já tiver um valor, a regra acima será usada em recursividade
Para a gente entender um pouquinho melhor como funciona isso, vamos para o seguinte exemplo
Vamos fazer a inserção de seis elementos: 30, 15, 50, 25, 10, 31.
Remoção de elemento
* Se tiver somente um nó, ele será apagado
* se for apagar um nó folha, também não haverá problema, só excluí-lo
* se for deletar um nó que tenha apenas um filho, deleta o nó e o substitui pelo seu filho, trazendo toda a subárvore do filho
* se for deletar um nó que tenha dois filhos
** O nó deletado só pode ser substituído pelo maior nó da subárvore da esquerda ou o menor da subárvore da direita
Observação: utilizar isso recursivamente
São algoritmos que percorrem caminhos pré-definidos em uma estrutura de árvore, cobrindo todos os nós.
Eles tem nomes e aplicações específicas
Há percursos de Pré-ordem, Pós-ordem, Em-ordem, Percurso em largura, Percurso em profundidade e Caminho Euleriano, mas aqui, vamos focar somente nos três primeiros
Pré-ordem
1. Executa a operação do algoritmo primeiro no nó atual
2. Se tem filho à esquerda: executa o pré-ordem no filho da esquerda
3. Se tem filho a direita: executa o pré-ordem no filho da direita
Sequência em pré-ordem: 30, 15, 10, 25 e 50
Em-ordem
1. Se tem filho a esquerda: executa o em ordem no filho da esquerda
2. Executa a operação do algoritmo no nó atual
3. Se tem filho a direita: executa o em-ordem no filho da direita
Sequência em em-ordem: 10, 15, 25, 30 e 50
Pós-ordem
1. Se tem filho à esquerda: executa o pós ordem no filho da esquerda
2. Se tem filho à direita: executa o pós ordem no filho da direita
3. Executa a operarão do algoritmo no nó atual
Sequência em pós-ordem: 10, 25, 15, 50 e 30
Com isso a gente fez uma introdução a árvore binária, no próximo post, vamos ver isso codificado, utilizando a ferramenta VisuAlg
Até lá
Nenhum comentário:
Postar um comentário