Recherche algo d'équilibrage d'arbre binaire. - Page 1

Tout est dans le titre, en C bien sur ( aboh avl quoi)

up quoi, c'est ultra urgent

C'est dans la plupart des bouquins d'algo.
Je ne connais pas super bien ces algos, donc je ne peux pas vraiment t'aider.

Apparemment, [google]c balanced tree[/google] me parle de http://libredblack.sourceforge.net/ ; ça doit plus ou moins répondre à ta question, non?

Voici un algo d'équilibrage fait à la va vite, je sais pas si ça fonctionne. Je parie que c'est pour un ABR??

Sommet *EquilibreSousArbre(Sommet *UnABR)
{
   Sommet *Tempo;
    if(!UnABR) return UnABR;
    if(!SousArbreGauche(UnABR) && !SousArbreDroit(UnABR)) return UnABR;
      if(!SousArbreDroit(UnABR))
         if(!SousArbreDroit(SousArbreGauche(UnABR)) && SousArbreGauche(SousArbreGauche(UnABR)))
         {
             Tempo=SousArbreGauche(UnABR);
             AccrocheGauche(UnABR,ArbreVide());
             AccrocheDroite(Tempo,UnABR);
             return Tempo;
          };
     if(!SousArbreGauche(UnABR))
       if(!SousArbreGauche(SousArbreDroit(UnABR)) && SousArbreDroit(SousArbreDroit(UnABR)))
       {
         Tempo=SousArbreDroit(UnABR);
         AccrocheDroite(UnABR,ArbreVide());
         AccrocheGauche(Tempo,UnABR);
         return Tempo;
        };
      AccrocheGauche(UnABR,EquilibreSousArbre(SousArbreGauche(UnABR)));
      AccrocheDroite(UnABR,EquilibreSousArbre(SousArbreDroit(UnABR)));
      return UnABR;
};
  

void Equilibre()
{
   int Prof=Profondeur(Racine);
   while(Prof)
   { 
      Racine=EquilibreSousArbre(Racine);
      Prof--;	
   }
};

int Profondeur(Sommet *UnABR)
{
    int valeur;
    if(!UnABR)return 0;
    valeur=1+Maximum(Profondeur(SousArbreGauche(UnABR)),Profondeur(SousArbreDroit(UnABR)));
    return valeur;
};
  
int Maximum(int Val1,int Val2)
{
   if(Val1>Val2)return Val1;
   return Val2;
};

Il faut juste savoir que SousArbreDroit ou SousArbreGauche correspond au fils d'un arbre genre UnABR->FilsGauche...

Pour finir AccrocheGauche ou AccrocheDroit correspondent tout simplement à UnABR1->FilsGauche=UnABR2; ou UnABR1 et UnABR2 sont les arguments de la fonction.

En passant quelqu'un pourrais m'expliquer comment insérer des chaîne de caractères dans un ABR pour rechercher un mot très rapidement car je ne sais pas comment faire.

Ah oui j'oublie ArbreVide correspond tout simplement à ceci en gros:

void AbreVide (void)
{
  Sommet *Tempo=NULL;
  return Tempo;
}

Ca peut être optimisé bien sûr.

geogeo :
En passant quelqu'un pourrais m'expliquer comment insérer des chaîne de caractères dans un ABR pour rechercher un mot très rapidement car je ne sais pas comment faire.

Tu insères comme dans un arbre de recherche non-balancé et puis tu équilibres. On ne peut pas faire mieux à ma connaissance.

Bah en fait j'avoue être encore plus nul que ça car je n'arrive pas à piger la structure qu'il me faut bref il faut utiliser des comparaisons pour construire l'arbre, or comparaison entre le code ascii d'un caractère de la chaîne?
Bref je ne sais que faire des ABR avec des chiffres rien de plus, malgré des recherches sur google rien sur les chaînes. Je trouve pas d'infos, donc si vous avez un lien ça serait sympa. (en français de préférence).

Si tes entrées sont des chaînes, il te faut des comparaisons de chaînes.

Bah en fait je sais pas si c'est possible et si c'est lourd mais faire un ABR avec seulement les caractères qui compose une chaîne de caractères et ainsi chaque noeud contiendera un caractère. Pour chercher une chaîne il faudra tester les branches de l'arbres jusqu'à arriver à une feuille qui me donne un numéro d'index.

Dans ce cas, ce n'est plus un arbre binaire, c'est un arbre d'ordre 256. Je t'en avais déjà parlé dans ton topic sur la compression.

Ah désolé mais j'ai pas compris comment ça marche.

Ben en fait je voulais savoir si qqun avait une routine tte faite: on rentre le pointeur de l'arbre déséqulibré, il nous ressort un arbre équilibré

Et bah y a tout regarde dans Equilibre.

geogeo :
Ah désolé mais j'ai pas compris comment ça marche.

1. Prends une feuille de papier et trace un arbre binaire de hauteur 1 (3 nœuds).
2. Maintenant, à tes 2 branches, tu en rajoutes 254 autres de la même manière (même point de départ, points d'arrivée différents).
3. Voilà un arbre d'ordre 256 de hauteur 1.
4. Si tu fais la même chose avec tes 256 nœuds du prochain niveau, tu peux passer à un arbre d'ordre 256 et de hauteur 2, 3 etc.
5. Compte tes nœuds. Si tu as bien fait ton travail, tu as 257 nœuds pour la hauteur 1, 65793 nœuds pour la hauteur 2, et pas assez de place sur ta feuille pour la hauteur 3.

lol ok j'ai tout compris.