Estrutura de Dados I - Arvore

Estrutura de Dados I - Arvore

(Parte 1 de 6)

Estrutura de Dados I Árvore

Profa Karina Oliveira kkco@dei.unicap.br

Estrutura de Dados I - Karina Oliveira2

Introdução

•Estruturas de dados lineares (pilha, fila) são estruturas que guardam coleções de elementos que são acessados sequencialmente.

•Efetivamente são chamadas lineares porque cada elemento tem um único sucessor.

•Em muitas aplicações a organização dos elementos apresenta-se não linear, dado que qualquer membro pode apresentar múltiplos sucessores.

Estrutura de Dados I - Karina Oliveira3

Árvores

•Uma das mais importantes classes de estruturas de dados em computação

•Aproveitando-se de sua organização hierárquica, muitas aplicações são realizadas usando-se algoritmos relativamente simples, recursivos e de eficiência bastante razoável.

•Veremos os conceitos básicos desta estrutura de dados e estudaremos as árvores binárias de busca, usadas em aplicações de busca em memória principal.

Estrutura de Dados I - Karina Oliveira4

Árvores - Definição

•Árvore é uma estrutura de dados bidimensional, não linear.

•Possui um conjunto finito de elementos (N ≥ 0), denominados nós ou vértices

–Se N = 0, dizemos que a árvore é nula;

–Se N > 0, então: •Há um nó especial denominado raiz da árvore;

•Os demais nós formam conjuntos disjuntos T1,

..., Tm, onde cada um destes conjuntos é também uma árvore;

–As árvores Ti são denominadas subárvores.

Estrutura de Dados I - Karina Oliveira5

Representação Gráfica de uma Árvore

Árvore Generalizada ...

Estrutura de Dados I - Karina Oliveira6

Representação Gráfica de uma Árvore

I J T1

Raiz • Exemplo:

Estrutura de Dados I - Karina Oliveira7

•A raiz da árvore é pai da raiz de cada subárvore e a raiz de cada subárvore é filha da raiz da árvore.

•Na árvore ao lado:

–A raiz é o nó A; –O nó A é pai dos nós B, C e D;

–Os nós B, C e D são raízes de cada uma das subárvores;

–O nó B tem 3 filhos: E, F e G;

–Os nós E, F e G são irmãos;

–Nós sem filhos são chamados de folhas: E, K, G, L, M, I e J;

I J T1

Raiz

Árvores - Terminologia

Estrutura de Dados I - Karina Oliveira8

Árvores - Terminologia

•O caminho de um nó n1 para um nó nk é definido como a seqüência de nós n1,n2,..,nk, tal que ni é o pai de ni+1 para 1 ≤ i < k.

–Observe que em uma árvore só existe um caminho da raiz até qualquer nó.

•O comprimento deste caminho é o número de arcos no caminho, ou seja, k-1.A

Estrutura de Dados I - Karina Oliveira9

Árvores - Terminologia

•Para qualquer nó ni, a profundidade ou nível de ni é o comprimento do único caminho da raiz para ni.. A raiz tem nível zero.

•A altura de ni é o maior caminho de ni para uma folha

–Assim, todas as folhas tem altura zero.

–Altura da árvore é igual a altura da raiz.A

(Parte 1 de 6)

Comentários