Qu'est-ce qui empêche les arbres Van Emde Boas d'être plus populaires dans les applications du monde réel?
Nous savons que les arbres équilibrés effectuent l'insertion, la suppression et la recherche dans O (log n) - time, par exemple
- Rouge-Noir
- AVL
- Splay
- B-tree (et ses variantes).
Cependant, lorsque les clés sont des entiers dans une plage limitée, il est possible d'utiliser un arbre Van Emde Boas pour réduire ces opérations à O(log(log n))-time, c'est-à-dire exponentiellement meilleur que les arbres AVL ou RB. Eh bien, c'est en fait le cas de nombreux monde réel application.
Je vois beaucoup d'applications pour cela. Celui que je voudrais citer est sur les bases de données, pour lesquelles la création d'index implique essentiellement de choisir entre un hachage ou un b*-tree. Si un arbre Van Emde Boas était implémenté, il fournirait un mi-chemin entre ces deux options, améliorant théoriquement de nombreux problèmes d'optimisation des requêtes.
Pourquoi L'arbre Van Emde Boas n'est pas largement utilisé comme rouge-noir ou B-tree depuis
- ce n'est pas une nouveauté (il a été inventé en 1975)
- facile à mettre en œuvre
- beaucoup plus rapide que les autres arbres
Et quelles sont les considérations à ce sujet?
2 réponses
La complexité asymptotique est parfois trompeuse. Dans le cas de Van Emde Boas tree la constante est assez grand voir ici. Je cite:
However, for small trees the overhead associated with vEB trees
is enormous: on the order of 2^(m/2)
Il y a aussi d'autres cas où un algorithme avec une meilleure complexité existe mais il ne s'améliore que pour une entrée si grande qu'en pratique il n'est presque jamais utilisé par exemple RMQ Statique linéaire.
L'Une des raisons en est que la complexité est définie non pas sur la taille de la vous magasin, mais sur la taille de l'univers des valeurs. Une autre différence est que les clés ne peuvent pas être des types arbitraires pour lesquels vous avez une opération de comparaison mais doivent être des entiers. Vous ne devriez pas voir vEB comme une alternative pour BST mais plutôt comme une alternative pour les tableaux. Un tableau A O(1) stocker et rechercher les coûts pour l'objet saisi par des entiers. VEB offre O (log log M), où M est la taille de l'univers de vos valeurs. Maintenant, vous voir vEB n'est pas meilleur que le tableau régulier pour les recherches et le magasin, mais il offre des opérations O(1) Min, max et O (log log m) précédent suivant opérations clés que le tableau ne fait pas. Il est à noter que la disposition des arbres vEB a des propriétés qui permettent de créer des arbres inconscients de cache qui sont des développements beaucoup plus intéressants de CS moderne.