Question arbre "tas"

Un arbre parfaitement complet aura toujours 2^h-1 valeurs (h est la hauteur de l'arbre, ici h=3) :

   8    
 5   7  
1 4 6 3

Un arbre presque complet aura un nombre quelconque de valeurs, mais seules les feuilles les plus à droites seront manquantes :

   8         8         8   
 5   7     5   7     5   7 
1 4 6     1 4       1     

En général quand on dit arbre complet (sans préciser) on sous-entends arbre presque complet.

Ces arbres ne sont pas complets (ni parfaitement complet, ni presque complet) :

   8         8         8         8    
 5   7     5   7     5   7     5      
  4 6 3   1   6 3   1 4   3   1 4    

Une manière simple de savoir si un arbre est complet c'est de représenter le tableau associé, avec des arbres non-complets tu vas avoir des "trous" :

Parfaitement complet :

[8,5,7,1,4,6,3]

Presque complets :

[8,5,7,1,4,6], [8,5,7,1,4], [8,5,7,1]

Pas complet :

[8,5,7,_,4,6,3], [8,5,7,1,_,6,3], [8,5,7,1,4,_,3], [8,5,_,1,4]

Là on joue un peu sur le vocabulaire, parce que l'arbre parfait est un cas particulier d'arbre complet (ce que j'appelais arbre parfaitement complet).

Parce qu'on a une question dans le projet :

- Quels sont les nombres minimum et maximum d'éléments dans un tas de hauteur h.

J'ai répondu à cela :
1 noeud = 2^0 -> hauteur 0
2 = 2^1 -> 1
3-> 1
4 = 2^2 -> 2
5 -> 2
....
8 = 2^3 -> 3
Le nombre maximum d'éléments dans un tas de hauteur h c'est lorsque l'arbre est complet et donc c'est juste avant un changement de hauteur.

Le nombre maximum d'éléments dans un tas de hauteur h est : 2^(h+1)-1 avec h la hauteur.

De la même manière, pour une hauteur de h, le nombre minimum d'éléments dans un tas c'est l'arbre qui correspond à la limite du passage à la hauteur suivante. Autrement dit, si on enlève un élément à cet arbre on descend une hauteur. Il s'agit donc de 2^h avec h qui est égal à la hauteur.

Est-ce correct ?

Non, ce n'est pas correct, ne serait-ce que le début : 1 noeud ? hauteur 0, ça ne va pas, s'il y a un noeud alors il y a une hauteur, sinon quelle serait la hauteur d'un arbre vide ?
En plus sans le savoir je t'ai donné cette réponse tout à l'heure : "Un arbre parfaitement complet aura toujours 2^h-1 valeurs (h est la hauteur de l'arbre)"

Chez nous, on dit que la hauteur 0 c'est un noeud.

Et si je change juste le fait qu'on commence par hauteur 1 c'est bon le reste ? Le principe je veux dire...

L'ordre dans un tas n'est pas nécessairement le plus grand à la racine, ça peut aussi être le plus petit, il faut juste que ce soit homogène. C'est à dire que soit on a toujours valeur(père)≥valeur(fils), soit on a toujours l'inverse c'est à dire valeur(père)≤valeur(fils). Donc tous les tableaux triés, que se soit par ordre croissant ou décroissant, sont des tas. Mais il y a aussi des tas qui ne sont pas triés.

Bah oui, ça dépend sur quel ordre est définit le tas, en plus ici tu réfléchis uniquement en terme de nombres (donc croissant ou décroissant) alors qu'en pratique les clés d'un tas peuvent être n'importe quoi (assez simple) et il peut y avoir plusieurs ordres acceptables...

Comment faire une bonne démonstration que le nombre maximum d'éléments dans un tas de hauteur h est : 2^(h+1)-1 avec h la hauteur. et le nombre minimum d'éléments est 2^h. ???

Il "suffit" de compter chaque étage, sachant que tu sais qu'au maximum chaque noeud a deux sous-arbre, ça veut dire que chaque "étage" contient le double du précédent, on a donc 2^k noeuds à l'étage k, et la somme de tous les étages te donnera ce que tu cherches.