Problema de mantenimiento de pedidos

En informática , el problema del mantenimiento del orden implica mantener un conjunto totalmente ordenado que admita las siguientes operaciones:

• insert(X, Y), que inserta X inmediatamente después de Y en el orden total;
• order(X, Y), que determina si X precede a Y en el orden total; y
• delete(X), lo que elimina X del conjunto.

Paul Dietz introdujo por primera vez una estructura de datos para resolver este problema en 1982. ^{[ 1 ]} Esta estructura de datos admite insert(X, Y)en${\displaystyle O(\log n)}$(en notación Big O ) tiempo amortizadoorder(X, Y) y en tiempo constante, pero no admite eliminación. Athanasios Tsakalidis utilizó árboles BB[α] con los mismos límites de rendimiento que admiten eliminación en${\displaystyle O(\log n)}$y mejoró el rendimiento de inserción y eliminación para ${\displaystyle O(1)}$tiempo amortizado con indirección. ^{[ 2 ]} Dietz y Daniel Sleator publicaron una mejora al tiempo constante del peor caso en 1987. ^{[ 3 ]} Michael Bender, Richard Cole y Jack Zito publicaron alternativas significativamente simplificadas en 2002. ^{[ 4 ]} Bender, Fineman, Gilbert, Kopelowitz y Montes también publicaron una solución desamortizada en 2017. ^{[ 5 ]}

Las estructuras de datos eficientes para el mantenimiento del orden tienen aplicaciones en muchas áreas, incluyendo la persistencia de estructuras de datos , ^{[ 6 ]} algoritmos de grafos ^{[ 7 ] [ 8 ]} y estructuras de datos tolerantes a fallos. ^{[ 9 ]}

Un problema relacionado con el problema de mantenimiento del orden es el problema de etiquetado de listas, en el que en lugar de la order(X, Y)operación, la solución debe mantener una asignación de etiquetas a partir de un universo de enteros.${\displaystyle \{1,2,\ldots ,m\}}$a los elementos del conjunto tales que X precede a Y en el orden total si y solo si a X se le asigna una etiqueta menor que a Y. También debe admitir una operación label(X)que devuelva la etiqueta de cualquier nodo X. Nótese que order(X, Y)se puede implementar simplemente comparando label(X)y label(Y)de modo que cualquier solución al problema de etiquetado de listas proporciona inmediatamente una al problema de mantenimiento del orden. De hecho, la mayoría de las soluciones al problema de mantenimiento del orden son soluciones al problema de etiquetado de listas aumentadas con un nivel de indirección de la estructura de datos para mejorar el rendimiento. Veremos un ejemplo de esto más adelante.

Para un problema de etiquetado de listas en conjuntos de tamaño hasta${\displaystyle n}$El costo del etiquetado de listas depende de cuán grande sea${\displaystyle m}$es una función de${\displaystyle n}$. El rango de parámetros relevantes para el mantenimiento de pedidos es para${\displaystyle m=n^{1+\Theta (1)}}$, para lo cual un${\displaystyle O(\log n)}$Se conoce la solución de costo amortizado, ^{[ 10 ]} y${\displaystyle 2^{\Omega (n)}}$para la cual se conoce una solución amortizada en tiempo constante ^{[ 11 ]}

La indirección es una técnica utilizada en estructuras de datos en la que un problema se divide en múltiples niveles de una estructura de datos para mejorar la eficiencia. Típicamente, un problema de tamaño${\displaystyle n}$se divide en ${\displaystyle n/\log n}$problemas de tamaño${\displaystyle \log n}$Por ejemplo, esta técnica se utiliza en los tries y-rápidos . Esta estrategia también funciona para mejorar el rendimiento de inserción y eliminación de la estructura de datos descrita anteriormente a un tiempo amortizado constante. De hecho, esta estrategia funciona para cualquier solución del problema de etiquetado de listas con${\displaystyle O(\log n)}$tiempo amortizado de inserción y eliminación.

La nueva estructura de datos se reconstruye por completo cada vez que crece demasiado o demasiado poco.${\displaystyle N}$sea ​​el número de elementos del orden total cuando se reconstruyó por última vez. La estructura de datos se reconstruye siempre que el invariante${\displaystyle {\tfrac {N}{3}}\leq n\leq 2N}$se incumple mediante una inserción o eliminación. Dado que la reconstrucción se puede realizar en tiempo lineal, esto no afecta al rendimiento amortizado de las inserciones y eliminaciones.

Durante la operación de reconstrucción, el${\displaystyle N}$Los elementos del pedido total se dividen en${\displaystyle O(N/\log N)}$sublistas contiguas, cada una de tamaño${\displaystyle \Omega (\log N)}$El problema de etiquetado de listas se resuelve en el conjunto de nodos que representan cada una de las sublistas en su orden original. Se considera que las etiquetas para este subproblema son polinómicas, por ejemplo:${\displaystyle m=N^{2}}$, de modo que puedan compararse en tiempo constante y actualizarse en amortizado${\displaystyle O(\log N)}$tiempo.

Para cada sublista se construye una lista doblemente enlazada de sus elementos, almacenando con cada elemento un puntero a su representante en el árbol, así como una etiqueta entera local. Las etiquetas enteras locales también se toman de un rango.${\displaystyle m=N^{2}}$, de modo que se puedan comparar en tiempo constante, pero debido a que cada problema local involucra solo${\displaystyle \Theta (\log N)}$artículos, las etiquetas varían${\displaystyle m}$es exponencial en el número de elementos etiquetados. Por lo tanto, se pueden actualizar en${\displaystyle O(1)}$tiempo amortizado.

Consulte el problema de etiquetado de listas para obtener detalles sobre ambas soluciones.

• Dos algoritmos simplificados para mantener el orden en una lista. - Este artículo ( Michael A. Bender , Richard Cole, Erik D. Demaine , Martin Farach-Colton y Jack Zito, 2002) presenta una estructura de datos para el etiquetado de listas con un rendimiento amortizado que no almacena explícitamente un árbol. El análisis presentado es más sencillo que el proporcionado por (Dietz y Sleator, 1987) para una estructura de datos similar.