Olhar Digital - Últimas Notícias

segunda-feira, 30 de agosto de 2010

Estrutura de dados - árvores



Nomenclatura

- Raiz: é o nó de mais alto nível da árvore (primeiro nó da árvore);
- Folha: nó com grau igual a zero;
- Nível: é o número de nós que vai da raiz até um determinado nó;
- Altura: Nível mais alto da árvore;
- Pai: a raiz de uma subárvore é pai das raízes de suas subárvores;
- Filho: os nós-raízes de uma subárvore; e
- Irmão:  nós raízes das subárvores de mesmo nível.




"Especialistas em produtividade dizem que as soluções são obtidas pensando-se de maneira não-linear."

Afinal, o que significa não-linear já tão defendido por especialistas?
São relacionamentos organizacionais mais ricos que simples relações do "antes" e "depois" entre objetos em uma sequencia.

Atalho na organização de dados: permitem implementar uma série de algoritmos de forma mais rápida do que usando estruturas de dados lineares, tais como listas, vetores ou sequencias.

OS RELACIONAMENTOS PODEM SER HIERÁRQUICOS

Ex: árvores genealógicas.


TIPO ABSTRATO DE DADOS ÁRVORE

Uma árvore é um tipo abstrato de dados que armazena elementos de maneira hierárquica. Com excessão do elemento do topo (raiz), cada elemento da árvores tem um elemento pai e zero ou mais elementos filhos.

Estrutura de dados contendo um número finito de elementos que pode estar vazia ou particionada em subconjuntos. O primeiro subconjunto contém um único elemento chamado raiz. Os outros subconjuntos são, em si mesmo árvores, chamados subárvores. Essa é um definição recursida de árvore.

árvore > raiz + árvores
                    > raiz + árvores                       
                                    > ...


PROPRIEDADES BASICAS E TERMINOLOGIA

Uma árvore T é um conjunto de nós que armazena elementos em relacionamentos pai-filho com as seguintes propriedades:

* T tem um nó especial r, chamado de raiz de T;
* Cada nó v e T diferente de r tem um nó pai u.

Propriedades:

* Se um nó u é pai de nó v, então dizemos que v é filho de u;
* Dois nós que são filhos do mesmo pai são irmãos;
* Um nó é externo se não tem filhos e são conhecidos com folhas;
* Um nó é interno se tem um ou mais filhos;


Na maioria dos sistemas operacionais, os arquivos são organizados de forma hierárquica utilizando o conceito de diretório ou pasta. As pastas, nessa árvore hierárquica de diretório, representam os nós internos, enquanto que os arquivos são os nós externos.

* Uma subárvore de T enraizada no nó v é a árvore formada por todos os descendentes de v em T (incluindo o próprio v);
* O ancestral de um nó é qualquer nó acima de sua hierarquia que possui relação de pai como seu pai ou o pai dele e assim sucessivamente;
* O descendente segue o mesmo conceito de forma inversa



A relação de herança entre classes de um programa java forma uma árvore. A classe java.lang.Object é ancestral de todas as demais classes.

* Uma árvore é ordenada se existe uma ordem linear definida para os filhos de cada nó, ou seja, se podemos identificar os filhos de um nó como sendo o primeiro, segundo, terceiro e assim por diante. tal ordenação é determinada pelo uso que se quer dar a árvore;
*  Uma árvore binária é uma árvore ordenada na qual todo nó tem, no máximo dois filhos:

video 



+ uma árvore binária é própria se cada um dos seus nós tiver zero ou dois filhos;
+ para cada nó interno de uma árvore binária, nomeamos cada filho como filho da esquerda e filho da direita;
+ as subárvores enraizadas no filho da esquerda ou da direta. são chamadas de subárvore esquerda e subárvore direita, respectivamente.

árvore de decisão sobre escolaridade



árvore de decisão sobre expressão aritmética

MÉTODOS DE ÁRVORES

O TAD árvore armazena elementos em posições, como as de uma lista, que são definidas em relação às posições de seus vizinhos. As posições de uma árvore são seus nós, e o posicionamento pela vizinhança satisfaz as relações pai-filho que definem uma árvore válida. Como as posições de uma lista, um objeto posição para uma árvore suporta os métodos:

elemento(): retorna o objeto nesta posição
entrada: nenhuma
saida: objeto

raiz(): retorna a raiz da árvores
entrada: nenhuma
saída: posição

filhos(): retorna um iterador sobre os filhos do nó v.
entrada: posição
saída: iterador de posição

Além dos métodos de acesso fundamental acima, pode-se apresentar os seguintes métodos de consultas:

ehinterno(): testa se um nó v é interno
entrada: posição
saída: booleano

ehexterno(): testa se um nó v é externo
entrada: posição
saída: booelano
 
ehraiz(): testa um nó v é raiz
entrada: posição
saída: booleano

INTERFACE SIMPLES de uma árvore em java

public interface arvore {
 
// método de acesso
               public No raiz();
               public No pai(No v);
               public No filhos (No v);
// métodos de consulta
              public boolean ehInterno();
              public boolean ehExterno();
              public boolean ehRaiz()
}

Nenhum comentário:

Postar um comentário