ARVORES

Disponível somente no TrabalhosFeitos
  • Páginas : 7 (1671 palavras )
  • Download(s) : 0
  • Publicado : 13 de dezembro de 2013
Ler documento completo
Amostra do texto
Estruturas de Dados
Árvores
Prof. Ricardo J. G. B. Campello

Créditos
Parte deste material consiste de:
Adaptações dos slides gentilmente cedidos
pela Profa. Maria Cristina F. de Oliveira
Adaptados dos originais de Walter Aoiama Nagai
e M. Graças Volpe Nunes

Adaptações e extensões dos originais de
Goodrich & Tamassia
Disponíveis em http://ww3.datastructures.net/

2

1 Introdução
Problema:
Listas Lineares
Lista Encadeada
Eficiente para inserção e remoção dinâmica de elementos,
mas ineficiente para busca

Lista Seqüencial (ordenada)
Eficiente para busca, mas ineficiente para inserção e
remoção de elementos

Possível Solução:
Árvores
Eficientes para inserção, remoção e busca
Representação não linear...
3

Introdução
Em computação, uma
árvore é ummodelo
abstrato de uma
estrutura hierárquica.
Trata-se de uma
estrutura não-linear
constituída de nós
com relações de
parentesco (pai-filho).
Aplicações:

ABC Computadores

Vendas

BR

Europa

Produção

Internacionais

Asia

Laptops

P&D

Desktops

EUA

S.O.s (arquivos).
Linguagens (O.O.).
etc
4

2

Introdução
Árvores são adequadas para representar
estruturashierárquicas não lineares, como
relações de descendência
pai, filhos, irmãos, etc.

Homer Simpson

Bart

Lisa

Maggie

5

Definição

RT
T1

T2

...

Tn

Árvore T: conjunto finito de elementos,
denominados nós, nodos ou vértices, tais que:
Se T = ∅ a árvore é dita vazia;
Caso Contrário:
(i) T contém um nó especial, denominado raiz (RT);
(ii) Os demais nós, ouconstituem um único conjunto vazio, ou
são divididos em n conjuntos disjuntos não vazios
(T1,T2,…,Tn), que são, por sua vez, cada qual uma árvore;
T1,T2,…,Tn são chamadas sub-árvores de RT;
6

3

Terminologia
Se um nó Y é raiz de uma sub-árvore de um
nó X, então X é PAI de Y e Y é FILHO de X
Dois nós são IRMÃOs se são filhos do
mesmo pai
Se os nós Y1, Y2, ..., Yj são irmãos, e o nó Z
é filhode Y1, então Y2,...,Yj são TIOs de Z
7

Exemplo
Nós: A, B, C, D, E, F, G
RAIZ da
árvore
FILHOS
DE A

E

A

B

C

F

FILHOS
DE B

Folhas: E,F,C,G

D

G

FILHO
DE D

8

4

Terminologia
Raiz (root): nó sem pai (A).
Nó Interno: nó com pelo
menos um filho (A, B, C, F).
A

Nó Externo ou Folha: nó
sem filhos (E, I, J, K, G, H, D).
Ancestrais (de um nó): paiou ancestrais do pai do nó.
Descendentes (de um nó):
nós que o possuem como
ancestral.
Sub-Árvore: árvore
consistindo de um nó e dos
seus descendentes.

B

E

C

F

I

J

G

D

H

K

9
Sub-árvore

Exemplo
ANCESTRAIS DE G

TIOS de F e E

A
C

D

B

NÓS
IRMÃOS

DESCENDENTES
DE A

G

F

E
10

5

Terminologia
O NÍVEL de um nó X é definidocomo:
O nível de um nó raiz é 1
O nível de um nó não raiz é dado por
Nível de seu nó PAI + 1

O GRAU de um nó X pertencente a uma
árvore é igual ao número de filhos de X
Se X é folha, então Grau(X) = 0

O GRAU de uma árvore T é o maior entre
os graus de todos os seus nós
11

Exemplo:

NÍVEL 1

NÍVEL 2

B

F

G

H

M

N

O

P

NÍVEL 5

A
C

D

NÍVEL 3

INÍVEL 4

E
J

K

L

Grau de A: 4
Grau de B: 3
Grau de C: 0
Grau de M: 1
Grau da Árvore: 4
12

6

Terminologia

A

Profundidade (de um nó):
número de ancestrais.

B

C

D

Raiz possui profundidade zero.

Altura (de uma árvore): máxima
profundidade de qualquer nó.

E

F

G

H

Exemplo ao lado ⇒ 3.
I

Altura (de um nó): altura da
sub-árvore com raiznaquele nó.
Folhas possuem altura zero.
Raiz possui altura da árvore.

Profundidade (de uma árvore):
máx. profundidade de uma folha.

J

K

Nota: Terminologia não é universal!
Alguns autores consideram como 1
Sub-Árvore
(ao invés de zero) a altura das folhas
e a profundidade da raiz, o que altera
as demais definições.

Equivalente à altura.
13

Exemplo:

A
B

F

G

C...
tracking img