AEDII-aula08

Prévia do material em texto

1
Aula 08 – Árvores binárias: algoritmos 
de varredura
MC3305
Algoritmos e Estruturas de Dados II
Prof. Jesús P. Mena-Chalco
jesus.mena@ufabc.edu.br
2Q-2014
2
Altura de uma árvore
3
Altura de uma árvore
Qual a relação entre a altura (h) e o número de nós de uma 
árvore binária?
4
Altura de uma árvore
Qual a relação entre a altura (h) e o número de nós de uma 
árvore binária?
n-1 ≥ h ≥ lg(n) 
5
Altura de uma árvore
Qual a relação entre a altura (h) e o número de nós de uma 
árvore binária?
n-1 ≥ h ≥ lg(n) 
6
Árvore binária balanceada
Árvore binária balanceada?
7
Árvore binária balanceada
Uma árvore binária é balanceada (ou equilibrada) se, em 
cada um de seus nós, as subárvores esquerda e direita, 
tiverem aproximadamente a mesma altura.
Uma árvore binária balanceada com n nós tem algura 
próxima lg(n).
Convém trabalhar com árvores balanceadas sempre que 
possível. Mas isso não é fácil se a árvore aumenta e 
diminui ao longo da execução do programa.
8
Exercícios:
Desenhe uma árvore binária que tenha conteúdos 1, . . . , 
17 e a menor altura possível. Repita com a maior altura 
possível.
Escreva uma função iterativa para calcular a altura de uma 
árvore binária.
Uma árvore é balanceada no sentido AVL se, para cada nó 
x, as alturas das subárvores que têm raízes x->esq e x->dir 
diferem de no máximo uma unidade.
Escreva uma função que decida se uma dada árvore é 
balanceada no sentido AVL.
Procure escrever sua função de modo que ela visite cada nó 
no máximo uma vez.
9
Nós, filhos e pais
10
Nós, filhos e pais
Escreva uma função que preencha corretamente todos os 
campos pai de uma árvore binária.
11
Nós, filhos e pais
Escreva uma função que preencha corretamente todos os 
campos pai de uma árvore binária.
12
Nó seguinte e anterior (sucessor e predecessor)
Escreva uma função que permita calcular o endereço do nó 
seguinte na ordem e-r-d.
Definição:
no *seguinte(no *x) 
13
Nó seguinte e anterior (sucessor e predecessor)
Escreva uma função que permita calcular o endereço do nó 
seguinte na ordem e-r-d.
14
Árvores binárias de pesquisa (ABP) 
15
Árvores binárias de pesquisa (balanceamento) 
Para qualquer nó que contenha um registro:
Temos a relação invariante:
16
Árvores binárias de pesquisa (balanceamento) 
17
Busca em uma Árvore Binária de Pesquisa
18
Busca em uma Árvore Binária de Pesquisa
19
Plantão de dúvidas
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19