DAA - Árvores de pesquisa binárias de custo ideal

Uma árvore de pesquisa binária (BST) é uma árvore onde os valores-chave são armazenados nos nós internos. Os nós externos são nós nulos. As chaves são ordenadas lexicograficamente, ou seja, para cada nó interno, todas as chaves na subárvore esquerda são menores do que as chaves no nó e todas as chaves na subárvore direita são maiores.

Quando sabemos a frequência de busca de cada uma das chaves, é muito fácil calcular o custo esperado de acesso a cada nó da árvore. Uma árvore de pesquisa binária ideal é um BST, que tem um custo mínimo esperado de localização de cada nó

O tempo de busca de um elemento em um BST é O(n), enquanto em um tempo de pesquisa Balanced-BST é O(log n). Novamente, o tempo de pesquisa pode ser melhorado na árvore de pesquisa binária de custo ideal, colocando os dados usados ​​com mais frequência na raiz e mais perto do elemento raiz, enquanto coloca os dados usados ​​com menos frequência perto das folhas e nas folhas.

Aqui, o algoritmo de árvore de busca binária ideal é apresentado. Primeiro, construímos um BST a partir de um conjunto den número de chaves distintas < k₁, k₂, k₃, ... k_n >. Aqui assumimos, a probabilidade de acessar uma chaveK_i é p_i. Algumas chaves fictícias (d₀, d₁, d₂, ... d_n) são adicionados, pois algumas pesquisas podem ser realizadas para os valores que não estão presentes no conjunto de chaves K. Assumimos, para cada chave fictíciad_i probabilidade de acesso é q_i.

Optimal-Binary-Search-Tree(p, q, n) 
e[1…n + 1, 0…n],  
w[1…n + 1, 0…n], 
root[1…n + 1, 0…n]  
for i = 1 to n + 1 do 
   e[i, i - 1] := qi - 1 
   w[i, i - 1] := qi - 1  
for l = 1 to n do 
   for i = 1 to n – l + 1 do 
      j = i + l – 1 e[i, j] := ∞ 
      w[i, i] := w[i, i -1] + pj + qj 
      for r = i to j do 
         t := e[i, r - 1] + e[r + 1, j] + w[i, j] 
         if t < e[i, j] 
            e[i, j] := t 
            root[i, j] := r 
return e and root

Análise

O algoritmo requer O (n³) tempo, desde três aninhados forloops são usados. Cada um desses loops leva no máximon valores.

Exemplo

Considerando a árvore a seguir, o custo é de 2,80, embora este não seja um resultado ideal.

Nó	Profundidade	Probabilidade	Contribuição
k 1	1	0,15	0,30
k 2	0	0,10	0,10
k 3	2	0,05	0,15
k 4	1	0,10	0,20
k 5	2	0,20	0,60
d 0	2	0,05	0,15
d 1	2	0,10	0,30
d 2	3	0,05	0,20
d 3	3	0,05	0,20
d 4	3	0,05	0,20
d 5	3	0,10	0,40
Total			2,80

Para obter uma solução ideal, usando o algoritmo discutido neste capítulo, as seguintes tabelas são geradas.

Nas tabelas a seguir, o índice da coluna é i e o índice da linha é j.

e	1	2	3	4	5	6
5	2,75	2,00	1,30	0,90	0,50	0,10
4	1,75	1,20	0,60	0,30	0,05
3	1,25	0,70	0,25	0,05
2	0,90	0,40	0,05
1	0,45	0,10
0	0,05

W	1	2	3	4	5	6
5	1,00	0,80	0,60	0,50	0,35	0,10
4	0,70	0,50	0,30	0,20	0,05
3	0,55	0,35	0,15	0,05
2	0,45	0,25	0,05
1	0,30	0,10
0	0,05

raiz	1	2	3	4	5
5	2	4	5	5	5
4	2	2	4	4
3	2	2	3
2	1	2
1	1

A partir dessas tabelas, a árvore ideal pode ser formada.