Un árbol de van Emde Boas ( pronunciación holandesa: [vɑn ˈɛmdə ˈboːɑs] ), también conocido como árbol vEB o cola de prioridad de van Emde Boas , es una estructura de datos de árbol que implementa una matriz asociativa con claves enteras de m bits. Realiza todas las operaciones en tiempo O (log m ) , o equivalentemente en tiempo O (log log M ) , donde M = 2 m es el número máximo de elementos que se pueden almacenar en el árbol. La mno debe confundirse con el número real de elementos almacenados en el árbol, mediante el cual a menudo se mide el rendimiento de otras estructuras de datos del árbol. El árbol vEB tiene una buena eficiencia de espacio cuando contiene muchos elementos. Fue inventado por un equipo dirigido por el informático holandés Peter van Emde Boas en 1975. [1]
árbol de van Emde Boas | |||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Tipo | Árbol no binario | ||||||||||||||||||||
Inventado | 1975 | ||||||||||||||||||||
Inventado por | Peter van Emde Boas | ||||||||||||||||||||
Complejidad del tiempo en notación O grande | |||||||||||||||||||||
|
Operaciones admitidas
Un vEB admite las operaciones de una matriz asociativa ordenada , que incluye las operaciones habituales de matriz asociativa junto con dos operaciones de orden más , FindNext y FindPrevious : [2]
- Insertar : inserte un par clave / valor con una clave de m bits
- Eliminar : elimina el par clave / valor con una clave determinada
- Búsqueda : encuentra el valor asociado con una clave determinada
- FindNext : encuentre el par clave / valor con la clave más pequeña que sea mayor que una k dada
- FindPrevious : encuentre el par clave / valor con la clave más grande que es más pequeña que una k dada
Un árbol vEB también admite las operaciones Mínimo y Máximo , que devuelven el elemento mínimo y máximo almacenado en el árbol respectivamente. [3] Ambos corren en O (1) tiempo, ya que el elemento mínimo y máximo se almacenan como atributos en cada árbol.
Función
En aras de la simplicidad, sea log 2 m = k para algún número entero k . Defina M = 2 m . Un árbol T vEB sobre el universo {0, ..., M −1 } tiene un nodo raíz que almacena una matriz. T.children de longitud √ M . T.children [i] es un puntero a un árbol vEB que es responsable de los valores { i √ M , ..., ( i +1) √ M −1 }. Además, T almacena dos valores T.min y T.max así como un árbol vEB auxiliar T.aux .
Los datos se almacenan en un árbol vEB de la siguiente manera: El valor más pequeño actualmente en el árbol se almacena en T.min y el valor más grande se almacena en T.max . Tenga en cuenta que T.min no se almacena en ningún otro lugar del árbol vEB, mientras que T.max es. Si T está vacío, usamos la convención de que T.max = −1 y T.min = M . Cualquier otro valor x se almacena en el subárbol T.niños [i] donde i = ⌊ x / √ M ⌋ . El árbol auxiliar T.aux realiza un seguimiento de los niños que no están vacíos, por lo que T.aux contiene el valor j si y solo si T.children [j] no está vacío.
FindNext
La operacion FindNext (T, x) que busca el sucesor de un elemento x en un árbol vEB procede de la siguiente manera: Si x
función FindNext (T, x) si xentonces devuelve T.min si x ≥ T.max entonces // no hay siguiente elemento devuelve M i = piso (x / √ M ) lo = x mod √ M si lo ños>entonces return ( √ M i) + FindNext (T.niños [i], lo) j = FindNext (T.aux, i) return ( √ M j) + T.children [j] .min end
Tenga en cuenta que, en cualquier caso, el algoritmo realiza O (1) trabajo y luego posiblemente recurre en un subárbol sobre un universo de tamaño M1/2 (un metro/2universo de bits). Esto da una recurrencia para el tiempo de ejecución de, que se resuelve en O (log m ) = O (log log M ) .
Insertar
La llamada insertar (T, x) que inserta un valor x en un árbol vEB T opera de la siguiente manera:
- Si T está vacío, establecemos T.min = T.max = x y ya está.
- De lo contrario, si x
luego insertamos T.min en el subárbol yo responsable de T.min y luego configurar T.min = x . Si T.children [i] anteriormente estaba vacío, luego también insertamos yo en T.aux - De lo contrario, si x> T.max luego insertamos x en el subárbol yo responsable de xy luego establezca T.max = x . Si T.children [i] anteriormente estaba vacío, luego también insertamos yo en T.aux
- De lo contrario, T.min
entonces insertamos x en el subárbol yo responsable de x . Si T.children [i] anteriormente estaba vacío, luego también insertamos yo en T.aux .
En codigo:
función Insertar (T, x) si T.min> T.max entonces // T está vacío T.min = T.max = x; volver si xentonces intercambio (x, T.min) si x> T.max entonces T.max = x i = piso (x / √ M ) lo = x mod √ M Insertar (T.niños [i], lo) si T.niños [i] .min == T.niños [i] .max entonces Insertar (T.aux, i)final
La clave de la eficacia de este procedimiento es que insertar un elemento en un árbol vEB vacío lleva O (1) tiempo. Entonces, aunque el algoritmo a veces hace dos llamadas recursivas, esto solo ocurre cuando la primera llamada recursiva estaba en un subárbol vacío. Esto da la misma recurrencia de tiempo de ejecución de como antes.
Borrar
La eliminación de árboles vEB es la operación más complicada. La llamada Eliminar (T, x) que elimina un valor x de un árbol vEB T opera de la siguiente manera:
- Si T.min = T.max = x entonces x es el único elemento almacenado en el árbol y establecemos T.min = M y T.max = −1 para indicar que el árbol está vacío.
- De lo contrario, si x == T.min, entonces necesitamos encontrar el segundo valor más pequeño y en el árbol vEB, eliminarlo de su ubicación actual y establecer T.min = y . El segundo valor más pequeño y es T.children [T.aux.min] .min , por lo que se puede encontrar en el tiempo O (1) . Eliminamos y del subárbol que lo contiene.
- Si x ≠ T.min y x ≠ T.max luego eliminamos x del subárbol T.children [i] que contiene x .
- Si x == T.max, entonces necesitaremos encontrar el segundo valor más grande y en el árbol vEB y establecer T.max = y . Empezamos borrando x como en el caso anterior. Entonces el valor y es T.min o T.children [T.aux.max] .max , por lo que se puede encontrar en el tiempo O (1) .
- En cualquiera de los casos anteriores, si borramos el último elemento X o Y de cualquier subárbol T.children [i] luego también eliminamos i de T.aux .
En codigo:
función Eliminar (T, x) si T.min == T.max == x entonces T.min = M T.max = −1 devuelve si x == T.min entonces hi = T.aux.min * √ M j = T.aux.min T.min = x = hi + T.niños [j] .min i = piso (x / √ M ) lo = x mod √ M Eliminar (T.niños [i], lo) si T.children [i] está vacío, entonces Eliminar (T.aux, i) si x == T.max entonces si T.aux está vacío entonces T.max = T.min si no hi = T.aux.max * √ M j = T.aux.max T.max = hi + T.niños [j] .maxfinal
Nuevamente, la eficiencia de este procedimiento depende del hecho de que eliminar de un árbol vEB que contiene solo un elemento toma solo un tiempo constante. En particular, la segunda llamada a Delete solo se ejecuta si x era el único elemento en T.children [i] antes de la eliminación.
Discusión
La suposición de que log m es un número entero es innecesaria. Las operaciones y se puede reemplazar tomando solo los bits de orden superior ⌈ m / 2⌉ y los de orden inferior ⌊ m / 2⌋ de x , respectivamente. En cualquier máquina existente, esto es más eficiente que los cálculos de división o resto.
La implementación descrita anteriormente usa punteros y ocupa un espacio total de O ( M ) = O (2 m ) . Esto se puede ver de la siguiente manera. La recurrencia es. Resolver eso conduciría a. Afortunadamente, también se puede demostrar que S ( M ) = M −2 por inducción. [4]
En implementaciones prácticas, especialmente en máquinas con shift-by-k y encontrar las primeras instrucciones de cero , el rendimiento se puede mejorar aún más cambiando a una matriz de bits una vez que se alcanza m igual al tamaño de la palabra (o un pequeño múltiplo del mismo). Dado que todas las operaciones sobre una sola palabra son de tiempo constante, esto no afecta el rendimiento asintótico, pero sí evita la mayor parte del almacenamiento de punteros y varias desreferencias de punteros, logrando un importante ahorro práctico en tiempo y espacio con este truco.
Una optimización obvia de los árboles vEB es descartar subárboles vacíos. Esto hace que los árboles vEB sean bastante compactos cuando contienen muchos elementos, porque no se crean subárboles hasta que es necesario agregarles algo. Inicialmente, cada elemento agregado crea aproximadamente log ( m ) árboles nuevos que contienen aproximadamente m / 2 punteros en total. A medida que el árbol crece, se reutilizan más y más subárboles, especialmente los más grandes. En un árbol completo de elementos de 2 m , solo se utiliza un espacio de O (2 m ) . Además, a diferencia de un árbol de búsqueda binario, la mayor parte de este espacio se utiliza para almacenar datos: incluso para miles de millones de elementos, los punteros en un árbol vEB completo se cuentan por miles.
Sin embargo, para los árboles pequeños, la sobrecarga asociada con los árboles vEB es enorme: del orden de . Ésta es una de las razones por las que no son populares en la práctica. Una forma de abordar esta limitación es usar solo un número fijo de bits por nivel, lo que da como resultado un ensayo . Alternativamente, cada tabla puede ser reemplazada por una tabla hash , reduciendo el espacio a O ( n log M ) (donde n es el número de elementos almacenados en la estructura de datos) a expensas de hacer que la estructura de datos sea aleatoria. Se han propuesto otras estructuras, incluidos los intentos y-fast y los intentos x-fast que tienen tiempos de consulta y actualización comparables y también utilizan tablas hash aleatorias para reducir el espacio a O ( n ) u O ( n log M ) .
Ver también
Referencias
- ↑ Peter van Emde Boas : Preservar el orden en un bosque en menos de un tiempo logarítmico ( Actas del 16º Simposio Anual sobre Fundamentos de la Ciencia de la Computación 10: 75-84, 1975)
- ^ Gudmund Skovbjerg Frandsen : Algoritmos dinámicos: Notas del curso sobre árboles de van Emde Boas (PDF) ( Universidad de Aarhus , Departamento de Ciencias de la Computación)
- ^ Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest y Clifford Stein . Introducción a los algoritmos , tercera edición. MIT Press , 2009. ISBN 978-0-262-53305-8 . Capítulo 20: El árbol de van Emde Boas, págs. 531–560.
- ^ Rex, A. "Determinación de la complejidad espacial de los árboles de van Emde Boas" . Consultado el 27 de mayo de 2011 .
Otras lecturas
- Erik Demaine, Sam Fingeret, Shravas Rao, Paul Christiano. Instituto de Tecnología de Massachusetts. 6.851: Estructuras de datos avanzadas (primavera de 2012). Notas de la lección 11 . 22 de marzo de 2012.
- van Emde Boas, P .; Kaas, R .; Zijlstra, E. (1976). "Diseño e implementación de una cola prioritaria eficiente". Teoría de sistemas matemáticos . 10 : 99-127. doi : 10.1007 / BF01683268 .