Discussion :

[tipi_11]

Bonjour

Le critere d’ ́equilibre est la taille des sous-arbres : un arbre est equilibre si, pour tout noeud de l’arbre, la taille de son fils gauche est egale a la taille de son fils droit a` un noeud pr`es (la taille d’un arbre est son nombre de noeuds, feuilles comprises).

Ecrire en C la fonction ConstruitArbreEquilibre(int T[], int g, int d) qui construit et renvoie un arbre binaire de recherche equilibre contenant les valeurs T[g], T[g+1],..., T[d]. On suppose que les valeurs dans le tableau T sont definies pour les indices compris entre g et d, et sont ordonnees dans l’ordre croissant.

Bref j'ai pensé a faire une dichotomie sur le tableau a chaque fois ajouté l'élement médian, mais j'arrive pas à l'implémenter avec ce protoype.
Voici mon code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
typedef struct noeud* ARBRE;
 
typedef struct noeud
{
    int val;
    struct noeud* fg;
    struct noeud* fd;
} NOEUD;
 
ARBRE cree_Noeud(int val, ARBRE fg, ARBRE fd)
{
    ARBRE arbre = malloc(sizeof(struct noeud));
    arbre->val = val;
    arbre->fg = fg;
    arbre->fd = fd;
    return arbre;
}
 
ARBRE inserer(int val,ARBRE a)
{
    if(a == NULL)
            return cree_Noeud(val,NULL,NULL);
    if(val < a->val)
            a->fg=inserer(val,a->fg);
    else if(val > a->val) 
    			a->fd = inserer(val,a->fd);
    return a;
}
ConstruitArbreEquilibre(int T[], int g, int d)
{
 
}

J'ai vraiment du mal :/ si vous pouvez m'aider.Bonne année =)

[emixam16]

Ce forum est la pour aider le gens quand ils ont une difficulté. Mais pour qu'on t'aide, il faut que tu montre que tu as au moins essayé, que tu as des pistes des idées.

La tu balance brut une consigne, et voici l'étendue de ton travail de recherche :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
ConstruitArbreEquilibre(int T[], int g, int d)
{
 
}

Voici quand même un lien qui pourra t'aider.

La prochaine fois reviens avec du code.

[tipi_11]

Merci de votre réponse, ma méthode aurait été d'implémenter tous les médians en premier de chaque intervalles. Mais c'est assez dure je pensais à une solution astucieuse récursive que je n'arrive pas à voir avec ce prototype.

[emixam16]

Si la solution n'est pas évidente à tes yeux (et ce sera souvent le cas) prends une feuille, un crayon, et esssaye de poser le problème en français, par étape.

Dans ton algo tu dois insérer les éléments 1 par 1.

Pour chaque insertion tu as deux possibilités.

• Soit une insertion classique ne déséquilibre pas l'arbre donc tu peux insérer le nœud directement.
• Soit une insertion classique déséquilibrerait l'arbre donc tu dois rééquilibrer l'arbre (cf lien plus haut) avant toute insertion.

Il te reste deux problèmes a résoudre. Quand est-ce qu'un arbre est équilibré? Comment rééquilibrer un arbre déséquilibré.

Essaye de poster du code.

[Médinoc]

En fait, tu as deux solutions:

1. Implémenter un véritable arbre auto-équilibré, comme par exemple un arbre AVL. Auquel cas, tu peux simplement y ajouter les éléments dans l'ordre, et l'arbre fera le reste.
2. Ton idée originelle, un arbre qui ne s'équilibre pas mais où l'on insère les éléments triés récursivement de manière à le construire équilibré.

La seconde méthode étant la plus simple (même si la première est la plus pérenne).

Ta fonction, qui prend en paramètre un tableau trié et deux bornes (que je suppose inclusives), doit donc:

• Si le tableau fait juste zéro cases (donc, si borne inférieure est supérieure à borne supérieure), ne rien faire.
• Si le tableau fait juste une case (donc, si les bornes sont égales), juste l'ajouter à l'arbre.
• Sinon:
• Calculer l'index au milieu des deux bornes (en gros, la moyenne des bornes).
• Ajouter à l'arbre la valeur se trouvant à cet index.
• Rappeler récursivement la fonction sur [borne inférieure, milieu[ (donc, [borne inférieure, milieu-1])
• Rappeler récursivement la fonction sur ]milieu, borne supérieure] (donc, [milieu+1, borne supérieure])

Le prototype de la fonction récursive doit donc être:

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
void ajouterValeursTriees(struct arbre *pArbre, int const *tabTrie, int g, int d)
{ }

[tipi_11]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
ARBRE ConstruitArbreEquilibre(int t[], int g, int d)
{
     if (g>d)
         return(NULL)
     else {
         return(creeNoeud(t[(d-g)/2], ConstruitArbreEquilibre(t, g, 
(d-g)/2-1), ConstruitArbreEquilibre(t, (d-g)/2+1, d)));
     }
}

[Médinoc]

Ce n'est pas (d-g)/2 qu'il te faut, mais la moyenne des deux (donc, plutôt (d+g)/2 si d et g sont suffisamment petits; sinon il faut un truc du genre g + (d-g)/2)