ARVORES
Á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