Quand choisir l'arbre RB, B-Tree ou un arbre AVL?

Question

En tant que programmeur quand dois-je envisager d'utiliser un arbre RB, arbre B ou un arbre AVL? Quels sont les points clés qui doivent être pris en considération avant de décider du choix?

Quelqu'un peut-il expliquer s'il vous plaît avec un scénario pour chaque structure d'arbre pourquoi il est choisi sur les autres en se référant aux points clés?

Answer 1

Prenez cela avec une pincée de sel:

B-tree lorsque vous gérez plus que des milliers d'articles et vous les pagination d'un disque ou d'un support de stockage lent.

arbre RB lorsque vous faites des inserts assez fréquents, et supprime les récupérations sur l'arbre.

arbre AVL lorsque vos insertions et suppressions sont peu fréquentes par rapport à vos récupérations.

Answer 2

Je pense que B + arbres sont un bon usage général structure de données de conteneurs commandés, même dans la mémoire principale. Même lorsque la mémoire virtuelle est pas un problème, cache-convivialité est souvent, et des arbres B + sont particulièrement bons pour l'accès séquentiel - la même performance asymptotique comme une liste liée, mais avec cache-convivialité proche d'un simple tableau. Tout cela et O (log n) recherche, insérer et supprimer.

B + arbres ont des problèmes, mais - comme les éléments qui se déplacent à l'intérieur des noeuds lorsque vous faites insertions / suppressions, des pointeurs vers ces invalidant articles. J'ai une bibliothèque de conteneurs qui fait « l'entretien du curseur » - curseurs se fixent au nœud de la feuille auxquels ils font référence actuellement dans une liste chaînée, de sorte qu'ils peuvent être fixes ou automatiquement invalidés. Comme il y a rarement plus d'un ou deux curseurs, cela fonctionne bien -. Mais il est un peu de travail supplémentaire tout de même

Une autre chose est que l'arbre B + est essentiellement cela. Je suppose que vous pouvez dépouiller ou recréer les noeuds non-feuilles selon que vous avez besoin ou non, mais avec des noeuds d'arbres binaires, vous obtenez beaucoup plus de flexibilité. Un arbre binaire peut être converti en une liste, et en arrière sans copier nœuds - vous venez de changer les pointeurs alors souvenez-vous que vous traitez comme une structure de données différente maintenant. Entre autres choses, cela signifie que vous obtenez O assez facile (n) la fusion des arbres - convertir les deux arbres à des listes, les fusionner, puis reconvertir un arbre

.

Une autre chose est l'allocation de mémoire et la libération. Dans un arbre binaire, cela peut être séparé des algorithmes - l'utilisateur peut créer un nœud puis appelez l'algorithme d'insertion, et supprime peut extraire les noeuds (les détacher de l'arbre, mais ne libérer la mémoire). Dans un B-arbre ou arbre B +, qui ne fonctionne évidemment pas - les données vont vivre dans un nœud multi-élément. méthodes d'insertion écrit « plan » l'opération sans modifier nœuds jusqu'à ce qu'ils sachent combien de nouveaux nœuds sont nécessaires et qu'ils peuvent être attribués est un défi.

noir rouge contre AVL? Je ne suis pas sûr que cela fasse une grande différence. Ma bibliothèque a une base politique de classe « outil » pour manipuler les nœuds, avec des méthodes pour les listes doubles liés, simples arbres binaires, des arbres, des arbres évasement rouge-noir et treaps, y compris diverses conversions. Certaines de ces méthodes ont été mises en œuvre parce que je ne me suis ennuyé à un moment ou un autre. Je ne suis pas sûr que je l'ai même testé les méthodes de Treap. La raison pour laquelle je choisi des arbres rouge-noir plutôt que AVL est parce que je comprends personnellement les algorithmes mieux -. Qui ne veut pas dire qu'ils sont plus simples, il est juste un coup de chance de l'histoire que je suis plus familier avec eux

Une dernière chose - je ne développé à l'origine de mes B + conteneurs arbre comme une expérience. Il est l'une de ces expériences qui ne ont fini vraiment, mais ce n'est pas quelque chose que je vous encourage d'autres à répéter. Si vous avez besoin est un conteneur ordonné, la meilleure réponse est d'utiliser celle que votre bibliothèque existante fournit - par exemple std :: carte etc en C ++. Ma bibliothèque a évolué au fil des années, il a fallu un bon moment pour l'obtenir stable, et je viens relativement récemment découvert qu'il est techniquement non portable (dépendant d'un peu de comportement non défini WRT offsetof).

Answer 3

Dans la mémoire B-Tree a l'avantage lorsque le nombre d'articles est plus 32000 ... Regardez de href="https://github.com/bingmann/stx-btree" rel="nofollow"> stx-btree .

Answer 4

Lors du choix des structures de données que vous négociez de facteurs tels que

• vitesse de récupération v vitesse de mise à jour
• comment la structure fait face aux pires opérations de cas, par exemple l'insertion d'enregistrements qui arrivent dans un ordre de tri
• espace perdu

Je commencerais en lisant les articles de Wikipedia référencés par Robert Harvey.

Pragmatique, lorsque l'on travaille dans des langages tels que Java le programmeur moyen a tendance à utiliser les classes de collecte prévus. Si une activité d'optimisation des performances que l'on découvre les performances de collecte est problématique, on peut alors rechercher d'autres implémentations. Il est rarement la première chose qu'un développement commercial dirigé doit prendre en compte. Il est extrêmement rare que l'on a besoin de mettre en œuvre de telles structures de données à la main, il y a généralement des bibliothèques qui peuvent être utilisés.