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 le même à tous les niveaux. Dans un arbre binaire de recherche, chaque nœud a 2 enfants. Dans un arbre exponentiel, le nombre d'enfants d'un noeud est égal à 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.
Disposition de nœuds 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.
Notes et références
Catégorie:Arbre (structure de données) Catégorie:Exponentielle