Bonjour,
 
Je souhaite realiser un programme utilisant les arbres balances sauf que je n'arrive pas a realiser l'algorithme d'insertion d'un element dans cet arbre. Un peu d'aide serait la bienvenue (ou des liens si vous avez).
Merci

C'est quoi que t'appelles un arbre balancé ?

C'est du franglais, je suppose, il veut parler d'arbres équililbrés (balanced trees en anglais).
 
cdr> Après, reste à savoir si tu parles d'arbres binaires ou de B-Trees. Mais dans tous les cas, tu dois pouvoir trouver ton bonheur sur Google.

On nou les a montrés comme ça, il ne s'agit pas d'arbres binaires équilibrés, c'est plus que ça. J'ai fait de nombreuses recherches sur google mais à par des exemples ou des descriptions sommaires j'ai rien alors que les algorithmes ne sont pas évident (je suis pas doué c'est vrai).
 
Sur cette page on peut voir une applet réalisant un arbre balancé mais je n'ai pas trouvé les sources.

Tu peux soit l'équilibrer à la création  
(choix d'un point médian à chaque noeud pour avoir autant d'élément à gauche qu'à droite)
soit ajouter les éléments dans n'importe quel ordre
et appliquer un algo style "swing left/swing right"
pour équilibrer branche par branche.
 
La deuxième solution s'impose si tu veux ajouter/retirer constamment des éléments dans ton tableau.
 
LeGreg

Normalement il est équilibré après chaque insertion. C'est d'ailleurs cet algo qui est compliqué et non l'insertion.
Là je me suis tourné vers un arbre binaire équilibré, l'équilibrage est plus facile car il n'y a qu'une seule clé par noeud et non pas plusieurs comme dans un arbre balancé (je me serais orienté vers un arbre balancé d'ordre 1 donc il y aurait eu 2 clés par noeud mais l'algo n'était vraiment pas évident et je n'ai pas le temps de le faire).

http://www.lri.fr/~filliatr/fsets/ tiens quelques implémentations en caml prouvées formellement (et débuggées ... hum).

jcomprend rien à ces trucs

Fait une recherche google sur « red-black trees » et « AVL trees ».

Les red-black trees et AVL trees sont des arbres binaires équilibrés, c'est différent de ce que je cherche. Mes arbres balancés possèdent plusieurs clés par noeud (ce qui réduit le nombre de noeud et regroupe les valeurs pour les lectures sur disque par exemple).

 
c étonnant ton exo, quand on parle d'arbres balancés en principe c pour les arbres binaires (arbre AVL). Pour des arbres n-aires, cela commence a devenir inutile du fait de la tres faible profondeur de l'arbre
t sur que c pas pour un arbre binaire ?

Justement la très faible profondeur est un avantage car ça permet de regrouper au même endroit les données, et cet avantage est immédiat sur disque puisque la lecture d'une page permet d'avoir plusieurs valeurs.
Enfin je vais pouvoir me débrouiller avec un arbre binaire équilibré, peut-être que je tenterai mieux plus tard.
Merci pour vos réponses

vous avez ça dans vos tirroir un algo pour rebalancer un arbre

<--- lisez ici !
 

http://brassens.upmf-grenoble.fr/I [...] resAVL.htm
merci à  
http://www.google.com/search?hl=en [...] gle+Search
pour son efficacité !
 
au passage, "to balance" veut dire "equilibrer" dans notre chère langue de Molière.