Doubly chained tree
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
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
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).