En ciencias de la computación , un árbol de búsqueda binario óptimo (Optimal BST) , a veces llamado árbol binario de peso balanceado , [1] es un árbol de búsqueda binario que proporciona el menor tiempo de búsqueda posible (o tiempo de búsqueda esperado ) para una secuencia dada de accesos. (o probabilidades de acceso). Los BST óptimos generalmente se dividen en dos tipos: estáticos y dinámicos.
En el problema de la optimización estática , el árbol no se puede modificar una vez construido. En este caso, existe un diseño particular de los nodos del árbol que proporciona el menor tiempo de búsqueda esperado para las probabilidades de acceso dadas. Existen varios algoritmos para construir o aproximar el árbol estáticamente óptimo dada la información sobre las probabilidades de acceso de los elementos.
En el problema de la optimización dinámica , el árbol se puede modificar en cualquier momento, normalmente permitiendo las rotaciones del árbol . Se considera que el árbol tiene un cursor que comienza en la raíz y que puede mover o usar para realizar modificaciones. En este caso, existe una secuencia de costo mínimo de estas operaciones que hace que el cursor visite cada nodo en la secuencia de acceso de destino en orden. Se conjetura que el árbol de distribución tiene una relación competitiva constante en comparación con el árbol dinámicamente óptimo en todos los casos, aunque esto aún no se ha probado.
Optimalidad estática
Definición
En el problema de la optimización estática definido por Knuth , [2] se nos da un conjunto de n elementos ordenados y un conjunto deprobabilidades. Denotaremos los elementos mediante y las probabilidades mediante y mediante . es la probabilidad de que se realice una búsqueda del elemento . Para, es la probabilidad de que se realice una búsqueda de un elemento entre y , es la probabilidad de que se realice una búsqueda de un elemento estrictamente menor que , y es la probabilidad de que se realice una búsqueda de un elemento estrictamente mayor que . Estas las probabilidades cubren todas las búsquedas posibles y, por lo tanto, suman una.
El problema de la optimización estática es el problema de optimización de encontrar el árbol de búsqueda binario que minimiza el tiempo de búsqueda esperado, dado elprobabilidades. Como el número de árboles posibles en un conjunto de n elementos es, [2] que es exponencial en n , la búsqueda por fuerza bruta no suele ser una solución factible.
Algoritmo de programación dinámica de Knuth
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 2 ) tiempo. [2] La idea principal de Knuth fue que el problema de la optimalidad estática exhibe una subestructura óptima ; es decir, si un determinado árbol 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.
Para ver esto, considere lo que Knuth llama la "longitud de ruta ponderada" de un árbol. La longitud de la ruta ponderada de un árbol en n elementos es la suma de las longitudes de todosposibles rutas de búsqueda, ponderadas por sus respectivas probabilidades. El árbol con la longitud de ruta mínima ponderada es, por definición, estáticamente óptimo.
Pero las longitudes de camino ponderadas tienen una propiedad interesante. Sea E la longitud de la ruta ponderada de un árbol binario, E L la longitud de la ruta ponderada de su subárbol izquierdo y E R la longitud de la ruta ponderada de su subárbol derecho. También sea 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, cada una de sus rutas de búsqueda) aumenta en uno. También observe que la raíz en sí tiene una profundidad de uno. Esto significa que la diferencia en la longitud de la ruta ponderada entre un árbol y sus dos subárboles es exactamente la suma de cada probabilidad en el árbol, lo que lleva a la siguiente recurrencia:
Esta recurrencia conduce a una solución de programación dinámica natural. Dejarsea la longitud de la ruta ponderada del árbol de búsqueda estáticamente óptimo para todos los valores entre a i y a j , sea sea el peso total de ese árbol, y dejemos ser el índice de su raíz. El algoritmo se puede construir usando las siguientes fórmulas:
- La implementación ingenua de este algoritmo en realidad toma O ( n 3 ) tiempo, pero el artículo de Knuth incluye algunas observaciones adicionales que pueden usarse para producir un algoritmo modificado que toma solo O ( n 2 ) tiempo.
Algoritmo de aproximación de Mehlhorn
Si bien el tiempo O ( n 2 ) que toma el algoritmo de Knuth es sustancialmente mejor que el tiempo exponencial requerido para una búsqueda de fuerza bruta, todavía es 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 que se podría usar un algoritmo mucho más simple para aproximarse mucho al árbol estáticamente óptimo en solohora. [3] En este algoritmo, la raíz del árbol se elige para equilibrar más estrechamente el peso total (por probabilidad) de los subárboles izquierdo y derecho. Esta estrategia se aplica luego de forma recursiva en cada subárbol.
Que esta estrategia produce una buena aproximación se puede ver intuitivamente al notar 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 ruta ponderada es como máximo
donde H es la entropía de la distribución de probabilidad. Dado que ningún árbol de búsqueda binario óptimo puede funcionar mejor que una longitud de ruta ponderada de
esta aproximación es muy cercana. [3]
Algoritmos de Hu-Tucker y Garsia-Wachs
En el caso especial de que todos los los valores son cero, el árbol óptimo se puede encontrar a tiempo . 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 Garsia-Wachs , realiza las mismas comparaciones en el mismo orden. El algoritmo funciona mediante el uso de un algoritmo codicioso 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. [4]
Optimidad dinámica
¿Los árboles de splay funcionan tan bien como cualquier otro algoritmo de árbol de búsqueda binario?
Definición
Hay varias definiciones diferentes de optimalidad dinámica, todas las cuales son efectivamente equivalentes dentro de un factor constante en términos de tiempo de ejecución. [5] El problema fue introducido implícitamente por primera vez por Sleator y Tarjan en su artículo sobre árboles de extensión , [6] pero Demaine et al. dar una muy buena declaración formal. [5]
En el problema de la optimización dinámica, se nos da una secuencia de accesos x 1 , ..., x m en las teclas 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:
- Mueva el puntero al hijo izquierdo del nodo actual.
- Mueva el puntero al hijo derecho del nodo actual.
- Mueva el puntero al padre del nodo actual.
- Realice una sola rotación en el nodo actual y su padre.
(Es la presencia de la cuarta operación, que reordena el árbol durante los accesos, lo que hace que éste sea el problema de optlmalidad dinámica ).
Para cada acceso, nuestro algoritmo BST puede realizar cualquier secuencia de las operaciones anteriores siempre que el puntero termine finalmente en el nodo que contiene el valor objetivo x i . El tiempo que le toma a un algoritmo BST dinámico dado realizar una secuencia de accesos es equivalente al número total de tales operaciones realizadas durante esa secuencia. Dada cualquier secuencia de accesos en cualquier conjunto de elementos, existe un número mínimo total de operaciones requeridas para realizar esos accesos. Nos gustaría acercarnos a este mínimo.
Si bien es imposible implementar este " algoritmo de Dios " sin un conocimiento previo de cuál será exactamente la secuencia de acceso, 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 el tiempo O (OPT (X)) (es decir, tiene una razón competitiva constante ). [5]
Se conjetura que varias estructuras de datos tienen esta propiedad, pero ninguna está probada. Es un problema abierto si existe una estructura de datos dinámicamente óptima en este modelo.
Árboles esparcidos
El árbol de splay es una forma de árbol de búsqueda binaria inventado en 1985 por Daniel Sleator y Robert Tarjan en el que se ejecutan las operaciones de árbol de búsqueda estándar entiempo amortizado. [7] Se conjetura que es dinámicamente óptimo en el sentido requerido. Es decir, se cree que un árbol de distribución realiza cualquier secuencia de acceso X suficientemente larga en el tiempo O (OPT (X)). [6]
Árboles de tango
El árbol del tango es una estructura de datos propuesta en 2004 por Erik Demaine y otros que ha demostrado realizar cualquier secuencia de acceso X suficientemente larga en el tiempo.. Si bien esto no es dinámicamente óptimo, la relación competitiva desigue siendo muy pequeño para valores razonables de n. [5]
Otros resultados
En 2013, John Iacono publicó un artículo que utiliza la geometría de los árboles de búsqueda binarios para proporcionar un algoritmo que es dinámicamente óptimo si cualquier algoritmo de árbol de búsqueda binario es dinámicamente óptimo. [8] Los nodos se interpretan como puntos en dos dimensiones, y la secuencia de acceso óptima es el superconjunto más pequeño arboralmente satisfecho de esos puntos. A diferencia de los árboles de esparcimiento y los árboles de tango, no se sabe que la estructura de datos de Iacono se pueda 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 árbol de búsqueda por un factor no constante.
El límite inferior entrelazado es un límite inferior asintótico en la optimización dinámica.
Ver también
- Árboles
- Árbol de extensión
- Árbol de tango
- Geometría de árboles de búsqueda binarios
- Intercalar límite inferior
Notas
- ^ Tremblay, Jean-Paul; Cheston, Grant A. (2001). Estructuras de datos y desarrollo de software en un dominio orientado a objetos . Edición Eiffel / Prentice Hall. ISBN 978-0-13-787946-5.
- ^ a b c Knuth, Donald E. (1971), "Árboles de búsqueda binarios óptimos", Acta Informatica , 1 (1): 14–25, doi : 10.1007 / BF00264289 , S2CID 62777263
- ^ a b Mehlhorn, Kurt (1975), "Árboles de búsqueda binarios casi óptimos" , Acta Informatica , 5 (4): 287–295, doi : 10.1007 / BF00264563 , S2CID 17188103
- ^ Knuth, Donald E. (1998), "Algoritmo G (algoritmo de Garsia-Wachs para árboles binarios óptimos)", El arte de la programación informática, vol. 3: Clasificación y búsqueda (2ª ed.), Addison – Wesley, págs. 451–453. Véase también Historia y bibliografía, págs. 453–454.
- ^ a b c d Demaine, Erik D .; Harmon, Dion; Iacono, John; Patrascu, Mihai (2004), Optimalidad dinámica — casi (PDF) , págs. 484–490, CiteSeerX 10.1.1.99.4964 , doi : 10.1109 / FOCS.2004.23 , ISBN 978-0-7695-2228-9 Parámetro desconocido
|book-title=
ignorado ( ayuda ) - ^ a b Sleator, Daniel; Tarjan, Robert (1985), "Árboles de búsqueda binarios autoajustables", Journal of the ACM , 32 (3): 652–686, doi : 10.1145 / 3828.3835 , S2CID 1165848
- ^ Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald; Stein, Clifford (2009). Introducción a los algoritmos (PDF) (Tercera ed.). La prensa del MIT. pag. 503. ISBN 978-0-262-03384-8. Consultado el 31 de octubre de 2017 .
- ^ Iacono, John (2013), "En pos de la conjetura de la optimización dinámica", arXiv : 1306.0207 [ cs.DS ]