Arbres équilibrés

par **deugeur** » 31 Déc 2007, 17:00

bonjour à tous,
je suis en train de bosser sur un devoir d'une matière intitulée : mathémathiques pour l'informatique. Le devoir porte donc sur les abres équilibrés. Voila le premier endroit ou je bloque. :briques:

soit A un abre binaire non vide de hauteur h, Ag et Ad ses sous-arbres droit et gauche.
quelles sont les hauteurs possibles pour Ag et Ad? en deduire un schéma d'induction des arbres binaires construits par hauteur.

Pour moi la hauteur possible de Ag et Ad est compris entre -1 et h-1, mais je ne vois pas ce que peut etre un schema d'induction.......par hauteur.

merci, de m'aiguiller

par **deugeur** » 03 Jan 2008, 11:34

Re, ce sujet n'attire pas les foules :dodo: je comprend, néanmoin j'ai trouvé la solution donc merci à ceux qui ont essayé.

Pour les curieux un schema d'induction c'est une démonstration par reccurense étendu aux arbres( ou a autres stuctures), on suppose vrai un proposition pour un AG et pour Ad et on démontre quel et vrai aussi pour A. Et voila :)

par **deugeur** » 04 Jan 2008, 00:23

si il y a des gens encore motivé par le sujet, qu'ils se manifestent car moi je planche encore sur la suite de ce devoir. Aprés ca part sur les arbres équilibrés et leurs rapports avec la suite de fibonacci et tout et tout et tout trop de la balle qui déchire :++: . Voilou a+

par **deugeur** » 04 Jan 2008, 11:59

Un collegue a moi a aussi posté un message donc pour plus de simplicité veuillez vous reporter ci-aprés :
:go: http://www.maths-forum.com/showthread.php?t=53540

bye bye

Arbres équilibrés

arbres équilibrés

Qui est en ligne