en fait j'ai juste du mal a trouver et démontrer la complecité de l'algo d'insertion en fonction du nombre d'élément .

A vue de nez je dirais O(log2(n)) c à peu pres le cout de parcour de l'arbre

ouais je pense aussi, mais ma difficulte est de le prouver.
sinon oui a vu de nez, c'est ça c'est sur .

tu appel quoi "arbre binaire ordonné".
 
un arbre de recherche, un tas, un B?-tree, un rb-tree.
 
c'est O(log(N)) sans doute mais precise ta structure de données

arbre binaire ordonné de
recherche (en abrégé ABOR) pour gérer les opérations d?insertion d?une liste L triée des éléments d?un ensemble
dynamique E totalement ordonné par une relation d?ordre notée <
. Un ABOR représentant une liste L est un arbre
binaire de recherche A sur E dont chaque sommet(associé à un élément e de E ) est un enregistrement possédant les
champs suivants :
? Le champ objet contenant e.
? Les champs fg et fd contenant un pointeur (éventuellement égal à null) respectivement sur les fils gauche et droit de s dans A. Le fils gauche contient les éléments plus petits que e, le fils droit contient les éléments supérieurs ou égaux à e.
? Les champs prec et suiv contenant un pointeur (éventuelement égal à null) sur les sommets de A associés aux éléments de E respectivement prédécesseur et successeur (par rapport à < ) de e dans E.
A lui-même est donc représenté par un pointeur sur le sommet racine de l?arbre. On suppose de plus que, si A n?est pas vide, la fonction Dernier(A) (respectivement Premier(A)) renvoie un pointeur sur l?enregistrement contenant le plus grand (respectivement le plus petit) élément de E.
 
bon c'est une description "informatique" plus pratique que theorique.
 
et si ca vous dit voila la procédure.
j'ai mon idée dessus, mais bon je suis pas chaud pour la mettre sur papier encore, enfin j'ai cherché des infos sur le net mais les arbres binaire ordonné de recherche ils en parlent pas tant que ça.
la complexité je me doute du résultat surtout vu que c'est un arbre mais je n'arrive pas à l'exprimer en fonction du nombre d'élément (faut dire que j'y ai pas encore vraiment réfléchis a fond, je révise en même temps que je fais ça et c'est pas la meilleure méthode, alors sic'est con comme la lune me flagélez pas SVP .
 

 
ça m parait pas complexe mais je trouve pas l'idée de départ.

en révisant d'autres algo, je me dis qu'il suffit d'exprimer la hauteur en fonction du nombre d'élément, et la hauteur d'un tel arbre n'est pas aléatoire, enfin elle est facilement exprimable en fonction du nombre d'élément je pense.
remarque non je melange avec autre chose la.
la complexite serait plutot egal dans le pire cas au nombre d element.

un simple dessin m'aurait suffit...
 
la complexité des opérations sur un ABOR est linéaire selon la Hauteur soit O(H)
 
apres, ca depend beaucoup de l'equilibrage de ton arbre. dans le pire des cas ou c'est un peigne, le cas est "assimilable" a une liste, les comparaisons en plus.

ouaip ca depend de l equilibrage, dans le pire cas ca va dependre du nombre d element, et le meilleur des cas c'est la racine non ?
meilleur cas complexité en O(1)
et dans le pire complexité en O(n)  n:nombre d'élément de E.
 
mais comment le justifier, en espérant que ce soit juste .
 
avec bien sur nombre d'appel:
inserer(element,arbre vide)) := 1 si larbre est vide
inserer(element,arbre de n elements) := inserer(element, arbre n-1 elements)+1 dans le pire cas.
 
non ?

 
le nombre d'éléments n'est pas mis en cause

si un peu.
on me demande en foncion du nombre d'element.
 
et la hauteur max d'un arbre binaire ordonne est egal au nombre d'élément dans le pire cas.
 
maintenant le justifier c'est autre chose mais je m'y attel (si ça s'écri comme ça).

je suis d'accord: tu peux seulement borner la hauteur

en fait c'est surtout le justifier qui me fait chier, car ca a l air tellement con a justifier que je me demande si c'est ca.
en prenant une suite U tel que U0 = nombre d'appel a la fonction d'insertion dans u narbre vide
U1 = nombre d'appel a la fonction d'insertion dans un arbre de 1 element
Un = nombre d'appel a la fonction d'insertion dans un arbre de n elements.
 
on a
U0 = 1
U1 = 2
Un = U(n-1) + 1
Un = n+1
 
donc suffirait de prouver par une recurrence a la con:
U(n+1)=Un+1 = (n+1)+1
 
ce qui est extremement con et facile a faire, c'est pour ca que je me demande l'interet de cette question, doit y avir un truc cache et je le trouve pas.

dans le pire des cas, c'est ca.
 
maintenant c'est sur que O(N) majore amplement O(log(N))

bein ouais, mais faut bien prendre en compte le pire cas, je peux pas faire autrement.
si j utilisais O(log n) ca serait forcément faux, non ?
si t en as le courage tu peux me rappller comment tu obtiens ton O(log n ) ?

ca vient de la structure d'arbre binaire tout simplement, apres pour le calcul    
 
distingue le cas moyen qui est quie O(log(N)) du pire des cas
 
et plus précisément, il me semble que ca doit etre O(log2(N)):
l'arbre binaire, c'est la structure parfaite pour des opérations dichotimiques => log2(N) est le nombre nécessaire de subdivison par 2 de l'espace de recherche qui dans cette structure arborescente est alors le nombre de noeuds traversés (dnas le cas moyen evidement)

bein il n'est pas précisé arbre parfait, c'est un arbre binaire de recherche c'est tout, il n'est pas forcément parfait.

j'avais bien compris

c'est la ou le ba blasse car d'habiotude je m'emmerdais pas , le resultat c'etait la hauteur de l'arbre .