L'utilisation d'un arbre 2-3-4 au lieu d'un arbre évasement

Question

Je suis bien sûr en ce moment dans une des structures de données et nous avons appris 2-3-4 arbres et ébrasés. Je me demandais dans quelles circonstances utiliseriez-vous un arbre 2-3-4 au lieu d'un arbre évasement? Ils sont tous les deux auto équilibrage et triés, donc je ne vois pas beaucoup de différence entre eux.

Answer 1

2-3-4 arbre ne modifie que la structure sur les insertions et suppressions, tandis qu'un évasement-tree aussi réorganise les noeuds sur les recherches.

arbres Splay sera, grâce à la réorganisation de recherche, fournir des réponses plus rapidement si votre modèle d'utilisation typique arrive à rechercher un petit sous-ensemble d'éléments la plupart du temps.

Il est possible de mettre en place un 2-3-4 arbre de sorte que le plus petit élément peut être regardé en O (1), mais généralement à la fois l'insertion de l'offre et la suppression à O amorti (log n).