En informática , un trie rápido y es una estructura de datos para almacenar números enteros de un dominio acotado. Admite consultas exactas y predecesoras o sucesoras en el tiempo O (log log M ), utilizando el espacio O ( n ), donde n es el número de valores almacenados y M es el valor máximo en el dominio. La estructura fue propuesta por Dan Willard en 1982 [1] para disminuir el espacio O ( n log M ) utilizado por un trie x-fast .
Y-fast trie | |
---|---|
Tipo | Trie |
Inventado | mil novecientos ochenta y dos |
Inventado por | Dan Willard |
Complejidad asintótica en notación O grande | |
Espacio | O ( n ) |
Buscar | O (log log M ) |
Insertar | O (log log M ) promedio amortizado |
Borrar | O (log log M ) promedio amortizado |
Estructura
Un trie rápido y consta de dos estructuras de datos: la mitad superior es un trie rápido x y la mitad inferior consta de varios árboles binarios equilibrados . Las claves se dividen en grupos de O (log M ) elementos consecutivos y para cada grupo se crea un árbol de búsqueda binario balanceado. Para facilitar la inserción y eliminación eficiente, cada grupo contiene al menos (log M ) / 4 y como máximo 2 log M elementos. [2] Para cada árbol de búsqueda binario balanceado se elige una r representativa . Estos representantes se almacenan en el trie x-fast. Un representante r no necesita ser un elemento del árbol asociado con él, pero sí necesita ser un número entero más pequeño que el sucesor de r y el elemento mínimo del árbol asociado con ese sucesor y mayor que el predecesor de r y el elemento máximo. del árbol asociado con ese predecesor. Inicialmente, el representante de un árbol será un número entero entre el elemento mínimo y máximo de su árbol.
Dado que el trie x-fast almacena O ( n / log M ) representantes y cada representante aparece en tablas hash O (log M ), esta parte del trie y-fast utiliza el espacio O ( n ). Los árboles de búsqueda binarios balanceados almacenan n elementos en total que utilizan O ( n ) espacio. Por lo tanto, en total, un trie rápido y usa espacio O ( n ).
Operaciones
Al igual que los árboles de van Emde Boas y los intentos x-fast, los intentos y-fast admiten las operaciones de una matriz asociativa ordenada . Esto incluye las operaciones habituales de matriz asociativa, junto con dos operaciones de orden más , Sucesora y Predecesora :
- Find ( k ): encuentra el valor asociado con la clave dada
- Sucesor ( k ): busque el par clave / valor con la clave más pequeña mayor o igual que la clave dada
- Predecesor ( k ): busque el par clave / valor con la clave más grande menor o igual que la clave dada
- Insertar ( k , v ): inserta el par clave / valor dado
- Delete ( k ): elimina el par clave / valor con la clave dada
Encontrar
Una clave k puede almacenarse en el árbol del representante más pequeño r mayor que k o en el árbol del predecesor de r ya que el representante de un árbol de búsqueda binaria no necesita ser un elemento almacenado en su árbol. Por lo tanto, primero se encuentra el representante más pequeño r mayor que k en el trie x-fast. Usando este representante, se recupera el predecesor de r . Estos dos representantes apuntan a dos árboles de búsqueda binarios balanceados, en los cuales uno busca k .
Encontrar el representante más pequeño r mayor que k en el trie x-fast toma O (log log M ). Con r , encontrar su predecesor lleva un tiempo constante. La búsqueda de los dos árboles de búsqueda binarios balanceados que contienen elementos O (log M ) lleva cada uno O (log log M ) tiempo. Por tanto, se puede encontrar una clave k , y recuperar su valor, en tiempo O (log log M ). [1]
Sucesor y predecesor
De manera similar a la clave k en sí, su sucesora puede almacenarse en el árbol del representante más pequeño r mayor que k o en el árbol del predecesor de r . Por lo tanto, para encontrar el sucesor de una clave k , primero se busca en el trie rápido x el representante más pequeño mayor que k . A continuación, se utiliza este representante para recuperar su predecesor en el trie x-fast. Estos dos representantes apuntan a dos árboles de búsqueda binarios equilibrados, en los que se busca el sucesor de k . [3]
Encontrar el representante más pequeño r mayor que k en el trie rápido x toma O (log log M ) tiempo y usar r para encontrar su predecesor toma un tiempo constante. La búsqueda de los dos árboles de búsqueda binarios balanceados que contienen elementos O (log M ) lleva cada uno O (log log M ) tiempo. Por tanto, se puede encontrar el sucesor de una clave k , y recuperar su valor, en tiempo O (log log M ). [1]
Buscar el predecesor de una clave k es muy similar a encontrar su sucesor. Se busca en el trie x-fast para el representante más grande r menor que k y se usa r para recuperar su predecesor en el trie x-fast. Finalmente, uno busca en los dos árboles de búsqueda binarios balanceados de estos dos representantes el predecesor de k . Esto lleva O (log log M ) tiempo.
Insertar
Para insertar un nuevo par clave / valor ( k , v ), primero se debe determinar en qué árbol de búsqueda binaria equilibrada se debe insertar k . Con este fin, se encuentra el árbol T que contiene el sucesor de k . A continuación, uno insertos k en T . Para asegurarse de que todos los árboles de búsqueda binarios balanceados contienen elementos O (log M ), se divide T en dos árboles binarios balanceados y se elimina su representante del trie x-fast si contiene más de 2 elementos log M. Cada uno de los dos nuevos árboles de búsqueda binaria equilibrada contiene como máximo elementos log M + 1. Uno elige un representante para cada árbol y lo inserta en el trie x-fast.
Encontrar el sucesor de k lleva O (log log M ) tiempo. Insertar k en un árbol de búsqueda binario balanceado que contiene elementos O (log M ) también toma O (log log M ) tiempo. La división de un árbol de búsqueda binaria que contiene elementos O (log M ) se puede realizar en tiempo O (log log M ). Finalmente, insertar y eliminar los tres representantes toma tiempo O (log M ). Sin embargo, dado que uno divide el árbol como máximo una vez cada O (log M ) inserciones y eliminaciones, esto lleva un tiempo amortizado constante. Por lo tanto, insertar un nuevo par clave / valor toma O (log log M ) tiempo de amortización. [3]
Borrar
Las eliminaciones son muy similares a las inserciones. Uno primero encuentra la clave k en uno de los árboles binarios de búsqueda equilibrados y eliminarla de este árbol T . Para asegurar que todos los árboles de búsqueda binaria balanceados contienen elementos O (log M ), se fusiona T con el árbol de búsqueda binaria balanceada de su sucesor o predecesor si contiene menos de (log M ) / 4 elementos. Los representantes de los árboles fusionados se eliminan del trie x-fast. Es posible que el árbol combinado contenga más de 2 elementos log M. Si este es el caso, el árbol recién formado se divide en dos árboles de aproximadamente el mismo tamaño. A continuación, se elige un nuevo representante para cada uno de los nuevos árboles y se los inserta en el trie x-fast.
Encontrar la clave k lleva O (log log M ) tiempo. Eliminar k de un árbol de búsqueda binario balanceado que contiene elementos O (log M ) también toma O (log log M ) tiempo. Fusionar y posiblemente dividir los árboles de búsqueda binaria balanceada lleva O (log log M ) tiempo. Finalmente, eliminar los antiguos representantes e insertar los nuevos representantes en el trie x-fast lleva O (log M ) tiempo. Sin embargo, la fusión y posiblemente la división del árbol de búsqueda binaria equilibrada se realiza como máximo una vez por cada O (log M ) inserciones y eliminaciones. Por lo tanto, se necesita un tiempo amortizado constante. Por lo tanto, eliminar un par clave / valor lleva O (log log M ) tiempo de amortización. [3]
Referencias
- ↑ a b c Willard, Dan E. (1983). "Las consultas de rango logarítmico del peor caso son posibles en el espacio Θ ( N )". Cartas de procesamiento de información . Elsevier. 17 (2): 81–84. doi : 10.1016 / 0020-0190 (83) 90075-3 . ISSN 0020-0190 .
- ^ Bose, Prosenjit ; Douïeb, Karim; Dujmović, Vida; Howat, John; Morin, Pat (2010), Fast Local Searches and Updates in Bounded Universes (PDF) , Actas de la 22ª Conferencia Canadiense sobre Geometría Computacional (CCCG2010), págs. 261–264
- ^ a b c Schulz, André; Christiano, Paul (4 de marzo de 2010). "Notas de la conferencia de la conferencia 9 de estructuras de datos avanzadas (primavera de 2010, 6.851)" (PDF) . Consultado el 14 de abril de 2011 .