data structures - ¿Qué impide que los árboles de Van Emde Boas sean más populares en las aplicaciones del mundo real?
data-structures van-emde-boas-trees (2)
Una de las razones es que la complejidad no se define en el tamaño del conjunto que almacena sino en el tamaño del universo de valores. Otra diferencia es que las claves no pueden ser tipos arbitrarios para los que tenga operación de comparación, sino que deben ser enteros. No debería ver vEB como una alternativa para BST sino como una alternativa para las matrices. Una matriz tiene O (1) almacena y busca costos para el objeto codificado por enteros. vEB offer O (log log M), donde M es el tamaño del universo de sus valores. Ahora, verá que vEB no es mejor que la matriz regular para búsquedas y almacenamiento, pero ofrece O (1) operaciones mínimas, máximas y O (registro de registro M) prev next operaciones de teclas que la matriz no contiene. Vale la pena mencionar que el diseño de los árboles vEB tiene propiedades que hacen posible la creación de árboles de memoria caché, que son desarrollos mucho más interesantes del CS moderno.
Sabemos que los árboles equilibrados realizan inserción, eliminación y búsqueda en O (log n) -time, los ejemplos incluyen
- Negro rojo
- AVL
- Biselar
- B-tree (y sus variantes).
Sin embargo, cuando las claves son números enteros en un rango limitado, es posible usar un árbol Van Emde Boas para reducir estas operaciones a O (log (log n)) -time, es decir, exponencialmente mejor que los árboles AVL o RB. Bueno, este es realmente el caso de muchas aplicaciones del mundo real.
Veo muchas aplicaciones para esto. Una que me gustaría citar es en bases de datos, para lo cual crear índices básicamente implica elegir entre un árbol Hash o un árbol B *. Si se implementara un árbol Van Emde Boas, proporcionaría una mitad de camino entre estas dos opciones, teóricamente mejorando muchos problemas de optimización de consultas.
Por qué el árbol de Van Emde Boas no se usa ampliamente, como por ejemplo Rojo-Negro o B-Tree desde
- no es una novedad (fue inventado en 1975)
- fácil de implementar
- mucho más rápido que otros árboles
y ¿cuáles son las consideraciones al respecto?
La complejidad asintótica a veces es engañosa. En el caso del Van Emde Boas tree la constante es bastante grande, mira aquí . Yo cito:
However, for small trees the overhead associated with vEB trees
is enormous: on the order of 2^(m/2)
También hay otros casos en los que existe un algoritmo con mejor complejidad pero que solo mejora para una entrada tan grande que en la práctica casi nunca se utiliza, por ejemplo, tiempo lineal RMQ estático.