Qu'est-ce qu'une implémentation d'arbre C ++ bonne et stable?

Question

Je me demande si quelqu'un peut recommander une bonne implémentation de l'arborescence C ++, espérons-le stl compatible si possible.

Pour mémoire, j'ai déjà écrit plusieurs fois des algorithmes arborescents, et je sais que cela peut être amusant, mais je veux être pragmatique et paresseux, si possible. L’objectif ici est donc de créer un lien réel vers une solution opérationnelle.

Remarque: je recherche un arbre générique, et non un arbre équilibré ou une carte / un ensemble. La structure elle-même et la connectivité de l'arbre sont importantes dans ce cas, pas seulement les données qu'il contient. Chaque branche doit donc pouvoir contenir des quantités arbitraires de données, et chaque branche doit être itérative séparément.

Answer 1

Je ne connais pas vos besoins, mais ne seriez-vous pas mieux avec un graphique (implémentations par exemple dans Graphique de boost ) si vous êtes intéressé principalement par la structure et pas par les avantages spécifiques à l’arborescence tels que la vitesse grâce à l’équilibrage? Vous pouvez "émuler" un arbre à travers un graphique, et peut-être que ce sera plus proche de ce que vous recherchez. Conceptuellement.

Answer 2

Regardez ceci .

La bibliothèque tree.hh pour C ++ fournit une classe de conteneur de type STL pour les arbres n-aire, basée sur les données stockées sur les nœuds. Différents types d'itérateurs sont fournis (post-commande, pré-commande, etc.). Si possible, les méthodes d'accès sont compatibles avec la STL ou d'autres algorithmes sont disponibles.

HTH

Answer 3

Je vais suggérer d'utiliser std :: map au lieu d'un arbre.

Les caractéristiques de complexité d'un arbre sont les suivantes:

Insérer: & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; O (ln (n))

Enlèvement: & Nbsp; & Nbsp; O (ln (n))

Trouvez: & Nbsp; & Nbsp; & Nbsp; & Nbsp; & Nbsp; & Nbsp; & Nbsp; & Nbsp; & Nbsp; O (ln (n))

Ce sont les mêmes caractéristiques que garantit std :: map.
En conséquence, la plupart des implémentations de std :: map utilisent un arbre (arbre rouge-noir) sous les couvertures (bien que cela ne soit techniquement pas nécessaire).

Answer 4

Ok, j'ai trouvé une autre bibliothèque d'arbres. stlplus.ntree . Mais je ne l'ai pas encore essayé.

Answer 5

Si vous n'avez pas de paires (clé, valeur), mais simplement des clés, utilisez std :: set. Cela utilise le même arbre rouge-noir que std :: map.

Answer 6

Supposons que la question porte sur les arbres binaires équilibrés (sous une forme essentiellement rouge noire), même si ce n’est pas le cas.

Les arbres binaires équilibrés, tels que vector, permettent de gérer l'ordre des éléments sans avoir besoin de clé (comme en insérant des éléments n'importe où dans le vecteur), mais:

• Avec O (log (n)) optimal ou meilleure complexité pour toutes les modifications d'un élément (ajouter / supprimer au début, à la fin et avant & et après tout itérateur)
• Avec la persistance des itérateurs par toute modification, à l'exception de la destruction directe de l'élément désigné par l'itérateur.

Il est éventuellement possible de prendre en charge l’accès par index, comme dans vector (avec un coût d’un élément size_t par élément), avec une complexité de O (log (n)). Si utilisés, les itérateurs seront aléatoires.

L’ordre peut éventuellement être appliqué à l’aide de fonctions de comparaison, mais la persistance des itérateurs permet d’utiliser un schéma de comparaison non répétable (ex: changement de voie arbitraire lors d’un embouteillage).

En pratique, l’arbre binaire équilibré possède une interface de vecteur, liste, liste double, carte, carte, carte multiple, deque, file d'attente, priorité_queue ... permettant d'atteindre la complexité théorique optimale O (log (n)) pour toutes les opérations sur un seul élément.

< sarcastique > c’est probablement pourquoi c ++ stl ne le propose pas < / sarcastique >

Les individus ne peuvent pas implémenter l’arbre général équilibré par eux-mêmes, en raison des difficultés à gérer correctement l’équilibrage, en particulier lors de l’extraction d’éléments.

Il n’existe pas d’implémentation largement disponible d’arborescence binaire équilibrée car l’arbre noir rouge à la pointe de la technologie (le meilleur type d’arbre équilibré en raison du nombre fixe de réorganisations coûteuses de l’arborescence lors de l’enlèvement) est connu pour sa mise en oeuvre, copiée servilement par chaque implémenteurs & # 8217; à partir du code initial de l’inventeur de la structure, ne permet pas la persistance de l’itérateur. C’est probablement la raison de l’absence d’un modèle d’arbre entièrement fonctionnel.