Problema del predecesor

En informática , el problema del predecesor implica mantener un conjunto de elementos para, dado un elemento, consultar eficientemente qué elemento precede o sucede a ese elemento en un orden determinado. Las estructuras de datos utilizadas para resolver el problema incluyen árboles de búsqueda binaria balanceados , árboles de van Emde Boas y árboles de fusión . En el problema del predecesor estático , el conjunto de elementos no cambia, pero en el problema del predecesor dinámico , se permiten inserciones y eliminaciones del conjunto. ^{[ 1 ]}

El problema del predecesor es un caso simple del problema del vecino más cercano , y las estructuras de datos que lo resuelven tienen aplicaciones en problemas como la ordenación de enteros .

El problema consiste en mantener un conjunto S , que contiene un subconjunto de U enteros. Cada uno de estos enteros se puede almacenar con un tamaño de palabra w , lo que implica que${\displaystyle U\leq 2^{w}}$. Las estructuras de datos que resuelven el problema admiten estas operaciones: ^{[ 2 ]}

• predecessor(x), que devuelve el elemento más grande en S estrictamente menor que x
• successor(x), que devuelve el elemento más pequeño en S estrictamente mayor que x

Además, las estructuras de datos que resuelven la versión dinámica del problema también admiten estas operaciones:

• insert(x), lo que añade x al conjunto S
• delete(x), lo que elimina x del conjunto S

El problema se analiza típicamente en un modelo de computación transdicotómico como la memoria RAM de palabras .

Una solución sencilla a este problema es utilizar un árbol de búsqueda binaria balanceado , que logra (en notación Big O ) un tiempo de ejecución de${\displaystyle O(\log n)}$para consultas predecesoras. El árbol de Van Emde Boas logra un tiempo de consulta de${\displaystyle O(\log \log U)}$pero requiere${\displaystyle O(U)}$espacio . ^{[ 1 ]} Dan Willard propuso una mejora en este uso del espacio con el trie x-rápido , que requiere${\displaystyle O(n\log U)}$espacio y el mismo tiempo de consulta, y el trie y-fast más complicado , que solo requiere${\displaystyle O(n)}$espacio. ^{[ 3 ]} Los árboles de fusión , introducidos por Michael Fredman y Willard, logran${\displaystyle O(\log _{w}n)}$tiempo de consulta y${\displaystyle O(n)}$para consultas de predecesores para el problema estático. ^{[ 4 ]} El problema dinámico se ha resuelto utilizando árboles exponenciales con${\displaystyle O(\log _{w}n+\log \log n)}$tiempo de consulta, ^{[ 5 ]} y con tiempo esperado${\displaystyle O(\log _{w}n)}$utilizando funciones hash . ^{[ 6 ]}

Se han publicado varios artículos que demuestran cotas inferiores para el problema del predecesor, o que identifican cuál sería el tiempo de ejecución de las soluciones asintóticamente óptimas . Por ejemplo, Michael Beame y Faith Ellen demostraron que para todos los valores de w , existe un valor de n con tiempo de consulta (en notación Big Theta ).${\displaystyle \Omega \left({\tfrac {\log w}{\log \log w}}\right)}$y de manera similar, para todos los valores de n , existe un valor de n tal que el tiempo de consulta es${\displaystyle \Omega \left({\sqrt {\tfrac {\log n}{\log \log n}}}\right)}$. ^{[ 1 ]} Otras pruebas de cotas inferiores incluyen la noción de complejidad de la comunicación .

Para el problema del predecesor estático, Mihai Pătrașcu y Mikkel Thorup mostraron la siguiente cota inferior para el tiempo de búsqueda óptimo, en el modelo de sonda celular : ^{[ 7 ]}$${\displaystyle O(1)\min \left\{{\begin{array}{l}\log _{w}n\\\lg {\frac {\ell -\lg n}{a}}\\{\frac {\lg {\frac {\ell }{a}}}{\lg \left({\frac {a}{\lg n}}\,\cdot \,\lg {\frac {\ell }{a}}\right)}}\\{\frac {\lg {\frac {\ell }{a}}}{\lg \left(\lg {\frac {\ell }{a}}\right/\left.\lg {\frac {\lg n}{a}}\right)}}\end{array}}\right.}$$ donde la RAM tiene longitud de palabra${\displaystyle w}$, el conjunto contiene${\displaystyle n}$enteros de${\displaystyle \ell }$bits cada uno y se representa en la RAM usando${\displaystyle S}$palabras de espacio y definición${\displaystyle a=\lg {\frac {S}{n}}+\lg w}$.

En el caso donde${\displaystyle w=\ell =\gamma \lg n}$para${\displaystyle \gamma >1}$y${\displaystyle S=n\cdot \lg ^{O(1)}n}$, el tiempo de búsqueda óptimo es ${\displaystyle \Theta (\lg \ell )}$y el árbol de van Emde Boas alcanza este límite. ^{[ 7 ]}

• Ordenación de enteros
• y-rápido trie
• Árbol de fusión