Estruturas de Dados - Busca - Parte 3 (Dibio)

Prévia do material em texto

dibio@unb.br
Assuntos 
● Árvores de Pesquisa (Busca)
● Árvores Binárias de Pesquisa
– Características
– Sem Balanceamento
– Exemplos (TADs)
dibio@unb.br
Árvores de Pesquisa
● Estrutura de dados eficiente para armazeanr 
informação
● Particularmente adequada, quando necessita-se de:
– Acesso direto e sequencial eficientes;
– Facilidade de inserção e retirada de registros
– Boa taxa de utilização de memória;
– Utilização tanto de memória primária quanto secundária;
dibio@unb.br
Se Pesquisa Binária é mais 
eficiente, como usar em árvore?
● Estrutura de vetor não é adequada, pois inserções e 
retiradas exigem reorganização dos elementos.
● É necessário ter uma estrutura dinâmica para tal 
tarefa.
dibio@unb.br
Árvore Binária de Pesquisa sem 
Balanceamento
dibio@unb.br
Árvore Binária de Pesquisa sem 
Balanceamento (ex)
● O nível do nó raiz é 0
– Se um nós está no nível i, a raiz de suas sub-árvores 
estão no nível i + 1
– A altura de um nó é o comprimento do caminho mais 
longo deste nó até um nó folha
– A altura de uma árvore é a altura do nó raiz
dibio@unb.br
Exemplo (TAD Dicionário para 
Árvore Binária sem 
balanceamento)
dibio@unb.br
Procedimento para pesquisar na 
árvore
● Para encontrar um registro com uma chave x:
– Compare-a com a chave que está na raiz
● Se x for menor, ir para sub-árvore esquerda
● Se x for maior, ir para sub-árvore direita
– Repita o processo recursivamente até que a chave seja 
encontrada, ou um nó folha atingido
– Se a pesquisa tiver sucesso, então o conteúdo do registro 
retorna no próprio registro x 
dibio@unb.br
Busca/Pesquisa em Árvores 
Binárias de Busca (Versão 
recursiva)
dibio@unb.br
Busca/Pesquisa em Árvores 
Binárias de Busca (Versão 
iterativa)
dibio@unb.br
Procedimento para pesquisar na 
árvore
dibio@unb.br
Procedimento para pesquisar na 
árvore ( Ex: em C)
dibio@unb.br
Procedimento para inserção na 
árvore 
dibio@unb.br
Procedimento para inserção na 
Árvore Binária de Busca 
dibio@unb.br
dibio@unb.br
Procedimento para inserção na 
árvore (Ex: em C)
dibio@unb.br
Procedimento para inicializar 
árvore (em C)
dibio@unb.br
Procedimento para retirar 
elemento da árvore
● Para realizar a retirada de um nó, em geral há duas 
situações:
– se o nó que contém o registro a ser retirado possuir no 
máximo um descendente (retirada direta)
– se o nó tiver dois descendentes, deve-se primeiramente:
● substituir o registro pelo que estiver mais à direita na sub-
aŕvore esquerda
● ou, substituir o registro pelo que estiver mais à esquerda na 
sub-árvore direita
dibio@unb.br
dibio@unb.br
dibio@unb.br
cont.
dibio@unb.br
Exemplo de retirada
dibio@unb.br
Exemplo de retirada
dibio@unb.br
Exemplo de retirada (em C)
dibio@unb.br
Exemplo de retirada (em C)
dibio@unb.br
Exemplo de retirada (em C) cont.
dibio@unb.br
Exemplo de retirada (em C) cont.
dibio@unb.br
Exemplos (retiradas)
dibio@unb.br
Exemplos (retiradas)
dibio@unb.br
Caminhamento central para 
Árvores Binárias de Pesquisa
dibio@unb.br
Exemplo (Caminhamento Central)
dibio@unb.br
Caminhamento Central (em C)
dibio@unb.br
Comentários 
dibio@unb.br
Referências
● Celes, W.; Cerqueira, R. & Rangel, J.L. 
 Introducão a Estruturas de Dados, Editora 
 Campus (Elsevier), RJ, 2004.
● Cormen, T.; Leiserson, C. & Rivest, R. 
 Algoritmos: teoria e prática, Campus Editora, RJ, 
 2002.
● Tenenbaum, A.; Langsam, Y. & Augenstein, M. 
 Estruturas de Dados usando C, Makron Books, 
 RJ, 1995.
● Ziviani, N. Projetos de Algoritmos com 
Implementações em Pascal e C, Cengage 
Learning, SP, 2004.
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33