Arbre Binaire Ordonné, Insertion d'un élément et complexié ?

Arbre Binaire Ordonné, Insertion d'un élément et complexié ? - Algo - Programmation

Marsh Posté le 27-11-2002 à 22:31:32    

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 :/.


---------------
"PAR LE POUVOIR DU CRÂNE ANCESTRAL, JE DETIENS LA FORCE TOUTE PUISSANTE".
Reply

Marsh Posté le 27-11-2002 à 22:31:32   

Reply

Marsh Posté le 27-11-2002 à 22:41:44    

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


Message édité par sombresonge le 27-11-2002 à 22:42:59
Reply

Marsh Posté le 27-11-2002 à 23:07:12    

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


---------------
"PAR LE POUVOIR DU CRÂNE ANCESTRAL, JE DETIENS LA FORCE TOUTE PUISSANTE".
Reply

Marsh Posté le 27-11-2002 à 23:18:26    

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


---------------
du bon usage de rand [C] / [C++]
Reply

Marsh Posté le 27-11-2002 à 23:43:19    

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 :D.
 

Code :
  1. la procédure:
  2. procedure Inserer(Element : in Type_Objet; Abor : in out Type_Abor) is
  3. -- Fonction d?allocation memoire (creation physique d?un nouvel element)
  4. function Creer_Element(Element: Type_Objet) return Type_Abor is
  5. Ptr : Type_Abor;
  6. begin
  7.   Ptr := new Sommet;
  8.   Ptr.Objet := Element;
  9.   return(Ptr);
  10. end Creer_Element;
  11. P_Ajoute : Type_Abor;
  12. begin
  13.   if (Abor = null) then
  14.    Abor := Creer_Element(Element);
  15.   elsif (Element < Abor.Objet) and (Abor.Fils_Gauche = null) then
  16.    P_Ajoute := Creer_Element(Element);
  17.    P_Ajoute.Successeur := Abor;
  18.    Abor.Fils_Gauche := P_Ajoute;
  19.    Abor.Predecesseur := P_Ajoute;
  20.   elsif (Element >= Abor.Objet) and (Abor.Fils_Droit = null) then
  21.    P_Ajoute := Creer_Element(Element);
  22.    P_Ajoute.Predecesseur := Abor;
  23.    Abor.Fils_Droit := P_Ajoute;
  24.    Abor.Successeur := P_Ajoute;
  25.   elsif (Element < Abor.Objet) then
  26.    Dernier(Abor.Fils_Gauche).Successeur := null;
  27.    Inserer(Element,Abor.Fils_Gauche);
  28.    Dernier(Abor.Fils_Gauche).Successeur := Abor;
  29.    Abor.Predecesseur := Dernier(Abor.Fils_Gauche);
  30.   else
  31.    Premier(Abor.Fils_Droit).Predecesseur := null;
  32.    Inserer(Element,Abor.Fils_Droit);


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


---------------
"PAR LE POUVOIR DU CRÂNE ANCESTRAL, JE DETIENS LA FORCE TOUTE PUISSANTE".
Reply

Marsh Posté le 27-11-2002 à 23:47:42    

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.


Message édité par Clarkent le 27-11-2002 à 23:52:32

---------------
"PAR LE POUVOIR DU CRÂNE ANCESTRAL, JE DETIENS LA FORCE TOUTE PUISSANTE".
Reply

Marsh Posté le 27-11-2002 à 23:54:25    

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.


---------------
du bon usage de rand [C] / [C++]
Reply

Marsh Posté le 28-11-2002 à 00:07:07    

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 ?


---------------
"PAR LE POUVOIR DU CRÂNE ANCESTRAL, JE DETIENS LA FORCE TOUTE PUISSANTE".
Reply

Marsh Posté le 28-11-2002 à 10:16:17    

Citation :

la complexité des opérations sur un ABOR est linéaire selon la Hauteur soit O(H)


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


---------------
du bon usage de rand [C] / [C++]
Reply

Marsh Posté le 28-11-2002 à 11:17:14    

Taz@PPC a écrit a écrit :

Citation :

la complexité des opérations sur un ABOR est linéaire selon la Hauteur soit O(H)


 
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 :D (si ça s'écri comme ça).


---------------
"PAR LE POUVOIR DU CRÂNE ANCESTRAL, JE DETIENS LA FORCE TOUTE PUISSANTE".
Reply

Marsh Posté le 28-11-2002 à 11:17:14   

Reply

Marsh Posté le 28-11-2002 à 11:35:39    

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


---------------
du bon usage de rand [C] / [C++]
Reply

Marsh Posté le 28-11-2002 à 11:44:25    

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.


---------------
"PAR LE POUVOIR DU CRÂNE ANCESTRAL, JE DETIENS LA FORCE TOUTE PUISSANTE".
Reply

Marsh Posté le 28-11-2002 à 13:30:13    

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


---------------
du bon usage de rand [C] / [C++]
Reply

Marsh Posté le 28-11-2002 à 14:09:18    

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 ) ?


---------------
"PAR LE POUVOIR DU CRÂNE ANCESTRAL, JE DETIENS LA FORCE TOUTE PUISSANTE".
Reply

Marsh Posté le 28-11-2002 à 16:51:45    

ca vient de la structure d'arbre binaire tout simplement, apres pour le calcul  :sarcastic:  
 
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)


Message édité par Taz@PPC le 28-11-2002 à 16:55:51

---------------
du bon usage de rand [C] / [C++]
Reply

Marsh Posté le 28-11-2002 à 22:42:13    

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.


---------------
"PAR LE POUVOIR DU CRÂNE ANCESTRAL, JE DETIENS LA FORCE TOUTE PUISSANTE".
Reply

Marsh Posté le 28-11-2002 à 22:51:52    

j'avais bien compris


---------------
du bon usage de rand [C] / [C++]
Reply

Marsh Posté le 28-11-2002 à 22:58:32    

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


---------------
"PAR LE POUVOIR DU CRÂNE ANCESTRAL, JE DETIENS LA FORCE TOUTE PUISSANTE".
Reply

Sujets relatifs:

Leave a Replay

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