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 2^d 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]

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].

• (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).

• Portail de l'informatique théorique