En informática , un trie y-fast es una estructura de datos para almacenar números enteros de un dominio acotado. Admite consultas exactas y de predecesor o sucesor en tiempo O (log log M ), utilizando un 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 .
Un trie y-fast consta de dos estructuras de datos: la mitad superior es un trie x-fast y la mitad inferior consta de una serie de árboles binarios equilibrados . Las claves se dividen en grupos de O (log M ) elementos consecutivos y para cada grupo se crea un árbol binario de búsqueda equilibrado. Para facilitar la inserción y eliminación eficientes, cada grupo contiene al menos (log M )/4 y como máximo 2 log M elementos. [2] Para cada árbol binario de búsqueda equilibrado se elige un representante r . 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 entero menor 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 entero entre el elemento mínimo y máximo en su árbol.
Dado que el trie x-fast almacena O ( n /log M ) representantes y cada representante aparece en O (log M ) tablas hash, esta parte del trie y-fast utiliza O ( n ) espacio. Los árboles de búsqueda binaria balanceados almacenan n elementos en total, lo que utiliza O ( n ) espacio. Por lo tanto, en total, un trie y-fast utiliza O ( n ) espacio.
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 de matriz asociativa habituales, junto con dos operaciones de orden más , Sucesor y Predecesor :
Una clave k se puede almacenar 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 binario de búsqueda 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 binarios de búsqueda balanceados, en los cuales se busca k .
Encontrar el representante más pequeño r mayor que k en el trie x-rápido lleva O (log log M ). Usando r , encontrar su predecesor lleva un tiempo constante. Buscar en los dos árboles binarios de búsqueda balanceados que contienen O (log M ) elementos cada uno lleva un tiempo O (log log M ). Por lo tanto, se puede encontrar una clave k , y recuperar su valor, en un tiempo O (log log M ). [1]
De manera similar a la clave k , su sucesor 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 x-fast 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 balanceados, en los que se busca el sucesor de k . [3]
Encontrar el representante más pequeño r mayor que k en el trie x-rápido toma O (log log M ) tiempo y usar r para encontrar su predecesor toma un tiempo constante. Buscar en los dos árboles binarios de búsqueda balanceados que contienen O (log M ) elementos toma cada uno O (log log M ) tiempo. Por lo tanto, el sucesor de una clave k se puede encontrar, y su valor se puede recuperar, en O (log log M ) tiempo. [1]
La búsqueda del predecesor de una clave k es muy similar a la búsqueda de su sucesor. Se busca en el trie x-rápido el mayor representante r menor que k y se utiliza r para recuperar su predecesor en el trie x-rápido. Por último, se busca en los dos árboles binarios de búsqueda balanceados de estos dos representantes el predecesor de k . Esto lleva tiempo O (log log M ).
Para insertar un nuevo par clave/valor ( k , v ), primero hay que determinar en qué árbol binario de búsqueda balanceado hay que insertar k . Para ello, se busca el árbol T que contiene el sucesor de k . A continuación, se inserta k en T . Para garantizar que todos los árboles binarios de búsqueda balanceados contengan O (log M ) elementos, se divide T en dos árboles binarios balanceados y se elimina su representante del trie x-fast si contiene más de 2 log M elementos. Cada uno de los dos nuevos árboles binarios de búsqueda balanceados contiene como máximo log M + 1 elementos. Se elige un representante para cada árbol y se inserta en el trie x-fast.
Encontrar el sucesor de k lleva O (log log M ). Insertar k en un árbol binario de búsqueda balanceado que contiene O (log M ) elementos también lleva O (log log M ). Dividir un árbol binario de búsqueda que contiene O (log M ) elementos se puede hacer en O (log log M ). Finalmente, insertar y eliminar los tres representantes lleva 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 lleva O (log log M ) tiempo amortizado. [3]
Las eliminaciones son muy similares a las inserciones. Primero se busca la clave k en uno de los árboles binarios de búsqueda balanceados y se elimina de este árbol T. Para garantizar que todos los árboles binarios de búsqueda balanceados contengan O (log M ) elementos, se fusiona T con el árbol binario de búsqueda balanceado 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 fusionado contenga más de 2 log M elementos. 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 ). Eliminar k de un árbol binario de búsqueda balanceado que contiene O (log M ) elementos también lleva O (log log M ). Fusionar y posiblemente dividir los árboles binarios de búsqueda balanceados lleva O (log log M ). Finalmente, eliminar los antiguos representantes e insertar los nuevos representantes en el trie x-fast lleva O (log M ). Sin embargo, fusionar y posiblemente dividir el árbol binario de búsqueda balanceado se hace como máximo una vez por cada O (log M ) inserciones y eliminaciones. Por lo tanto, lleva un tiempo amortizado constante. Por lo tanto, eliminar un par clave/valor lleva O (log log M ) tiempo amortizado. [3]
Tenga en cuenta que si el elemento que queremos eliminar es una hoja del trie X-fast, entonces ponemos una nota que diga que este número está ahí solo para separar dos árboles de búsqueda binarios, y este número no será devuelto. En este caso, el número no será realmente eliminado. Esto tomará O (1) tiempo, y encontrar la clave k toma O (log log M ) tiempo. Por lo tanto, la complejidad temporal es O (log log M ). [4]