04. Arvore Binaria de Busca

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Árvore Binária de busca
Estrutura de Dados II
Introdução
A operação de busca de um elemento em um conjunto de dados é uma das operações mais frequentes da computação
Sistema Acadêmico
-------------------------
Matricula: 454
Aluno Encontrado
Nome: José Silva
Idade: 20 anos
Sexo: Masculino
454
José Silva
20 anos
Masculino
231
593
930
201
454
201
Introdução
Com listas lineares, foram utilizados três algoritmos de busca:
A Busca Linear
A Busca Linear Ordenada
A Busca Binária
Uma árvore binária de busca é uma estrutura de dados que permite a execução de uma busca binária em uma árvore
Árvore Binária de Busca
É uma árvore binária em que a chave de cada vértice:
É maior que a chave em cada vértice da sub-árvore esquerda
É menor que a chave em cada vértice da sub-árvore direita.
5
9
3
2
1
4
0
7
6
8
Árvores Binárias de Busca
Diferentes árvores binárias de busca podem ser construídas a partir das mesmas chaves
5
9
3
2
1
4
0
7
6
8
3
7
2
1
8
0
5
4
6
9
Árvores Binárias de Busca
É possível construir um algoritmo recursivo ou iterativo para fazer a busca em uma árvore binária de busca
A idéia é a mesma em ambos os casos:
Em cada iteração, exclui-se a sub-árvore esquerda ou direita da busca, dependendo do valor da raiz dessas sub-árvores:
Se a chave procurada é maior que a raiz, a busca continua na sub-árvore direita
Se a chave procurada é menor que a raiz, a busca continua na sub-árvore esquerda
Se a chave procurada é igual a raiz, encerra-se a busca
Implementação da Busca
Entrada: Um ponteiro para a raiz de uma árvore binária de busca T e a chave procurada x
Saída: Se x for encontrado, o ponteiro pt aponta para este vértice da árvore; ele aponta para nulo caso contrário 
Algoritmo: Busca em árvore binária de busca (iterativo)
 pt = raiz(T)
 enquanto (pt ≠ λ) e (x ≠ ptchave) faça
 | se x > ptchave então 
 | | pt = ptdir
 | senão 
 | | pt = ptesq
 retorne pt
7
3
8
1
2
ptraiz
λ
λ
5
λ
λ
4
λ
λ
6
λ
λ
9
λ
λ
λ
Esse algoritmos nos diz se a chave procurada está ou não na árvore.
7
Implementação da Busca
Algoritmo: Busca em árvore binária de busca (recursivo)
 função busca-arvore(x, pt)
 | se pt = λ então retorna 0
 | senão se x = ptchave então retorna 1
 | senão se x < ptchave então 
 | | se ptesq = λ então retorna 2
 | | senão 
 | | | pt := ptesq 
 | | | busca-arvore(x, pt)
 | senão 
 | | se ptdir = λ então retorna 3
 | | senão 
 | | | pt := ptdir 
 | | | busca-arvore(x, pt)
 pt := ptraiz 
 resultado = busca-arvore(x, pt)
7
3
8
1
2
ptraiz
λ
λ
5
λ
λ
4
λ
λ
6
λ
λ
9
λ
λ
λ
Por que ver outro algoritmo de busca? Porque este é usado como base para a inserção de novos elementos na árvore.
8
Complexidade da Busca
O número de operações dentro da função busca-arvore é constante
O número de chamadas da função busca-árvore é igual ao número de nós existentes da raiz até o nó em que termina a busca
No pior caso (árvore ziguezague) a complexidade é O(n)
No melhor caso (árvore binária completa) a complexidade é Ω(log n)
Ω (Ômega) = melhor caso
O (Omicron) = pior caso
9
Inserção na Árvore de Busca
Algoritmo: Inserção em árvore binária de busca
 pt = ptraiz
 f = busca-arvore(x, pt)
 se f = 1 então
 | "inserção inválida"
 senão 
 | ocupar(novo)
 | novochave = x
 | novoinfo = valor
 | novoesq = λ
 | novodir = λ
 | se f=0 então ptraiz = novo
 | senão se f=2 então
 | | ptesq = novo
 | senão
 | | ptdir = novo
Construção da Árvore de Busca
Uma árvore binária de busca pode ser construída utilizando o algoritmo de inserção visto anteriormente: 
5
7
2
4
1
3
0
6
9
8
S = {5, 2, 7, 1, 6, 0, 8, 3, 9, 4}
Construção da Árvore de Busca
Dependendo da ordem de inserção dos elementos, a árvore gerada pode não ser ótima e resultar numa busca
com eficiência quase linear
8
9
7
6
1
3
0
5
2
4
S = {8, 9, 7, 1, 6, 0, 5, 3, 2, 4}
Construção da Árvore de Busca
Para construir uma árvore de busca ótima basta colocar as chaves numa ordem conveniente
A idéia consiste em, a cada passo, inserir na árvore alguma nova chave que seja de índice médio entre duas chaves si e sj já inseridas
A árvore completa é ótima para o problema da busca no caso em que a frequência de acesso aos nós são idênticas
Construção da Árvore de Busca
Em um caso real, como em acessos a registros de um banco de dados, existirão registros mais acessados que outros
Há interesse em construir uma árvore binária de busca que seja a melhor possível para um dado conjunto de chaves e freqüências de acesso
Solução: árvore de partilha
Resumo
A busca é uma das operações mais realizadas em aplicações computacionais
Em uma estrutura linear podem ser usados os algoritmos:
Busca Linear
Busca Linear Ordenada
Busca Binária
Uma árvore binária de busca é uma estrutura de dados que permite a execução de uma busca binária em uma estrutura hierárquica
A ordem de inserção dos elementos tem impacto no formato da árvore e consequentemente no desempenho da busca:
Pior caso O(n) e melhor caso Ω(log n)