Arbre exponentiel
Cet article est une ébauche concernant l’informatique théorique.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
Un arbre exponentiel est presque identique à un arbre binaire de recherche, à l'exception que le nombre d'enfants des nœuds de l'arbre n'est pas la même à tous les niveaux. Dans un arbre binaire de recherche, chaque nœud a 2 enfants. Dans un arbre exponentiel, la dimension[Quoi ?] est égale à la profondeur du nœud (le nœud racine ayant une profondeur d = 1), c'est-à-dire qu'un nœud de profondeur d aura 2d enfants qui auront chacun deux fois plus d'enfants. Ainsi, le deuxième niveau peut contenir quatre nœuds, le troisième peut contenir huit nœuds, le quatrième 16 nœuds, etc.[1]
Disposition de nœuds[modifier | modifier le code]
Le terme « arbre exponentiel » peut également faire référence à une méthode de disposition des nœuds d'une structure arborescente dans un espace de dimension n (généralement 2). Les nœuds sont placés plus près d'une ligne de base que leur parent, par un facteur égal au nombre de nœuds enfants de ce nœud parent (éventuellement pondéré), et mis à l'échelle en fonction de leur proximité. Ainsi, quelle que soit la profondeur de l'arbre, il y a toujours de la place pour plus de nœuds. L'ensemble a une structure fractale[2].
Notes et références[modifier | modifier le code]
- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Exponential tree » (voir la liste des auteurs).
- (en) Andersson, Arne, « Faster deterministic sorting and searching in linear space », Proceedings of 37th Conference on Foundations of Computer Science, , p. 135-141 (lire en ligne)
- (en) Lamping, John and Rao, Ramana, « Laying out and visualizing large trees using a hyperbolic space », Proceedings of the 7th annual ACM symposium on User interface software and technology, , p. 13-14 (lire en ligne)
