ÁRVORE BINÁRIA

Há diversos tipos de árvores, entretanto, árvores binárias são as mais utilizadas, pela simples razão de permitirem quando ordenadas pesquisas, inclusões e exclusões de dados, com um melhor desempenho.

Neste artigo será abordado apenas os conceitos de uma árvore binária, ao final dele vamos disponibilizar uma pequena implementação em java. Conceitos esses sobre percursos, busca, inserção e remoção da mesma.

“Sigam-me os bons!”

As árvores são estruturas de dados baseadas em listas encadeadas. Elas possuem um nó superior também chamado de raiz que aponta para outros nós. Que logo são chamados de nós filhos, que podem também ser pais de outros nós.

· Nós — são todos os itens guardados na árvore

· Raiz — é o nó do topo da árvore.

· Filhos — são os nós que vem depois dos outros nós.

· Pais — são os nós que vem antes dos outros nós.

· Folhas — são os nós que não têm filhos; são os últimos nós da árvore.

Segue abaixo um exemplo uma árvore binária, onde sua raiz é representada pelo nó vermelho.

Um nó que não tem pai é dito ser a raiz da árvore. Se um nó não tem filho é chamado folha.

Neste exemplo foram destacados alguns nós que representam as folhas de uma árvore binária.

BUSCA ÁRVORE BINÁRIA

“Não contavam com minha astúcia!”

Em uma busca binária se começa examinando o nó de uma raiz, caso a árvore esteja vazia, o valor que foi procurado pode não existir nela. Se o valor for igual, é por que a busca foi bem sucedida. Se o valor é menor do que a raiz vai para subárvore a esquerda, senão para subárvore a direita, e assim sucessivamente, até que o valor seja encontrado ou a subárvore seja nula.

Segue abaixo um exemplo de árvore binária:

No exemplo ao lado tem-se uma árvore binária onde a raiz é o elemento 8, o filho da esquerda do elemento 8 é o elemento 3, o filho da direita é o elemento número 10, nota-se que todos elementos da árvore binária possuem no máximo dois filhos, sendo o da esquerda sempre menor e o da direita sempre maior que o elemento pai.

TIPOS DE PERCURSOS EM UMA ÁRVORE BINÁRIA

Existem 3 tipos de percursos em uma árvore binária, eles percorrem a árvore dado uma ordem, enumerando cada nó, o nó que foi enumerado é dito como “visitado”.

Pré-ordem (ou profundidade):

1. Visita a raiz

2. Percorre a subárvore esquerda em pré-ordem

3. Percorre a subárvore direita em pré-ordem

Em-ordem (Ordem Simétrica):

1. Percorre a subárvore esquerda em ordem simétrica

2. Visita a raiz

3. Percorre a subárvore direita em ordem simétrica

Pós-ordem:

1. Percorre a subárvore esquerda em pós-ordem

2. Percorre a subárvore direita em pós-ordem

3. Visita a raiz

Neste exemplo, vamos identificar como cada tipo de percurso vai percorrer dada uma árvore.

Pré-ordem: 8,3,1,6,4,7,10,14,13

Em-ordem: 1,3,4,6,7, 8, 10,13,14

Pós-ordem: 1,4,7,6,3,13,14,10,8

INSERÇÃO

A inserção em uma árvore binária, é muito simples. Primeiro verifica se o valor a ser inserido é menor que o nodo corrente da árvore, se sim vai para sub-árvore esquerda, se não para o maior, enquanto estiver elementos continua a busca, senão insere um novo nó.

EXCLUSÃO

A exclusão de um nó, é um pouco mais difícil para desenvolver. Para excluir um nó de uma árvore binária de busca, há de se considerar três casos distintos para a exclusão:

Exclusão na folha

Onde vamos remove-la da árvore.

Exclusão de um nó com um filho

Excluindo-o, o filho sobe para a posição do pai.

Exclusão de um nó com dois filhos

Neste caso, pode-se operar de duas maneiras diferentes. Pode-se substituir o valor do nó a ser retirado pelo valor sucessor ou pelo valor antecessor, removendo-se aí o nó sucessor.

No exemplo ao lado, o nó de valor 30 está para ser removido, e possui como sucessor imediato o valor 35. Assim sendo, na exclusão, o valor 35 será promovido no lugar do nó a ser excluído, enquanto a sua sub-árvore (direita) será promovida para sub-árvore esquerda do 40, como pode ser visto na figura. Ao excluir, ou mesmo ao incluir, um nó, pode haver o desbalanceamento da árvore, que pode ser corrigido.

"Palma, palma, não priemos cânico!"

Logo podemos corrigi-lo com o balanceamento AVL !!

Acabamos… Mas não fique triste temos outras publicações, como a da árvore AVL menciona agora a pouco, para ler basta clicar aqui!

Para ter acesso ao código com toda implementação da árvore binária. Bom… Clique nesse okay ao lado OK!

Ficamos por aqui, fique com um bom dia.