Doubly chained tree
Cet article peut contenir un travail inédit ou des déclarations non vérifiées ().
Vous pouvez aider en ajoutant des références ou en supprimant le contenu inédit.
Cette section ou cet article est une traduction incomplète ().
Vous pouvez modifier la page pour effectuer la traduction.
En informatique, un arbre « double chaîne » ou Doubly chained tree peut s'entendre de deux manières :
- Au niveau technique : utilisation deux liens (pointeurs) seulement (voir les arbres dits left-child right-sibling binary tree[1])
- Au niveau conceptuel : un ensemble de listes double chaînes organisées dans une structure hiérarchique (arbre), ce qui implique au moins l'usage d'un troisième lien pour gérer la hiérarchie.
Est abordée ci-dessous la notion d'arbre double chaîne au niveau conceptuel, pour les double-chaînes techniques.
Définition
[modifier | modifier le code]Un arbre double chaîne au niveau conceptuel doit pouvoir permettre la navigation transparente élémentaire dans l'arbre (élément suivant ou précédent, élément parent ou élément(s) fils) quel que soit le contexte de l'élément courant.
Applications
[modifier | modifier le code]L'intérêt d'une telle implémentation consiste en l'absence de restriction quant à la navigation élémentaire ceci permettant plus de souplesse pour les optimisations algorithmiques du parcours de l'arbre. Les opérations élémentaires des tableaux associatifs (ajout, modification, suppression, recherche, tableau associatif) sont donc facilités par l'implémentation. Le fait qu'un élément unitaire puisse être considéré virtuellement indépendamment de la structure permet d'envisager d'autres primitives ou des usages fonctionnels convergents (gestion de la mémoire).
