ARVORES

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 é um modelo 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 estruturas hierá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, ou constituem 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 é filho