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 choisir?
Quelqu'un peut-il s'il vous plaît expliquer avec un scénario pour chaque structure arborescente pourquoi il est choisi 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 depuis un disque ou un support de stockage lent.
Arborescence RB lorsque vous effectuez des insertions, des suppressions et des extractions assez fréquentes sur l’arbre.
L’arborescence AVL lorsque vos insertions et vos suppressions sont peu fréquentes par rapport à vos extractions.
Je pense que B+ arbres sont un bon usage général a ordonné contenant la structure de données, même dans la mémoire principale. Même lorsque la mémoire virtuelle n'est pas un problème, cache-amitié est souvent le cas, et B+ arbres sont particulièrement bonnes pour un accès séquentiel - la même performance asymptotique comme une liste chaînée, mais avec un cache-amitié à proximité d'un simple tableau. Tout cela et O(log n) de recherche, d'insertion et de suppression.
B+ arbres à problèmes, tels que les articles de se déplacer dans les nœuds lorsque vous effectuer des insertions/suppressions, d'invalider des pointeurs vers ces éléments. J'ai un conteneur de bibliothèque qui ne "curseur" maintenance des curseurs de se joindre à la feuille, elles sont actuellement de référence dans une liste liée, de sorte qu'ils peuvent être fixes ou automatiquement invalidée. Puisqu'il y a rarement plus d'un ou deux curseurs, il fonctionne bien mais il y a peu de travail tout de même.
Une autre chose est que la B+ arbre est essentiellement juste. Je suppose que vous pouvez enlever ou de recréer la non-nœuds-feuille si vous avez besoin d'eux ou pas, mais avec les binaires les nœuds de l'arborescence que vous obtenez beaucoup plus de flexibilité. Un arbre binaire peut être converti à une liste, et en arrière sans avoir à copier les nœuds, il suffit de changer les pointeurs puis n'oubliez pas que vous êtes en la traitant comme une autre structure de données maintenant. Entre autres choses, cela signifie que vous obtenez assez facile O(n) fusion des arbres - convertir les deux arbres de listes, de les fusionner, puis de les convertir en arrière à un arbre.
Encore une autre chose est l'allocation de la mémoire et de la libération. Dans un arbre binaire, ce peut être séparée de celle des algorithmes - l'utilisateur peut créer un nœud appeler ensuite l'insérer algorithme, et supprime pouvez extraire les nœuds (les détacher de l'arbre, mais ne pas libérer la mémoire). Dans un arbre-B ou B+-arbre, qui de toute évidence ne fonctionne pas - les données de vivre dans un environnement multi-élément de nœud. L'écriture de méthodes d'insertion que le "plan" de l'opération sans modifier les nœuds jusqu'à ce qu'ils savent combien de nouveaux nœuds sont nécessaires et qu'elles peuvent être allouées est un défi.
Rouge noir vs AVL? Je ne suis pas sûr que cela fait une grande différence. Ma propre bibliothèque dispose d'une politique basée sur "outil" de la classe de manipuler les nœuds, avec des méthodes pour le double-listes liées, simple d'arbres binaires, s'écartent des arbres, des arbres rouge-noir et treaps, y compris les diverses conversions. Certaines de ces méthodes ont été mis en œuvre seulement parce que je m'ennuyais à un moment ou à un autre. Je ne suis pas sûr que je l'ai même testé le treap méthodes. La raison que j'ai choisi arbres rouge-noir plutôt que AVL est parce que j'ai personnellement comprendre les algorithmes de mieux, ce qui ne veut pas dire qu'ils sont plus simples, c'est juste un hasard de l'histoire que je suis plus familier avec eux.
Une dernière chose: je ne initialement développé mon B+ tree conteneurs comme une expérience. C'est une de ces expériences qui termine jamais vraiment, mais ce n'est pas quelque chose que j'avais à encourager les autres à le répéter. Si vous avez besoin d'un ordre de conteneurs, la meilleure réponse est d'utiliser celui de votre ancienne bibliothèque de l'offre - par exemple std::map etc en C++. Ma bibliothèque a évolué au fil des ans, il a fallu un certain temps pour obtenir de l'écurie, et je viens de relativement récemment découvert qu'il est techniquement non portable (dépend 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 à 32 000 ... Regardez speedtest.pdf de stx-btree .
Lors du choix des structures de données, vous êtes en échange de facteurs tels que
Je voudrais commencer par lire les articles de Wikipédia référencé par Robert Harvey.
De façon pragmatique, lorsque l'on travaille dans des langages tels que Java, le programmeur moyen a tendance à utiliser la collection de classes fournies. Si dans l'optimisation des performances de l'activité que l'on découvre que le rendement de la collecte est difficile, on peut chercher d'autres implémentations. C'est rarement la première chose que l'initiative des entreprises de développement de a à prendre en compte. Il est extrêmement rare que l'on doit mettre en place de telles structures de données à la main, il ya généralement des bibliothèques qui peuvent être utilisés.
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
