Arbre Binaire et leur rang :

Arbre Binaire et leur rang : - Divers - Programmation

Marsh Posté le 25-12-2004 à 01:37:16    

Bonjour il me faut une fonction qui a chaque arbre associe son rang :
 
voir image : http://www.chez.com/picco/Ftp/inde [...] open=¤Taff (désolé elle voulai pas s'inclure !)
 
suggestion : on admettra qu'il y a (n parmi 2n)/n+1 arbre à n feuilles  
remarquer que pour n feuilles nous avons n-1 noeud interne  
 
 
Voila ce que me dis le sujet le probléme est que j'trouve même pas une idée d'algoritme rien ! si qq1 vois qq chose,  
 
j'dois faire ca en caml mon type Arbre = Feuille | Noeud of (Arbre*Arbre)
 
mais ca a la limite on s'enfou si qq1 a juste une idée d'algorithme moi j'vois vraiment pas :/ sinon tanpis merci joyeu noel !


Message édité par picco le 25-12-2004 à 01:47:12
Reply

Marsh Posté le 25-12-2004 à 01:37:16   

Reply

Marsh Posté le 25-12-2004 à 14:40:08    

ce topic aurait sa place dans la subcat algo.
Si pour toi le rang d'un arbre est sa hauteur, alors voici l'algo récursif :

Code :
  1. rang(noeud):
  2.    si noeud = nul alors retourne 0
  3.    sinon retourne 1 + max(rang(noeud.filsgauche), rang(noeud.filsdroit))


Reply

Marsh Posté le 25-12-2004 à 15:55:29    

nan justement ce n'est pas sa hauteur c'est ce qui est décris dans l'image !

Reply

Marsh Posté le 25-12-2004 à 16:04:24    

ok ok, je pensais que ton image n'était que des exemples d'arbres pour lesquels fallait trouver son rang.
 
Vu comme ça ça me parait rigolo comme problème...

Reply

Marsh Posté le 25-12-2004 à 17:55:40    

Rigolo comme tu dis... ca la été les 3 premiers jours, la ca le devien nettement moins :p

Reply

Marsh Posté le 26-12-2004 à 00:04:49    

Je crois avoir compris un truc...
Tout d'abord, il faut que ton arbre binaire, pour qu'il soit "légal" vérifie la propriété énoncée : pour n feuilles, on doit avoir n-1 noeuds internes.
Combien il y a-t-il d'arbres binaires à 1 feuilles vérifiant la propriété précédemment citée ? 1 seul arbre réduit à un seul noeud.
2 feuilles ? 1 seul arbre également.
3 feuilles ? 2 arbres.
4 feuilles ? 5 arbres.
etc.
Ca peut peut être te donner d'autres idées...

Reply

Marsh Posté le 26-12-2004 à 00:21:29    

Autre propriété : Les arbres semblent être ordonnés de la manière suivante : On choisit les plus "gauchers" en premier.
Par exemple pour les arbres à 4 feuilles (rang 5 à 9) on voit que l'arbre de rang 5 est le plus gaucher (comme l'arbre de rang 3 pour les arbres à 3 feuilles).
 
Ensuite il faut déterminer comment on énumère les arbres.
Pour passer du rang 5 au rang 6 : L'arbre de rang 6 et le symétrique à droite du rang 5.
5 -> 7 : On déplace sur la 3ème feuille en partant de la gauche, les feuilles n°1 et n°2 de l'arbre de rang 5.
7 -> 8 : Le rang 8 est le symétrique à droite du rang 7.
7 -> 9 : On déplace sur la 4ème feuille en partant de la gauche, les feuilles n°2 et n°3 de l'arbre de rang 7. On remarque que son symétrique à droite donne le même arbre.

Reply

Marsh Posté le 26-12-2004 à 00:22:55    

Il ne te reste plus qu'à formaliser tout ça mais je pense que ton exercice est résolu :D

Reply

Marsh Posté le 26-12-2004 à 00:25:34    

euh merci tout ca c'est des constatation que j'avais pu faire a part peu être l'idée de la symétrie ca c pas con !!
si j'fais une fonction symétrie ca peu peu être aidé merci beaucoup (mais c loin d'être résolu :) )

Reply

Marsh Posté le 26-12-2004 à 00:27:25    

moi j'vois plus un truc tout con avec une fonction récursive qui fais des opération différente selon "que l'on part a droite ou a gauche" mais j'ai rien trouvé :'(

Reply

Marsh Posté le 26-12-2004 à 00:27:25   

Reply

Marsh Posté le 26-12-2004 à 00:59:01    

Il me semble qu'il serait intéressant d'exprimer le nombre d'arbres en fonction du nombre de feuille.
D'après les exemples, j'aurais tendance à conjecturer les relations suivantes :
si n impair, A(n) = 2(n-1) = 2n-2
si n pair, A(n) = 2(n-1)-1 = 2n-3
où n désigne le nombre de feuilles et A(n) le nombre d'arbre en fonction du nombre de feuilles.
Il faudrait les démontrer (par récurrence) pour être rigoureux à partir de n=2.
Evidemment faut poser A(1)=1.
A partir d'une formule de ce genre on peut déjà avoir un encadrement pour le rang d'un arbre dont on connait le nombre de feuilles.
A(1)+A(2)+...+A(n-1) < rang(arbre(n)) <= A(1)+A(2)+...+A(n-1)+A(n)
 
Connaître le rang d'un arbre à n feuilles, revient à connaitre son rang relatif dans l'ensemble des arbres qui ont également n feuilles.


Message édité par pains-aux-raisins le 26-12-2004 à 01:17:20
Reply

Marsh Posté le 26-12-2004 à 01:08:43    

Un algo naïf et certes pas très performant pour trouver le rang relatif consiterait à générer le premier arbre à n feuilles.
On déroule le mécanisme d'énumération posté précédemment en incrémentant le rang relatif et à chaque itération on le compare à l'arbre dont on veut connaître le rang.
Dès que ça "match" on connaît le rang relatif, et donc le rang global.
 
Si je résume une première version de l'algo :
1/ calculer le nombre de feuille de l'arbre binaire à traiter.
2/ calculer le rang de l'arbre le plus gaucher ayant le même nombre de feuilles que l'arbre à traiter.
3/ calculer le rang relatif de l'arbre à traiter.


Message édité par pains-aux-raisins le 26-12-2004 à 01:09:39
Reply

Marsh Posté le 26-12-2004 à 11:08:15    

ok merci alors :
1/ pour calculer A(n) la formule est donné dans mon énoncé c plus simple que ca pas de question de parité :  
A(n) = (n parmis 2n)/(n+1)
j'avais deja pensé a encadré le rang de l'arbre de cette facon, maintenant je n'ai pas bien saisie comment tu arrive au "rang global" car comparé puis démaré le "processus", ok c facile pour le plus gauché son symétrique, mais comment tu fais pour lui dire : "le plus gaucher moins la dernier feuille sur a droite" enfin j'ai même du mal a me visualisé le rang des arbres a 5 feuille, j'v les dessiner j'revien

Reply

Marsh Posté le 26-12-2004 à 11:26:25    

8! / 4! * 4! = 5x6x7x8 / 2x3x4 = 5x7x8 / 4 = 5x7x2 = 70
70 / 4 +1 = 14  la formule de l'énoncé marche pas pour 4 feuille merde ! c pas possible ils ont du se gourré dans l'énoncé on est plus sur de rien la c la merde :/
 
bref de tte facon imagine pour un n assez grand le processus de comparation j'sais pas trop comment le codé ca devien vraiment un truc énorme ! j'v réflechir encor merci

Reply

Marsh Posté le 26-12-2004 à 11:36:54    

Voici les 14 arbres à 5 feuilles :


   /\    /\
  /\      /\
 /\        /\
/\          /\
 
10       11
 
  /\     /\
 /\       /\
/\         /\
 /\       /\
 
12       13
 
  /\     /\
 /\       /\
/\/\     /\/\
 
14       15
 
  /\      /\
 /\/\    /\/\
/\          /\
 
16       17
 
  / \      / \
 /\ /\    /\ /\
  /\        /\
 
17       18
 
  /\     /\
 /\       /\
  /\     /\
 /\       /\
 
19       20
 
  /\      /\
 /\        /\
  /\      /\
   /\    /\
 
21       22


 
Quand dans l'énoncé ils écrivent (n parmis 2n), c'est bien de C(2n, n) dont il s'agit ? Car dans ce cas on aurait pour le nombre d'arbres "légaux" à 4 feuilles : A(4)=C(8,4)/5=14
ou A(3)=5
Ca ne semble pas correspondre à ce qu'il y a sur le dessin où il semble il y avoir A(3)=2 et A(4)=5...


Message édité par pains-aux-raisins le 26-12-2004 à 12:24:46
Reply

Marsh Posté le 26-12-2004 à 11:48:50    

tu as oublier :
 
 / \
/\ /\
 /\
 
et  
 / \
/\ /\
  /\
 
ca fais 10 arbre a 5 feuille et oui la formule de l'énoncé est bien fausse (ca nous arrange pas)

Reply

Marsh Posté le 26-12-2004 à 12:12:19    

bien vu. j'ai corrigé le post précédent.
 
Sinon, je pense avoir un squelette d'algo pour le rang. Le voici :
 


rang(arbre):
   choix de arbre parmi
      cas arbre = arbre de rang 1 alors retourne 1
      cas arbre = arbre de rang 2 alors retourne 2
      sinon
         si hauteur à droite > hauteur à gauche alors
            retourne 1 + rang(symétrique à gauche(arbre))
         sinon
            parcours préfixe(arbre)  -- on associe à chaque noeud sa hauteur par rapport à la racine,
                                     -- ainsi que le numéro d'ordre de la visite préfixe.
            si arbre=arbre de rang 2 alors retourne 1
            sinon
               parmi les feuilles de hauteur maximale,
                  suppression des deux feuilles de numéro de visite préfixe le plus élevé.
               retourne Z(rang(arbre ainsi modifié))
            fin si
         fin si
   fin choix parmi
fin rang


 
La fonction Z reste encore à déterminer mais je pense que le principal est là.
Au début j'avais Z = 2*(nb feuilles à gauche des deux feuilles supprimées+1) + rang(arbre ainsi modifié)
mais avec les arbres à 5 feuilles ça ne marche pas.
Je pense effectivement que la fonction Z est une fonction combinatoire.

Reply

Marsh Posté le 26-12-2004 à 12:29:37    

Yes :D
Je viens de trouver les 14 arbres à 5 feuilles ! (cf un des posts au dessus)
 
La formule est correcte mais faut la lire comme suit :
Il y a C(2n, n)/n+1 arbre à n noeuds internes.
Y a plus qu'à bosser sur la fonction Z est le but est proche :)

Reply

Marsh Posté le 26-12-2004 à 14:33:34    

wahou merci beaucoup ! j'v essayé de bien comprendre ton algo et apres j'réfléchis pour la fct z j'te dis ou j'en suis merci :)

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed