Quand choisir l'arbre RB, l'arbre B ou l'arbre AVL?

En tant que programmeur, quand devrais-je envisager d'utiliser un arbre RB, un arbre B ou un arbre AVL? Quels sont les points clés à prendre en compte avant de décider du choix?

Quelqu'un peut-il expliquer avec un scénario pour chaque structure arborescente pourquoi elle est choisie par rapport aux autres en référence aux points clés?

Prenez ceci avec une pincée de sel:

B-tree lorsque vous gérez plus de milliers d'éléments et que vous les paginez à partir d'un disque ou d'un support de stockage lent.

Arbre RB lorsque vous effectuez des insertions, des suppressions et des récupérations assez fréquentes sur l'arbre.

Arborescence AVL lorsque vos insertions et suppressions sont peu fréquentes par rapport à vos extractions.

Je pense que les arbres B + sont une bonne structure de données de conteneur ordonnée à usage général, même dans la mémoire principale. Même lorsque la mémoire virtuelle n'est pas un problème, la convivialité du cache l'est souvent, et les arbres B + sont particulièrement bons pour l'accès séquentiel - les mêmes performances asymptotiques qu'une liste chaînée, mais avec une convivialité du cache proche d'un simple tableau. Tout cela et O (log n) rechercher, insérer et supprimer.

Les arborescences B + ont cependant des problèmes - tels que les éléments se déplaçant dans les nœuds lorsque vous insérez / supprimez, ce qui invalide les pointeurs vers ces éléments. J'ai une bibliothèque de conteneurs qui fait la "maintenance du curseur" - les curseurs se fixent au nœud feuille qu'ils référencent actuellement dans une liste liée, afin qu'ils puissent être automatiquement corrigés ou invalidés. Comme il y a rarement plus d'un ou deux curseurs, cela fonctionne bien - mais c'est tout de même un peu plus de travail.

Une autre chose est que l'arbre B + est essentiellement juste cela. Je suppose que vous pouvez supprimer ou recréer les nœuds non-feuilles selon que vous en avez besoin ou non, mais avec des nœuds d'arbre binaire, vous obtenez beaucoup plus de flexibilité. Un arbre binaire peut être converti en liste chaînée et inversement sans copier de nœuds - il vous suffit de changer les pointeurs, puis de vous rappeler que vous le traitez maintenant comme une structure de données différente. Entre autres choses, cela signifie que vous obtenez une fusion O (n) assez facile des arbres - convertissez les deux arbres en listes, fusionnez-les, puis reconvertissez-les en arbre.

Encore une autre chose est l'allocation et la libération de mémoire. Dans un arbre binaire, cela peut être séparé des algorithmes - l'utilisateur peut créer un nœud puis appeler l'algorithme d'insertion, et les suppressions peuvent extraire les nœuds (les détacher de l'arborescence, mais ne pas libérer la mémoire). Dans un arbre B ou un arbre B +, cela ne fonctionne évidemment pas - les données vivront dans un nœud multi-éléments. Ecrire des méthodes d'insertion qui «planifient» l'opération sans modifier les nœuds jusqu'à ce qu'ils sachent combien de nouveaux nœuds sont nécessaires et qu'ils peuvent être alloués est un défi.

Rouge noir vs AVL? Je ne suis pas sûr que cela fasse une grande différence. Ma propre bibliothèque a une classe "outil" basée sur des règles pour manipuler les nœuds, avec des méthodes pour les listes à double lien, les arbres binaires simples, les arbres splay, les arbres rouge-noir et les treaps, y compris diverses conversions. Certaines de ces méthodes n'ont été mises en œuvre que parce que je m'ennuyais à un moment ou à un autre. Je ne suis pas sûr d'avoir même testé les méthodes treap. La raison pour laquelle j'ai choisi les arbres rouge-noir plutôt que AVL est que je comprends personnellement mieux les algorithmes - ce qui ne signifie pas qu'ils sont plus simples, c'est juste un hasard de l'histoire que je les connais mieux.

Une dernière chose - je n'ai développé à l'origine mes conteneurs d'arbres B + qu'à titre expérimental. C'est une de ces expériences qui ne s'est jamais vraiment terminée, mais ce n'est pas quelque chose que j'encouragerais les autres à répéter. Si tout ce dont vous avez besoin est un conteneur ordonné, la meilleure réponse est d'utiliser celui que votre bibliothèque existante fournit - par exemple std :: map etc en C ++. Ma bibliothèque a évolué au fil des années, il a fallu un certain temps pour la stabiliser, et j'ai récemment découvert qu'elle est techniquement non portable (dépend d'un peu de comportement indéfini WRT offsetof).

En mémoire, B-Tree a l'avantage lorsque le nombre d'éléments est supérieur à 32000 ... Regardez speedtest.pdf de stx-btree .

Lorsque vous choisissez des structures de données, vous échangez des facteurs tels que

• vitesse de récupération v vitesse de mise à jour
• la capacité de la structure à gérer les opérations les plus défavorables, par exemple l'insertion d'enregistrements qui arrivent dans un ordre trié
• espace gaspillé

Je commencerais par lire les articles Wikipédia référencés par Robert Harvey.

De manière pragmatique, lorsqu'il travaille dans des langages tels que Java, le programmeur moyen a tendance à utiliser les classes de collection fournies. Si, dans une activité de réglage des performances, on découvre que les performances de la collection sont problématiques, on peut rechercher des implémentations alternatives. C'est rarement la première chose qu'un développement dirigé par une entreprise doit prendre en compte. Il est extrêmement rare que l'on ait besoin d'implémenter de telles structures de données à la main, il existe généralement des bibliothèques qui peuvent être utilisées.