Algorítmos e estrutura de
dados III
Carlos Oberdan Rolim
Ciência da Computação
Árvores binárias
Árvore binária
Uma árvore binária é uma árvore com as seguintes
propriedades:
Cada nó interno tem, no máximo, dois filhos
Os filhos de um nó é um par ordenado
Chamamos os filhos de um nó de filho da esquerda e filho
da direita
Árvore binária
O número de folhas é uma importante característica das árvores
binárias para mensurar uma eficiência esperada de algoritmos.
Árvore estritamente binária: quando todo nó que não é folha
tiver subárvore direita e esquerda não vazios
Árvore binária completa: se todos os nós em todos os níveis,
exceto o último, tiverem 2 filhos.
A
A
B
D
B
C
E
Árvore binária estritamente binária
D
C
E
F
H
Árvore binária completa
Árvores binárias
Podemos, também, definir uma árvore binária
recursivamente como:
uma árvore consistindo de um único nó, ou
Uma árvore cuja raiz tem um par ordenado de filho,
cada um dos quais é uma árvore binária
Cuidado na hora de representar árvore para podermos
saber se é o filho direito ou esquerdo de seu pai
A
B
Árvore binária
Aplicações:
A
Expressões aritméticas
Processo de decisão
B
C
busca
D
F
E
H
I
Árvore de expressões aritméticas
Árvore binária associada com uma expressão aritmética
Nós internos: operadores
Nós externos: operandos
Exemplo: árvore da expressão aritmética para a expressão
(2  (a - 1) + (3  b))
+


-
2
a
3
1
b
Árvore de decisão
Árvore binária associada com um processo de decisão
Nós internos: questões com respostas sim/não
Nós externos: decisões
Exemplo: Onde jantar
Refeição rápida?
Não
Sim
Que tal um café?
Pode ser caro?
Sim
Não
Sim
Não
Cantina
Shopping
Abade
Tábua de carne
Propriedades de AB (BT)
Notação
n número de nós
Propriedades:
e=i+1
n = 2e - 1
e número de nós
externos
hi
i número de nós
internos
h  (n - 1)/2
h altura (height)
e  2h
h  log2 e
h  log2 (n + 1) - 1
Propriedades de AB (BT)
Nível
0
Nós
1
2
2
4
3
8
1
Número máximo de nós em um nível h é 2h
Pode haver, 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.
Número total de nós é, no máximo é 2h+1 -1