Árbol de búsqueda binaria óptimo

En el problema de optimalidad estática definido por Knuth , ^{[ 2 ]} se nos da un conjunto de n elementos ordenados y un conjunto de${\displaystyle 2n+1}$probabilidades. Denotaremos los elementos${\displaystyle a_{1}}$a través de${\displaystyle a_{n}}$y las probabilidades${\displaystyle A_{1}}$a través de${\displaystyle A_{n}}$y${\displaystyle B_{0}}$a través de${\displaystyle B_{n}}$.${\displaystyle A_{i}}$es la probabilidad de que se realice una búsqueda del elemento${\displaystyle a_{i}}$(o búsqueda exitosa ). ^{[ 3 ]} Para${\displaystyle 1\leq i<n}$,${\displaystyle B_{i}}$es la probabilidad de que se realice una búsqueda de un elemento entre${\displaystyle a_{i}}$y${\displaystyle a_{i+1}}$(o búsqueda infructuosa ), ^{[ 3 ]}${\displaystyle B_{0}}$es la probabilidad de que se realice una búsqueda de un elemento estrictamente menor que${\displaystyle a_{1}}$, y${\displaystyle B_{n}}$¿La probabilidad de que se realice una búsqueda de un elemento es estrictamente mayor que...?${\displaystyle a_{n}}$. Estos${\displaystyle 2n+1}$Las probabilidades abarcan todas las búsquedas posibles y, por lo tanto, suman uno.

El problema de optimalidad estática es el problema de optimización de encontrar el árbol de búsqueda binaria que minimiza el tiempo de búsqueda esperado, dado el${\displaystyle 2n+1}$probabilidades. Como el número de árboles posibles en un conjunto de n elementos es${\displaystyle {2n \choose n}{\frac {1}{n+1}}}$, ^{[ 2 ]} que es exponencial en n , la búsqueda por fuerza bruta no suele ser una solución factible.

En 1971, Knuth publicó un algoritmo de programación dinámica relativamente sencillo capaz de construir el árbol estáticamente óptimo en solo O ( n² ) tiempo. ^{[ 2 ]} En este trabajo, Knuth extendió y mejoró el algoritmo de programación dinámica de Edgar Gilbert y Edward F. Moore ^introducido en 1958. ^{[ 4 ]} El algoritmo de Gilbert y Moore requería${\displaystyle O(n^{3})}$tiempo y${\displaystyle O(n^{2})}$espacio y fue diseñado para un caso particular de construcción de árboles de búsqueda binaria óptimos (conocido como problema del árbol alfabético óptimo ^{[ 5 ]} ) que considera solo la probabilidad de búsquedas no exitosas, es decir,${\textstyle \sum _{i=1}^{n}A_{i}=0}$El trabajo de Knuth se basó en la siguiente idea: el problema de optimalidad estática presenta una subestructura óptima ; es decir, si un árbol determinado es estáticamente óptimo para una distribución de probabilidad dada, entonces sus subárboles izquierdo y derecho también deben ser estáticamente óptimos para sus subconjuntos apropiados de la distribución (lo que se conoce como propiedad de monotonicidad de las raíces).

Para ver esto, consideremos lo que Knuth llama la "longitud de camino ponderada" de un árbol. La longitud de camino ponderada de un árbol de n elementos es la suma de las longitudes de todos los caminos.${\displaystyle 2n+1}$Posibles rutas de búsqueda, ponderadas según sus respectivas probabilidades. El árbol con la longitud de ruta ponderada mínima es, por definición, estáticamente óptimo.

Pero las longitudes de camino ponderadas tienen una propiedad interesante. Sea E la longitud de camino ponderada de un árbol binario, E _L la longitud de camino ponderada de su subárbol izquierdo y E _R la longitud de camino ponderada de su subárbol derecho. Sea también W la suma de todas las probabilidades en el árbol. Observe que cuando cualquiera de los subárboles se adjunta a la raíz, la profundidad de cada uno de sus elementos (y, por lo tanto, de cada uno de sus caminos de búsqueda) aumenta en uno. Observe también que la raíz misma tiene una profundidad de uno. Esto significa que la diferencia en la longitud de camino ponderada entre un árbol y sus dos subárboles es exactamente la suma de cada probabilidad individual en el árbol, lo que lleva a la siguiente recurrencia:

${\displaystyle E=E_{L}+E_{R}+W}$

Esta recurrencia conduce a una solución de programación dinámica natural.${\displaystyle E_{ij}}$Sea la longitud de ruta ponderada del árbol de búsqueda estáticamente óptimo para todos los valores entre a _i y a _j , sea${\displaystyle W_{ij}}$sea ​​el peso total de ese árbol, y sea${\displaystyle R_{ij}}$Sea el índice de su raíz. El algoritmo se puede construir utilizando las siguientes fórmulas:

${\displaystyle {\begin{aligned}E_{i,i-1}=W_{i,i-1}&=B_{i-1}\operatorname {para} 1\leq i\leq n+1\\W_{i,j}&=W_{i,j-1}+A_{j}+B_{j}\\E_{i,j}&=\min _{i\leq r\leq j}(E_{i,r-1}+E_{r+1,j}+W_{i,j})\operatorname {para} 1\leq i\leq j\leq n\end{aligned}}}$

La implementación ingenua de este algoritmo en realidad toma un tiempo de O ( n ³ ), pero el artículo de Knuth incluye algunas observaciones adicionales que se pueden utilizar para producir un algoritmo modificado que toma solo un tiempo de O ( n ² ).

Además de su algoritmo de programación dinámica, Knuth propuso dos heurísticas (o reglas) para producir árboles de búsqueda binaria casi óptimos (aproximados a ellos) . Estudiar árboles de búsqueda binaria casi óptimos era necesario ya que la complejidad temporal y espacial del algoritmo de Knuth puede ser prohibitiva cuando${\displaystyle n}$es sustancialmente grande. ^{[ 6 ]}

Las reglas de Knuth pueden verse de la siguiente manera:

• Regla I (Raíz máxima): Coloca el nombre que aparece con mayor frecuencia en la raíz del árbol y luego procede de manera similar en los subárboles.
• Regla II (Bisección): Elija la raíz de manera que se iguale el peso total de los subárboles izquierdo y derecho tanto como sea posible, y luego proceda de manera similar con los subárboles.

La heurística de Knuth implementa árboles de búsqueda binaria casi óptimos en${\displaystyle O(n\log n)}$tiempo y${\displaystyle O(n)}$espacio. Kurt Mehlhorn propuso además un análisis sobre cuán lejos del óptimo pueden estar las heurísticas de Knuth . ^{[ 6 ]}

Aunque el tiempo O ( n2 ⁾ que tarda el algoritmo de Knuth es sustancialmente mejor que el tiempo exponencial requerido para una búsqueda por fuerza bruta, sigue siendo demasiado lento para ser práctico cuando el número de elementos en el árbol es muy grande.

En 1975, Kurt Mehlhorn publicó un artículo que demostraba propiedades importantes de las reglas de Knuth. Los principales resultados de Mehlhorn indican que solo una de las heurísticas de Knuth (Regla II) siempre produce árboles de búsqueda binaria casi óptimos. Por otro lado, la regla root-max a menudo puede generar árboles de búsqueda muy deficientes, según el siguiente argumento simple. ^{[ 6 ]}

Dejar

${\textstyle {\begin{aligned}n=2^{k}-1,~~A_{i}=2^{-k}+\varepsilon _{i}~~\operatorname {con} ~~\sum _{i=1}^{n}\varepsilon _{i}=2^{-k}\end{aligned}}}$

y

${\textstyle {\begin{aligned}\varepsilon _{1},\varepsilon _{2},\dots ,\varepsilon _{n}>0~~\operatorname {para} ~~1\leqq i\leqq n~~\operatorname {y} ~~B_{j}=0\operatorname {para} ~~0\leqq j\leqq n.\end{aligned}}}$

Considerando la longitud de la ruta ponderada${\displaystyle P}$Del árbol construido a partir de la definición anterior, tenemos lo siguiente:

${\textstyle {\begin{aligned}P&=\sum _{i=1}^{n}A_{i}(a_{i}+1)+\sum _{j=1}^{n}B_{j}b_{j}\\&=\sum _{i=1}^{n}A_{i}i\\&\geqq 2^{-k}\sum _{i=1}^{n}i=2^{-k}{\frac {n(n+1)}{2}}\geqq {\frac {n}{2}}.\end{aligned}}}$

Por lo tanto, el árbol resultante según la regla root-max será un árbol que crece solo en el lado derecho (excepto en el nivel más profundo del árbol), y el lado izquierdo siempre tendrá nodos terminales. Este árbol tiene una longitud de camino limitada por${\estilo de texto \Omega ({\frac {n}{2}})}$y, en comparación con un árbol de búsqueda equilibrado (con ruta delimitada por${\textstyle O(2\log n)}$), tendrá un rendimiento sustancialmente peor para la misma distribución de frecuencia. ^{[ 6 ]}

Además, Mehlhorn mejoró el trabajo de Knuth e introdujo un algoritmo mucho más simple que utiliza la Regla II y se aproxima mucho al rendimiento del árbol estáticamente óptimo en solo ⁠${\displaystyle O(n)}$tiempo. [ ^{6 ] El algoritmo sigue la misma idea de la regla de bisección al elegir la raíz del árbol para equilibrar el peso total (por probabilidad) de los subárboles izquierdo y derecho de} la manera más precisa. Y la estrategia se aplica luego recursivamente en cada subárbol.

Que esta estrategia produce una buena aproximación se puede ver intuitivamente al observar que los pesos de los subárboles a lo largo de cualquier camino forman algo muy cercano a una secuencia geométricamente decreciente. De hecho, esta estrategia genera un árbol cuya longitud de camino ponderado es como máximo

${\displaystyle 2+(1-\log({\sqrt {5}}-1))^{-1}H=2+{\frac {H}{1-\log({\sqrt {5}}-1)}}}$

donde H es la entropía de la distribución de probabilidad. Dado que ningún árbol de búsqueda binaria óptimo puede hacerlo mejor que una longitud de ruta ponderada de

${\displaystyle (1/\log 3)H={\frac {H}{\log 3}}}$

Esta aproximación es muy cercana. ^{[ 6 ]}

En el caso especial de que todos los${\displaystyle A_{i}}$Los valores son cero, el árbol óptimo se puede encontrar en tiempo${\displaystyle O(n\log n)}$Esto fue demostrado por primera vez por TC Hu y Alan Tucker en un artículo que publicaron en 1971. Una simplificación posterior de Garsia y Wachs, el algoritmo de Garsia-Wachs , realiza las mismas comparaciones en el mismo orden. El algoritmo funciona utilizando un algoritmo voraz para construir un árbol que tiene la altura óptima para cada hoja, pero está fuera de orden, y luego construye otro árbol de búsqueda binaria con las mismas alturas. ^{[ 7 ]}

Existen varias definiciones diferentes de optimalidad dinámica, todas las cuales son efectivamente equivalentes con un factor constante en términos de tiempo de ejecución. ^{[ 8 ]} El problema fue introducido implícitamente por primera vez por Sleator y Tarjan en su artículo sobre árboles splay , ^{[ 9 ]} pero Demaine et al. ofrecen una formulación formal muy buena del mismo. ^{[ 8 ]}

En el problema de optimalidad dinámica, se nos da una secuencia de accesos x ₁ , ..., x _m sobre las claves 1, ..., n. Para cada acceso, se nos da un puntero a la raíz de nuestro BST y podemos usar el puntero para realizar cualquiera de las siguientes operaciones:

1. Mueva el puntero al hijo izquierdo del nodo actual.
2. Mueva el puntero al hijo derecho del nodo actual.
3. Mueva el puntero al nodo padre del nodo actual.
4. Realiza una única rotación sobre el nodo actual y su nodo padre.

(Es la presencia de la cuarta operación, que reorganiza el árbol durante los accesos, lo que convierte esto en un problema de optimalidad dinámica ).

Para cada acceso, nuestro algoritmo BST puede realizar cualquier secuencia de las operaciones anteriores, siempre que el puntero termine en el nodo que contiene el valor objetivo x _i . El tiempo que tarda un algoritmo BST dinámico en realizar una secuencia de accesos es equivalente al número total de operaciones realizadas durante dicha secuencia. Dada cualquier secuencia de accesos a cualquier conjunto de elementos, existe un número mínimo total de operaciones necesarias para realizar esos accesos. Nos gustaría aproximarnos a este mínimo.

Si bien es imposible implementar este " algoritmo de Dios " sin conocer de antemano la secuencia de acceso exacta, podemos definir OPT(X) como el número de operaciones que realizaría para una secuencia de acceso X, y podemos decir que un algoritmo es dinámicamente óptimo si, para cualquier X, realiza X en tiempo O (OPT(X)) (es decir, tiene una razón de competitividad constante ). ^{[ 8 ]}

Se han conjeturado varias estructuras de datos que poseen esta propiedad, pero ninguna ha sido probada. Sigue siendo un problema abierto determinar si existe una estructura de datos dinámicamente óptima en este modelo.

El árbol splay es una forma de árbol de búsqueda binaria inventada en 1985 por Daniel Sleator y Robert Tarjan sobre la cual se ejecutan las operaciones estándar del árbol de búsqueda.${\displaystyle O(\log(n))}$tiempo amortizado. ^{[ 10 ]} Se conjetura que es dinámicamente óptimo en el sentido requerido. Es decir, se cree que un árbol splay realiza cualquier secuencia de acceso suficientemente larga X en tiempo O(OPT(X)). ^{[ 9 ]}

El árbol tango es una estructura de datos propuesta en 2004 por Erik D. Demaine , Dion Harmon, John Iacono y Mihai Pătrașcu que ha demostrado realizar cualquier secuencia de acceso suficientemente larga X en tiempo${\displaystyle O(\log \log n\operatorname {OPT} (X))}$. Si bien esto no es dinámicamente óptimo, la relación competitiva de${\displaystyle \log \log n}$sigue siendo muy pequeño para valores razonables de n. ^{[ 8 ]}

En 2013, John Iacono publicó un artículo que utiliza la geometría de los árboles de búsqueda binaria para proporcionar un algoritmo que es dinámicamente óptimo si algún algoritmo de árbol de búsqueda binaria es dinámicamente óptimo. ^{[ 11 ]} Los nodos se interpretan como puntos en dos dimensiones, y la secuencia de acceso óptima es el superconjunto más pequeño de esos puntos que satisface arborísticamente . A diferencia de los árboles splay y los árboles tango, no se sabe si la estructura de datos de Iacono se puede implementar en tiempo constante por paso de secuencia de acceso, por lo que incluso si es dinámicamente óptima, aún podría ser más lenta que otras estructuras de datos de árboles de búsqueda por un factor no constante.

El límite inferior de entrelazado es un límite inferior asintótico para la optimalidad dinámica.