DAA: árboles de búsqueda binaria de costo óptimo

Un árbol de búsqueda binaria (BST) es un árbol donde los valores clave se almacenan en los nodos internos. Los nodos externos son nodos nulos. Las claves están ordenadas lexicográficamente, es decir, para cada nodo interno todas las claves en el subárbol izquierdo son menores que las claves en el nodo, y todas las claves en el subárbol derecho son mayores.

Cuando conocemos la frecuencia de búsqueda de cada una de las claves, es bastante fácil calcular el costo esperado de acceder a cada nodo del árbol. Un árbol de búsqueda binario óptimo es un BST, que tiene un costo mínimo esperado para ubicar cada nodo

El tiempo de búsqueda de un elemento en una BST es O(n), mientras que en una BST equilibrada el tiempo de búsqueda es O(log n). Nuevamente, el tiempo de búsqueda se puede mejorar en el árbol de búsqueda binaria de costo óptimo, colocando los datos utilizados con más frecuencia en la raíz y más cerca del elemento raíz, mientras que los datos utilizados con menos frecuencia cerca de las hojas y en las hojas.

Aquí, se presenta el algoritmo de árbol de búsqueda binario óptimo. Primero, construimos una BST a partir de un conjunto den número de claves distintas < k1, k2, k3, ... kn >. Aquí asumimos, la probabilidad de acceder a una claveKi es pi. Algunas llaves falsas (d0, d1, d2, ... dn) se añaden ya que se pueden realizar algunas búsquedas para los valores que no están presentes en el conjunto de claves K. Suponemos, para cada clave ficticiadi probabilidad de acceso es qi.

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álisis

El algoritmo requiere O (n3) tiempo, desde tres anidados forse utilizan bucles. Cada uno de estos bucles adquiere como máximon valores.

Ejemplo

Considerando el siguiente árbol, el costo es 2.80, aunque este no es un resultado óptimo.

Nodo Profundidad Probabilidad Contribución
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 obtener una solución óptima, utilizando el algoritmo discutido en este capítulo, se generan las siguientes tablas.

En las siguientes tablas, el índice de columna es i y el índice de fila es j.

mi 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

raíz 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 de estas tablas, se puede formar el árbol óptimo.