Arbres binaires - Tri par tas

Extraits

[...] Ainsi, il est visible dans l'expression qu'à chaque itération de on ajoute le double d'éléments dans l'ensemble associé. La propriété de tels arbres est donc que si on considère les feuilles une à une, la hauteur associée est constante égale à . Question 14. On voit dans le tableau que le sous arbre gauche va de l'indice 3 à l'indice 21 soit l'intervalle (parenthèses comprises). On voit dans le tableau que le sous arbre droit va de l'indice 23 à l'indice 41 soit l'intervalle (parenthèses comprises). [...]

[...] Arbres binaires - Tri par tas Question 1 - Premier cas : Les nombres qui se retrouvent sans enfants adoptifs sont les nombres pour lesquels , soit . Ainsi, les nombres qui se retrouvent sans enfants adoptifs sont les nombres compris entre et . - Second cas : Les nombres qui se retrouvent sans enfants adoptifs sont les nombres pour lesquels , soit . Ainsi, les nombres qui se retrouvent sans enfants adoptifs sont les nombres compris entre et . - Premier cas : Les nombres qui se retrouvent avec un seul enfant adoptif sont les nombres pour lesquels , soit . [...]

[...] Ainsi, est la puissance de 2 maximale telle que ou alors la puissance de 2 minimale telle que . On a : 1 2 3 4 5 6 7 8 9 10 11 12 Il semble donc que pour le nombre de l'ensemble associé correspondant à un sommet, correspond à élevé à la puissance du numéro de ligne (commençant par 0). Pour ce qui est du reste de la division de par, on a : 1 2 3 4 5 6 7 8 9 10 11 12 1 1 2 3 1 2 3 4 Il semble donc que pour le nombre de l'ensemble associé correspondant à un sommet, retourne l'indice de ce sommet dans la ligne (en commençant par 0). [...]

[...] Si est impair, est un nombre entier : c'est lui qui adopte . Ainsi, tous les nombres supérieurs ou égaux à auront un parent adoptif : aucun ne tombera sur le sol. Le nombre , quant à lui, est attaché à l'arbre donc ne tombe pas sur le sol non plus. Généralisation pour quelconque : - Les nombres qui se retrouvent sans enfants adoptifs sont les nombres tels que , soit (avec entier). Les nombres qui se retrouvent sans enfants adoptifs sont dont les nombres entiers compris entre et - Les nombres qui se retrouvent avec un seul enfant adoptif sont les nombres entiers tels que et . [...]

[...] - Quel que soit , il n'y a aucun nombre orphelin n'ayant pas de parents adoptifs (voir question précédente pour la démonstration) Question 2 On obtient : Si est le niveau de , le niveau de et de est On a le découpage suivant : - Niveau : nombre - Niveau 2 : nombres compris entre et - Niveau 3 : nombres compris entre et - Niveau 4 : nombres compris entre et - Niveau 5 : nombres compris entre et Question 3 : - Nous allons d'abord montrer, comme demandé par l'énoncé, qu'on peut remplacer les implications par des équivalences dans la règle 3 : Supposons . Alors, d'après l'implication on a : D'où L'implication est donc une équivalence. - Supposons maintenant que est un entier strictement positif tel que . - On a alors (règle et donc - On en déduit, d'après la règle 1 que . Supposons que . On aurait alors un nombre impair ( qui serait égal à un nombre pair ( ce qui est impossible d'après la règle 4. Ainsi et finalement Question 4 - Supposons . [...]