Curso Online de Algoritmos e Estruturas de Dados: Árvores

Valdey valente silva FAPEN
Ciencia da computação

Algoritmos e Estruturas de Dados
Aula 02: Arvores

Árvores

Árvores

Utilizadas em muitas aplicações
Modela uma hierarquia entre elementos
Árvore genealógica
Diagrama hierárquico de uma organização
Modelagem de algoritmos
O conceito de árvores está diretamente ligado à recursão

Árvores

Um conjunto finito de elementos onde
um elemento é chamado de raiz
os outros são divididos em subconjuntos disjuntos, onde cada um define uma árvore
cada elemento é um nó ou vértice da árvore
arcos ou arestas conectam os vértices

Árvores

Uma coleção não vazia de vértices e ramos que satisfazem a certos requisitos
vértice (ou nó):
é um objeto simples que pode ter um nome e mais alguma outra informação associada
arco ou aresta (direcionado ou não):
é uma conexão entre dois nós

Representação

Terminologia e Propriedades

cada vértice (exceto a raiz) tem exatamente um antecessor imediato ou pai
cada vértice tem nós sucessores imediatos ou filhos, a não ser:
nós sem filhos  terminais ou folhas ou externos
filhos de um mesmo pai - irmãos
nós com pelo menos um filho  não-terminais ou internos

Terminologia e Propriedades

caminho em uma árvore:
é uma lista de vértices distintos e sucessivos, conectados por arcos (arestas) da árvore
nó raiz
existe exatamente um caminho entre a raiz e cada um dos nós da árvore
se existir mais de um caminho ou nenhum grafo

Terminologia e Propriedades

grau
é o número de subárvores de um nó
no exemplo: grau de A é 3; de N é 4; de J é 1
qualquer nó é a raiz de uma sub-árvore consistindo dele e dos nós abaixo

Árvores

Árvores

A única diferença entre as duas árvores é a ordem das sub-árvores
Uma árvore ordenada é definida como uma árvore onde as sub-árvores formam um conjunto ordenado
Em uma árvore ordenada define-se o primeiro, segundo e último irmão, de acordo com alguma propriedade