rvores de Pesquisa Binrias Centro de Inform-ca Universidade
Federal de Pernambuco Sistemas de Informao Vinicius Cardoso Garcia
[email protected]
2011 Vinicius Cardoso Garcia
Introduo Uma rvore de pesquisa binria so estruturas de dados que
admitem operaes em conjuntos dinmicos, como: Search Minimum Maximum
Predecessor Sucessor Insert Delete Algoritmos e Estrutura de Dados
rvores de Pesquisa Binria 2011 Vinicius Cardoso Garcia
2
Operaes Bsicas X Custos De forma geral, as operaes bsicas em uma
rvore binria so proporcionais a sua altura Para uma rvore binria
completa: Custo em tempo (lgn)
Para uma rvore que uma cadeia linear de ns: Custo em tempo
(n)
Algoritmos e Estrutura de Dados rvores de Pesquisa Binria 2011
Vinicius Cardoso Garcia
3
rvore Binria de Pesquisa Uma rvore binria T em que cada nodo
>
interno v de T armazena um elemento (k, x) que: As chaves
armazenadas na subrvore esquerda de v so menores ou iguais a k As
chaves armazenadas na subrvore direita de v so maiores ou iguais a
k 6 chave[x].
Concre-zao de um dicionrio ordenado Representao hierrquica da
ordenao de suas chaves por meio da relao pai e lho Um caminhamento
interxado dos nodos de uma rvore binria de pesquisa T dever visitar
as chaves em ordem no-decrescente Algoritmos e Estrutura de Dados
rvores de Pesquisa Binria 2011 Vinicius Cardoso Garcia
5
Operaes sobre ABB As principais operaes so: Pesquisa Insero
Remoo
As operaes insero e remoo devem ser realizadas respeitando a
propriedade das ABP.
Algoritmos e Estrutura de Dados rvores de Pesquisa Binria 2011
Vinicius Cardoso Garcia
6
Pesquisa Pesquisa com sucesso. Exemplo: Na ABP abaixo, pesquisar
os dados referenciados pelo n de valor 3.
4
4
1
6
1
3 2
5
7
3
Algoritmos e Estrutura de Dados rvores de Pesquisa Binria 2011
Vinicius Cardoso Garcia
7
Pesquisa Pesquisa sem sucesso. Exemplo: Na ABP abaixo, pesquisa
os dados referenciados pelo n de valor 9.
4
4
1
6
6
3 2
5
7
7
Algoritmos e Estrutura de Dados rvores de Pesquisa Binria 2011
Vinicius Cardoso Garcia
8
Pesquisa Para pesquisar por uma chave k, devemos traar um
caminhamento comeando da raiz O prximo nodo visitado depende do
resultado da comparao de k com a chave do nodo corrente Se
alcanarmos uma folha, a chave no encontrada e retornamos null
Exemplo: nd(4) Call TreeSearch(4, root) Algorithm TreeSearch(k, v)
if T.isExternal (v) return v if k < key(v) return TreeSearch(k,
T.left(v)) else if k = key(v) return v else { k > key(v) }
return TreeSearch(k, T.right(v))
w6 8
2 1 4 5 8
9
w
Algoritmos e Estrutura de Dados rvores de Pesquisa Binria 2011
Vinicius Cardoso Garcia
14
Remoo Trs casos dis-ntos a serem tratados: n a ser removido tem
zero, um ou dois lhos.
Algoritmos e Estrutura de Dados rvores de Pesquisa Binria 2011
Vinicius Cardoso Garcia
15
Remoo Caso 1 Caso 1: nodo a ser removido tem zero lhos
Simplesmente remove o nodo raiz 10 4 16 8 3 7 9 11 12 1 4 raiz 10
16 8 3 7 9 12
21
2
Aps a remoo
Algoritmos e Estrutura de Dados rvores de Pesquisa Binria 2011
Vinicius Cardoso Garcia
16
Remoo - Caso 2 Caso 2: nodo a ser removido tem um lho
Subs-tui o nodo por seu lho raiz 10 4 16 8 3 7 9 12 11 1 4 raiz
10 16 8 3 7 9 11
21
2
Aps a remoo
Algoritmos e Estrutura de Dados rvores de Pesquisa Binria 2011
Vinicius Cardoso Garcia
17
Remoo Caso 3 Caso 3: nodo a ser removido tem dois lhos
Subs-tui o nodo por seu sucessor raiz 10 4 16 8 3 7 9 12 11 1 7
raiz 10 16 8 3 9Aps a remoo
21
2
11
nodo sucessor
Pergunta: Poderamos ter feito a substituio pelo nodo
antecessor?Algoritmos e Estrutura de Dados rvores de Pesquisa
Binria 2011 Vinicius Cardoso Garcia
18
Nodo Sucessor e Antecessor Considerando que as chaves sejam
todas dis-ntas: O sucessor de um nodo x o nodo y, tal que chave[y]
o menor valor maior que chave[x]. O antecessor de um nodo x o nodo
y, tal que chave[y] o maior valor menor que chave[x]. Algoritmos e
Estrutura de Dados rvores de Pesquisa Binria 2011 Vinicius Cardoso
Garcia
19
Anlise de complexidade Com relao a pesquisa Depende da quan-dade
de ns internos que eu precise visitar. Qual a complexidade de uma
busca com sucesso? Depende da ordem de insero dos ns ao construir
uma ABP. 4, 6, 2, 5, 1, 7, 3 1, 2, 3, 4, 5, 6, 7
Figura 1 Figura 2Algoritmos e Estrutura de Dados rvores de
Pesquisa Binria 2011 Vinicius Cardoso Garcia
20
Anlise de complexidade Complexidade de uma busca sem sucesso
Melhor Caso: rvore binria perfeita: O(log n) Figura 1 rvore no
balanceada: O(n) Figura 2 4, 6, 2, 5, 1, 7, 3 1, 2, 3, 4, 5, 6,
7
Figura 1 Figura 2
Algoritmos e Estrutura de Dados rvores de Pesquisa Binria 2011
Vinicius Cardoso Garcia
21
ASvidades Complementares Leitura do captulo 12 do livro do
Cormen Implementar uma classe rvore de pesquisa binria com as funes
search, maximum, minimum, sucessor, predecessor, inserir e
deletar.
Algoritmos e Estrutura de Dados rvores de Pesquisa Binria 2011
Vinicius Cardoso Garcia
22
