Bonjour à tous,
J'essaye actuellement de résoudre un problème proposé par les auteurs du livre "Introduction à l'algorithmie" (le Cormen pour ceux qui connaissent). Ce problème concerne les arbres binomiaux et la numérotation de leur noeud dans l'ordre postfixe.
Il faut montrer qu'à la profondeur i, une étiquette (numéro du noeud en base 2) possède (k - i) '1'. J'ai différentes idées mais aucune ne semblent pouvoir me faire avancer...
J'expose rapidement mes idées.
Un arbre binomial Bk contient 2^k noeuds donc à l'aide d'un parcours postfixe, la racine de ce sous arbre est numérotée 2^k - 1 (On numérote à partir de 0). Donc à partir de là j'ai essayé de trouver une règle de numérotation pour les noeuds situés à une même profondeur en utilisant la définition sur la construction d'un Bk à partir de ses k - 1 fils... Mais je ne sais pas trop comment conclure...
Ensuite j'ai tenté de trouver une relation entre un noeud et son frère. Toujours dans l'espoir de montrer que le nombre de 1 ne varie pas (à l'aide d'opération de décalage liées aux puissances de 2 etc).
J'ai également essayé avec le nombre de noeuds présents à une certaine profondeur (combinaison de i parmi k à la profondeur i d'un Bk)...
Bref, j'ai testé pas mal de chose (peut-être un peu trop...) et je commence à me demander si je ne loupe pas quelque chose de "simple".
Si vous pouviez m'aiguiller dans une direction ou dans une autre, merci à vous
--
sperca
-----