Estrutura de Dados e Algoritmos
e
Programação e Computadores II
Aula 7: Árvores
Árvores





Conceitos e terminologia
Árvores binárias
Árvores-B
Inclusão e Exclusão
Introdução aos grafos
Árvores



As listas ligadas usualmente fornecem maior
flexibilidade do que as matrizes, mas são
estruturas lineares e é difícil usá-las para organizar
uma representação hierárquica de objectos.
Pilhas e Filas limitam-se a somente uma
dimensão.
A árvore consiste de nós e arcos, que ao inverso
das árvores naturais são representadas de cima
para baixo, com a raiz no topo e as folhas na
base.
Árvores



A raiz é um nó que não possui ancestrais; ele só
possui nós filhos.
As folhas não possuem nós filhos, ou seus filhos
são estruturas vazias.
Exemplo:
Árvores

Mais exemplos:
Árvores




Cada nó tem que ser atingível a partir da raiz
através de uma sequência única de arcos,
chamada de caminho.
O número de arco de um caminho é chamado de
comprimento do caminho.
O nível de um nó é o comprimento do caminho da
raiz ao nó mais 1, que é o número de nós no
caminho.
A altura de uma árvore não vazia é o nível máximo
de um nó na árvore.
Árvores


O número de filhos permitido
por nó e as informações
armazenadas em cada nó
diferenciam os diversos tipos
de árvores existentes.
Exemplo: na árvore da
expressão (3+6)*(4-1)+5 os
nós folhas possuem valores e
os nós intermediários
possuem operações
Árvores





O número de filhos de um nó é chamado grau de
saída desse nó.
Um nó folha é aquele com grau de saída nulo, ou
também nó terminal.
Um nó que não é folha (isto é, possui grau de
saída diferente de zero) é chamado nó interior ou
nó interno, ou também nó não-terminal.
O grau de uma árvore é o máximo entre os graus
de seus nós.
Uma floresta é um conjunto de zero ou mais
árvores.
Percurso em Árvores





O percurso em árvores é o processo de visitar
cada nó da árvore exactamente uma vez.
O percurso pode ser interpretado como colocar
todos os nós em uma linha.
Mas qual a ordem?
Existem n! percursos diferentes, quase todos
caóticos.
Os básicos são percurso em profundidade e
percurso em extensão (largura).
Percurso em Árvores




Um percurso em extensão é visitar cada nó
começando do menor nível e move-se para os
níveis mais altos nível após nível, visitando cada
nó da esquerda para a direita.
Sua implementação é directa quando uma fila é
utilizada.
Depois que um nó é visitado, seus filhos, se
houver algum, são colocados no final da fila e o
nó no início da fila é visitado.
Assim, os nós do nível n+1 serão visitados
somente depois de ter visitados todos os nós do
nível n.
Percurso em Árvores

Breadth - First Search (BFS)
Fila: 13
13
Fila: 10, 25
10
2
Fila: 25, 2, 12
25
12
20
Fila: 2, 12, 20, 31
31
29
Percurso: 13, 10, 25, 2, 12, 20, 31, 29
Fila: 12, 20, 31
Fila: 20, 31
Fila: 31
Fila: 29
Percurso em Árvores


O percurso em profundidade prossegue tanto
quanto possível à esquerda (ou direita), então se
move para trás até a primeira encruzilhada, vai
um passo para a direita (ou esquerda) e
novamente, tanto quanto possível, para a
esquerda (ou direita).
Repete-se este processo até que todos os nós
sejam visitados.
Percurso em Árvores

Depth - First Search (DFS)
V – Visitar um nó
L – Percorrer à esquerda
R – Percorrer à direita
13
10
2
25
12
20
31
29
VLR VRL
LVR RVL
LRV RLV
Percurso em Árvores
V
V
a
b
e
c
e
c
d
h
d
g
f
j
f
k
m
i
g
l
j
i
h
b
a
k
Árvores Binárias



Uma árvore binária é uma árvore cujos nós têm 2
filhos (possivelmente vazios) e cada filho é
designado como filho à esquerda ou filho à direita.
O número de folhas é uma importante
característica das árvores binárias para mensurar
uma eficiência esperada de algoritmos.
Uma árvore binária é conhecida como completa se
todos os nós em todos os níveis, excepto o último,
tiverem 2 filhos.
Árvores Binárias



Assim haveria, 20 = 1 nós no nível 1, 21 = 2 nós no
nível 2, 22 = 4 nós no nível 3 e, na forma geral, 2i
nós no nível i+1.
Para todas as árvores binárias não-vazias cujos
nós terminais tenham exactamente 2 filhos nãovazios, o número de folhas m será o número de
nós não-terminais k mais 1. (m = k + 1)
Se uma árvore tem somente uma raiz, essa
observação é trivialmente válida.
Árvores Binárias


Se ela for válida para uma certa árvore, então,
depois de anexar 2 folhas a uma das folhas já
existentes, essa folha se torna um nó não-terminal
(m é subtraído de 1 e k é adicionado de 1).
No entanto, 2 novas folhas são enxertadas na
árvore (m é adicionado de 2).
Árvores Binárias
k nós não-terminais
m folhas
k+1 nós não-terminais
m+1 folhas
Árvores Binárias de Busca

Para cada nó da árvore, todos os valores
armazenados em sua sub-árvore à esquerda são
menores que o valor armazenado no próprio nó, e
todos os valores armazenados na sub-árvore à
direita são maiores que o próprio nó.
K
A
13
10
P
N
R
2
25
12
20
31
29
Árvores Binárias de Busca






Um algoritmo para localizar um elemento nessa
árvore é bastante directo.
Para cada nó, compare a chave com o valor
armazenado no nó correntemente apontado.
Se for menor, vá para a sub-árvore à esquerda.
Se for maior, vá para a sub-árvore à direita.
Se for a mesma, a busca chegou ao fim.
Se não houver como continuar, a chave não está
na árvore.
Percurso em Árvores Binárias
void BreadthFirst() {
Queue q;
Node *p = root;
if (p != 0) {
q.enqueue(p);
while (!q.empty()){
p = q.dequeue();
visit(p);
if (p->left != 0)
q.enqueue(p->left);
if (p->right != 0)
q.enqueue(p->right);
}
}
}
Percurso em Árvores Binárias
void inorder(Node *p) {
if (p != 0) {
inorder(p->left);
visit(p);
inorder(p->right);
}
}
void preorder(Node *p) {
if (p != 0) {
visit(p);
preorder(p->left);
preorder(p->right);
}
}
void postorder(Node *p) {
if (p != 0) {
postorder(p->left);
postorder(p->right);
visit(p);
}
}
Árvores Binárias de Busca


Como será a inserção em uma árvore binária de
busca?
E como será a remoção em uma árvore binária de
busca?



No nó folha?
No nó raiz?
No nó intermediário?