5 - ARVORE BUSCA

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

*
*
DEQ/EE3 – FUNDAMENTOS DA ESTRUTURA DA INFORMAÇÃO
Departamento de Engenharia Química
Universidade Estadual de Maringá
Prof. Leonardo F. Costa
*
*
Construção de uma árvore binária de busca completa
A árvore completa é ótima para o problema de busca no caso em que as frequências de acesso aos diferentes nós são todas idênticas.
Em um caso real, essas frequências podem ser diferentes.
Se cada nó representar um registro em um banco de dados, alguns serão mais requisitados que outros.
*
*
Comprimento de caminho interno de T
Total de comparações necessário para o acesso a todas as chaves de uma árvore binária de busca (buscas com sucesso)
*
*
Buscas sem sucesso
Quando se efetua uma busca a algum elemento não pertencente a S, são realizadas também comparações que devem ser levadas em consideração.
*
*
Buscas sem sucesso
Seja R o conjunto de chaves x buscadas ao longo de toda a programação. 
j=1, ..., n-1
Os n+1 conjuntos Rj, 0 ≤ j ≤ n, representam os diferentes intervalos onde se localizam as chaves correspondentes às buscas sem sucesso.
*
*
Considerações de uma busca sem sucesso
Uma busca sem sucesso termina, necessariamente, em alguma subárvore vazia.
Os diferentes intervalos Rj ocorrem da esquerda para a direita em T, segundo valores crescentes de seus índices.
*
*
Representação dos intervalos Rj
Uma árvore com os nós externos incorporados é sempre estritamente binária. (cada nó possui 0 ou 2 filhos)
Nós internos: contém as chaves
Nós externos: intervalos Rj (folhas)
*
*
Número de comparações efetuadas em uma busca sem sucesso
A busca sem sucesso termina em algum nó externo Rk.
O número de comparações vai desde a raiz até Rk.
Como não há chave em Rk, a última comparação é feita com o pai de Rk.
Seja l’k o nível de Rk em T, o número de comparações correspondente a uma busca sem sucesso é igual a lk -1.
*
*
Comprimento de caminho externo de T
*
*
Valores médios de comparações efetuadas em operações de busca
Com sucesso
Sem sucesso
Quanto menores forem estes valores, melhor é a árvore T.
*
*
Relação entre os comprimentos dos caminhos interno e externo de uma árvore de busca binária 
*
*
ÁRVORES BINÁRIAS DE BUSCA
Introdução
Árvore Binária de Busca
Conceitos básicos, busca e inserção
Busca com frequência de acesso diferenciadas
Árvore de Partilha
Conceitos básicos
A busca em árvores binárias de partilha
Árvore binária de partilha ótima
*
*
Conceitos e Definições
Nesse caso, é estudado o problema da busca no caso geral em que as chaves apresentam frequências de acesso distintas.
Objetivo é determinar a árvore binária de busca que seja a melhor possível.
*
*
O que significa melhor árvore
Seja T uma árvore binária de busca, em que cada chave sk possui frequência de acesso fk e se localiza, em T, em um nível lk, 1 ≤ k ≤ n.
A árvore T também incorpora nós externos, correspondentes aos intervalos R0, ..., Rn onde terminam as buscas sem sucesso.
Cada Rk possui frequência de acesso f´k e se localiza no nível l´k de T, 0 ≤ k ≤ n.
*
*
Análise das buscas com sucesso
Toda vez que uma busca bem-sucedida é realizada para localizar sk são efetuadas lk comparações.
Estimativa do número total de comparações realizadas ao longo do processo = fk. lk 
Considerando-se todas as chaves:
Este valor é denominado comprimento de caminho interno ponderado de T
*
*
Análise das buscas sem sucesso
Busca sem sucesso: termina em algum nó externo Rk são efetuadas (l´k-1) comparações.
A parcela de contribuição de Rk no total de comparações efetuadas = f´k.(l´k-1) 
Considerando-se todas os nós externos:
Este somatório é denominado comprimento de caminho externo ponderado de T
*
*
Custo c(T)
O número total de comparações efetuadas ao longo do processo, considerando-se as buscas com e sem sucesso é denominado custo c(T) de T.
A árvore ótima é aquela que apresenta custo mínimo.
*
*
Exemplo
Se a frequência da chave 6 for 3
Se a frequência das demais chaves e nós externos for 5
Calcular o custo c(T).
*
*
Programação Dinâmica
Técnica utilizada para resolver o problema de construir uma árvore binária de busca ótima
A idéia consiste em decompor o problema da do em dois outros de tamanho menor.
T’ - árvore binária de busca com chaves {s1, ..., sk-1} e nós externos R0, ..., Rk-1
 
T’’ - árvore binária de busca com chaves {sk+1, ..., sn} e nós externos Rk, ..., Rn 
*
*
Lema: As subárvores de uma árvore binária de busca ótima são também ótimas.
Se T é ótima, então T’ e T” também o são.
Portanto, conhecendo sk e sabendo construir T’ e T”, a árvore T estará automaticamente construída.
Como conhecer sk?
Como determinar T’ e T”?
*
*
Seja T(i,j) a árvore binária de busca ótima de raiz sk, correspondente às chaves {si+1, ..., sj}, 0 ≤ i < j ≤ n. Então: 
Onde F(i,j) é a soma de todas as frequências correspondentes a T(i,j):
*
*
Resumo
C(T) – custo de T – n° total de comparações efetuadas ao longo do processo para buscas com e sem sucesso
	C(0,n) é o custo final da árvore ótima
T(i,j) – árvore binária de busca ótima de raiz sk
F(i,j) – soma de todas as frequências correspondentes a T(i,j)
*
*
Algoritmo de cálculo do custo da árvore binária de busca ótima
*
*
Observações
O interesse é construir uma árvore de busca ótimo;
Em cada minimização para o cálculo de c[i,j] (última linha do algoritmo) deve ser armazenado o valor minimizante k;
A subárvore ótima possui portanto uma raiz sk, localizando-se as chaves a esquerda e a direita de sk;
É necessário a construção de uma matriz para armazenar os valores de k.
*
*
Exemplo
Seja um conjunto com n = 4 chaves e as seguintes frequências:
Preencher as matrizes correspondentes as variáveis c, F e k
*
*
Inicialização
*
*
Passo 1: d=1; i=0; j=1 -> F(0,1), c(0,1), k(0,1)
*
*
Passo 2: d=1; i=1; j=2 -> F(1,2), c(1,2), k(1,2)
*
*
Passo 3: d=1; i=2; j=3 -> F(2,3), c(2,3), k(2,3)
*
*
Passo 4: d=1; i=3; j=4 -> F(3,4), c(3,4), k(3,4)
*
*
Passo 5: d=2; i=0; j=2 -> F(0,2), c(0,2), k(0,2)
*
*
Passo 6: d=2; i=1; j=3 -> F(1,3), c(1,3), k(1,3)
*
*
Passo 7: d=2; i=2; j=4 -> F(2,4), c(2,4), k(2,4)
*
*
Passo 8: d=3; i=0; j=3 -> F(0,3), c(0,3), k(0,3)
*
*
Passo 9: d=3; i=1; j=4 -> F(1,4), c(1,4), k(1,4)
*
*
Passo 10: d=4; i=0; j=4 -> F(0,4), c(0,4), k(0,4)
*
*
Observações
C[0,4] = 39, O algoritmo realiza 39 passos (comparações) para concluir todos os acessos solicitados;
A configuração da árvore ótima é feita a partir da matriz k
Como k[0,4] = 1, a chave s1, é a raiz da árvore ótima T, a subárvore esquerda de T é vazia;
K[1,4] = 3, o filho direito de s1 é s3
K[1, 2] = 2, o filho esquerdo de s3 é s2
K[3,4] = 4, o filho direito de s3 é s4
*
*
*
*
4.16 – As chaves da árvore da figura apresentam as seguintes frequências de acesso:
Determinar os comprimentos de caminho interno e externo ponderados, bem como o custo da árvore.
*
*
4.17 – Desenhar a árvore binária de custo mínimo relativa às frequências do exercício anterior
4.16 – Comprimento caminho interno ponderado = 20
 Comprimento caminho externo ponderado = 19
 Custo c(T) = 20 + 19 = 39
*