Árvores

Afluentes: Estrutura de Dados

Árvores

Existe uma ampla variedade de dados que são comumente organizados sob a forma de árvores hierárquicas utilizadas recorrentemente em nosso dia a dia. Exemplos são a organização administrativa de empresas (Diretor, Gerentes, Chefes de Departamento, etc), a tabela de jogos de uma disputa esportiva (rodada classificatória, oitavas de final, quartas de final, etc) taxonomias (botânica, biologia, etc) dentre muitos outros.

É lógico concluir que a criação de uma estrutura de dados computacional para acomodação de tais tipos de informação se faz necessária. Neste capítulo apresentamos o conceito de árvores. Inicialmente será apresentada a nomenclatura que permeia esta estrutura de dados, seguida de uma comparação com o conceito de grafos no qual será demonstrado que árvores nada mais são do que um caso particular de grafos. Em seguida o estudo de árvores se concentrará em um tipo específico chamado Árvores Binárias.

Nomenclatura

A figura abaixo sumariza todos os principais conceitos relativos a árvores. Toda árvore é composta por elementos chamados nós. Tais nós são organizados de uma maneira hierárquica, ou seja, ligados logicamente uns aos outros de forma a mimetizar ramificações de uma árvore. Embora na natureza árvores ocorram naturalmente de forma que a raiz seja localizada na parte inferior (próxima ao chão) e seus galhos se ramifiquem para cima, em computação, árvores são representadas na ordem inversa, ou seja, raiz no topo e ramificações se expandindo para baixo.

O nó localizado mais acima é chamado de nó raiz. Ele deve ser único para cada árvore servindo alternativamente como um cabeçalho da estrutura de dados. Outro fator que diferencia o nó raiz dos demais nós é o fato de que ele não possuir nós ancestrais. Tal fato traz a nossa atenção outro conceito importante, o fato de que as relações entre nós em uma árvore são nomeadas. Um nó A é dito ancestral ou pai de outro nó B se B é expandido a partir de A. Ainda B é dito filho de A. Os nós que não possuem nenhum filho são chamados de nós folha ou nós terminais e todos os demais nós que não são nem o nó raiz nem folhas são chamados de nós internos. Cada nível de ancestralidade, ou seja, a cada vez que uma nova linha de expansão ocorre em uma árvore dizemos que um novo nível de ramificação é criado. Os níveis são numerados a partir da raiz (nível 0) até o último nível de expansão (nível N) que conterá apenas nós folha. Por fim, o número total de níveis de uma árvore é chamado de altura da arvore.

Árvores Binárias

Como exemplificado no diagrama de Venn acima, árvores binárias são um tipo especial de árvores nas quais todo nó possui exatamente dois nós filhos exceto os nos folha, que devem possuir exatamente 0 filhos. Elas são muito útil para modelar situações em que precisam ser tomadas decisões bidirecionais em cada ponto de um processo.

Dizemos que uma árvore binária é completa de nível d se todas as folhas da árvore encontram-se no nível d.

Note que se a árvore contiver m nós no nível l, ela conterá no máximo 2m nós no nível l+1 . Uma árvore binária completa de nível d contém exatamente 2 l nós em cada lível l entre 0 e d (profundidade d com exatamente 2 d nós no nível d.

Arquivo:Arvore 03

Árvore Binárias Quase Completas

Uma árvore binária é dita quase completa se todas as folhas da árvore devem estar localizadas no nível d ou no nível d-1. Para cada nó nd na árvore com um descendente direto no nível d, todos os descendentes esquerdos de nd que forem folhas estiverem também no nível d.

Uma forma mais simples de verificar se uma árvore binária é quase completa é checar se todos os nós folha encontram-se nos níveis d e d-1, e se todos os nós folhas estão "identados para a esquerda".

O interesse em árvores binárias quase completas reside no fato de que se uma dada árvore é quase completa, sua implementação computacional fica consideravelmente simplificada como veremos mais adiante.

Numeração de nós de árvores binárias

Os nós de uma árvore binária quase completa podem ser numerados da seguinte forma:

• 1 para a raiz
• Filho esquerdo = dobro do n. do pai
• Filho direito = dobro + 1 do n. do pai

A numeração dos nós ajuda na implementação (implementação por vetores) e facilita a pesquisa de itens na árvore. A figura abaixo exemplifica a numeração de uma árvore completa de altura 3 assim como sua codificação em um array.

Implementando Árvores Binárias Usando Arrays

Existem diversas formas de se implementar árvores binárias. Neste capítulo estudaremos a implementação via arrays estáticos e via estruturas dinâmicas ligadas.

A implementação via arrays requer que a árvore binária a ser codificada seja uma árvore binária completa ou quase completa. Tal fato impõe a restrição de que toda a estrutura da árvore deve ser conhecida antes de se criar a estrutura de dados para acomodá-la.

• Para a criação do espaço de armazenamento basta que se aloque (estaticamente via declaração do tamanho do array no programa ou de maneira dinâmica via malloc).
• A construção da árvore se dá via a inserção dos elementos da árvore no array seguindo o modelo de numeração de nós visto no tópico anterior.

A implementação de árvores binárias via array serve para resolver problemas os quais todos os elementos da árvore são conhecidos a priori. O ponto chave na solução de tais problemas recai na busca de itens dentro da estrutura da árvore, que em muitos casos pode ser consideravelmente mais rápido do que a busca linear ou seqüencial.

Busca em Árvores Binárias

Não existe uma ordem “natural” para se percorrer uma árvore binária. . No entanto três formas básicas de busca são definidas:

• Ordem Anterior (percurso em profundidade)
• Ordem (ou em ordem simétrica)
• Ordem Posterior

As formas de busca aqui descritas possuem implementação intuitiva via algoritmos recursivos.

Em ordem anterior, também chamada de busca PreOrdem ou busca em profundidade, os elementos da árvore são inspecionados a partir da raiz e da esquerda para a direita. direita Cada nó visitado tem seu valor inspecionado A busca continua até que um nó folha da esquerda é encontrado. Neste momento a busca passa a acessar os elementos da direita.

Na busca emOrdem, os elementos da árvore são inspecionados a partir da raiz e da esquerda para a direita até que um nó folha seja encontrado (nó sem filhos). A partir deste momento o nó é acessado a busca então analisa o no da direita. O processo continua recursivamente percorrendo toda a árvore.

Na busca em ordem posterior ou pós ordem a idéia é construir uma árvore de chamadas de função recursiva na pilha em que todos os elementos ele mentos da esquerda não percorridos seguidos dos elementos da direita. A diferença reside no fato de que os elementos só serão acessados a partir do momento em que a recursão atingir a condição de parada. Desta forma os elementos serão acessados na ordem inversa versa a qual eles foram percorridos.

Implementando Árvores Binárias Usando Nós Dinâmicos Ligados

Para implementar uma árvore binária baseada em nós dinâmicos faz-se faz se necessário:

• Definir uma estrutura de dados capaz de acomodar os dados a serem organizados sob a forma de uma árvore binária;
• Definir nesta estrutura ponteiros para as sub-árvores sub árvores da esquerda e da direita;
• Definir a interface ou lista de métodos que manipularão tal estrutura.

1class No {
2    int dado;
3    int level;
4    No direita;
5    No esquerda;
6}

Árvore com link para o nó pai. Isso permite que não precisemos utilizar recursividade:

1class No {
2    int dado;
3    int level;
4    No pai;
5    No direita;
6    No esquerda;
7}

A estrutura acima define um nó para uma árvore binária. Note que com a inclusão do campo int level (nível) permite a identificação de em que nível da árvore o nó se encontra.

Métodos/funções para Árvores Binárias Dinâmicas

• inserir à direita
• inserir à esquerda
• retirar da direita
• retirar da esquerda
• juntar uma árvore à outra
• tamanho da árvore
• verifica se é folha
• retorna árvore da esquerda
• retorna árvore da direita
• outros...

Exercícios

1. Para que tipo de problemas árvores são a estrutura de dados indicada? De exemplos.

2. Desenhe uma árvore qualquer e identifique na mesma os vários termos relativos á árvores tal como nó pai, nó filho, folha, etc....

3. Implemente uma estrutura de dados para acomodar árvores binárias completas e quase completas. Use um array para armazenamento dos dados da árvore; (para este exercício algumas decisões de codificação deverão ser tomadas, por exemplo o número N de elementos no array)

a. Escreva uma função que crie uma árvore binária;

b. Escreva uma função que insira um novo elemento nesta árvore;

c. Crie uma função que construa uma árvore binária a partir de uma lista de números. Esta função deve retornar todos os elementos repetidos na lista;

d. Discuta o problema de não balanceamento decorrente da ordem em que os elementos são inseridos na árvore binária do exercício anterior. Utilize um exemplo para exemplificar o problema;

4. Delineie uma função que teste se uma árvore binária é completa ou quase completa;

5. Porque desejamos que uma árvore binária seja quase completa? (dica, tem a ver com facilidade de implementação) Descreva como podemos calcular o índice dos elementos de uma árvore se a mesma for quase completa e representada por meio de um array;

6. Implemente a função para busca em árvores binárias entitulada PreOrdem;

7. Implemente a função para busca em árvores binárias entitulada emOrdem;

8. Implemente a função para busca em árvores binárias entitulada PosOrdem;

9. Implemente uma função que receba duas arvores binárias e retorne uma árvore binária composta pelas duas fornecidas. (uma arvore será a sub-árvore direita e a outra a esquerda)