Arvore

Conteúdo
1. Introdução
2. Listas
3. Pilhas e Filas
4. Árvores
5. Árvores de Pesquisa
• Árvore Binária e Árvore AVL
• Árvore N-ária e Árvore B
6. Tabelas de Dispersão (Hashing)
7. Métodos de Acesso a Arquivos
8. Métodos de Ordenação de Dados

Árvores

Árvore
ÁRVORE: Estrutura que armazena elementos de maneira hierárquica. Com exceção do elemento do topo, cada elemento da árvore tem um pai e zero ou mais filhos.

A

B

C

E

D

F

G

* o elemento topo é chamado de raiz da árvore, mas é desenhado como sendo o elemento mais alto.

Exemplos de Árvores
Livro x
Capítulo 1

Seção 1.1

Sub-seção 1.1.1

Capítulo 2

Seção 1.2

...

Sub-seção 1.1.2

...

Capítulo n

Seção 1.m

...

Sub-seção 1.1.k

Definição de Árvore
Uma árvore A é uma estrutura de dados tal que:
• se A não é vazia, existe um nodo raiz r;
• existem outros nodos n1, n2, ..., nm, m >= 0, associados a r que são raízes de subárvores disjuntas A1, A2, ..., Am.

r n1 n3

n2 n4 n5

n6

Propriedades das Árvores

Grau de um nodo
• Denotado por g(n)
• É o número de subárvores de um nodo.

A

B

C

E

D

F

G

Nodo Folha e Nodo Interno
• n é um nodo folha ou terminal se g(n) = 0
• m é um nodo interno se g(m) > 0

A

B

C

E

D

F

G

Caminho
• Um caminho C em uma árvore é uma seqüência de nodos relacionados na forma C = n1, n2, ..., nm, m > 0, sendo ni hierarquicamente superior a ni+1 .
• Comprimento de C = m – 1

A

B

C

E

D

F

G

Profundidade de um Nodo
• Denotado por p(n)
• p(n) = comprimento(C), sendo C = r, ..., n.

A

B

C

E

D

F

G

Nodo Pai e Nodo Filho
• Dados 2 nodos ni e nj, se existe um caminho a partir da raiz que passa por ni e nj e p(nj) = p(ni) + 1, então ni é nodo pai de nj e, conseqüentemente, nj é nodo filho de ni.

A

B

C

E

D

F

G

• Uma característica inerente às árvores é que todo nodo, exceto a raiz, tem