Quel est le nom de l'arbre binaire (ou la famille des arbres binaires ), qui est équilibré, et a le nombre minimum de nœuds possible pour sa hauteur?Arbre binaire spécial
Eh bien c'est un type spécial d'arbre pas l'arbre AVL.
Arbre rouge-noir?
L'un de http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree#Implementations?
Si l'arbre binaire est équilibré alors, il est une fonction de ses nœuds (n). height = log n. donc un arbre équilibré n'a pas de gamme de hauteurs.
Et qu'en est-il de RB-tree alors? Il est équilibré mais peut avoir des hauteurs différentes de ses nœuds feuilles (fondamentalement 2x différence au maximum) - http://en.wikipedia.org/wiki/Red-black_tree. – IgorK
un arbre RB est autorisé à être presque équilibré, c'est ainsi qu'il y a une gamme de ses hauteurs (est également dans l'entrée de Wikipedia: "l'arbre est à peu près équilibré" – Alon
Le nombre minimal de nœuds qu'un arbre binaire complètement équilibré peut avoir pour la hauteur d est 2^(d-1) +1. Pour autant que je sache, ce type n'a pas de nom.
Le nombre maximal de nœuds est de 2^d. C'est ce qu'on appelle un arbre complet. Tous les calques sont complètement remplis et chaque noeud a 2 ou 0 childern (implicite).
Le nom de l'arbre binaire (ou la famille des arbres binaires), qui a le nombre minimum de nœuds possibles pour sa hauteur est une liste chaînée: D
Ne vous dire nombre maximal de noeuds pour sa hauteur? – JPvdMerwe