Discussion :

[johnkhm]

Bonjour !

Voici mon petit projet :
Je dois trouver un algorithme permettant de trouver le plus grand élement d'un tableau situé entre deux indices, en utilisant les ARBRES.
Je fais alors un pré-traitement de mon tableau, pour obtenir un arbre.
Voici l'algo :
En gros, je repère l'élement le plus grand du tableau ( indice i ), ca devient le pere. Je sépare le tableau de [0-> i-1] et [i+1 -> tailleMax]. Ensuite je rappele la fonction pour ces deux tableaux...

Voici le pseudo 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
 
fonction( mot, noeud ){
    si |mot| == 1 :
       retour mot
    sinon :
       max = mot[0]
       indice = 0
       pour i : 1 -> |mot|
          si max < mot[i]
            max = mot[i]
            indice = i
            tableauNoeud[i] = noeud
       nouveau filsGauche de noeud
       filsGauche.profondeur = noeud.profondeur + 1
       filsGauche.texte = fonction(mot[0,i-1])
       nouveau filsDroit de noeud
       fildDroit.profondeur = noeud.profondeur + 1
       filsDroit.texte = fonction(mot[i+1,|mot|])

Une fois que cet arbre est crée, je dispose d'une fonction permettant de trouver l'ancetre commun le plus proche entre deux noeuds.

Le probleme, c'est que la création de l'arbre est en O(n!) !!!!!!

On m'a conseillé d'utiliser une pile FIFO , voici mes indications :
" a chaque fois que tu ajoute une position tu cree un noeud avec la valeur de la position et tu parcours la pile en faisant ce qu'il faut "


Sinon j'ai une autre idée, c"est de créer un tableau trié , qui garderai les positions initiales. Le meilleur algo de tri est en O(n2) ( enfin je crois )
mais je ne sais pas si c'est une meilleur solution que la pile

Est ce que qqun saurait comment s'y prendre pour adapter une pile a ma construction d'arbre ??

Merci beaucoup !

[Zavonen]

Le meilleur algo de tri est en O(n2) ( enfin je crois )

Quicksort est en nlog(n)

On m'a conseillé d'utiliser une pile FIFO

Une pile c'est une LIFO (Last In First Out)
Une structure FIFO (First In First Out) c'est une file (en anglais queue)

[souviron34]

précises un peu ce que tu entends par "plus grand"

[johnkhm]

En fait, on peux assimiler mon tableau a un tableau de chiffres. Quand je dis le plus grand, c'est le plus grand chiffre du tableau situé entre deux indices.

Pour quicksort en nlog(n), ca parrait interessant, je doute que la pile puisse faire mieux ... J'y réflechis

[souviron34]

tu peux faire une structure :

Code :

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

1
2
3
4
  int num ds tableau (i)
  int longeur ;
  struct *prec ;
  struct *suiv ;

tu fais une tableau de structures (ton arbre)

tu fais une boucle pour initialiser :

Code :

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

1
2
3
4
5
   for ( i = 0 ; i < ntableau ; i++ )
     num = i 
     longueur = strlen()
     prec = precedent
     suiv = suivant

tu fais un qsort :

fonction de tri -> classe en fonction de longueur

fait une boucle sur tableau de struct
ajuste suiv et prec

et là voilà :-)

3*N + O(N*logN)

[johnkhm]

3*N + O(N*logN)
Je pense pas que la pile puisse faire mieux ... Va pour cette solution !
Merci bcp !

[pseudocode]

Je dois trouver un algorithme permettant de trouver le plus grand élement d'un tableau situé entre deux indices, en utilisant les ARBRES.

Si c'est un algo "one shot" (qui ne sert qu'une seule fois), le plus simple c'est de faire un QuickSort borné entre les 2 indices. Et dans ce cas, je ne vois pas pourquoi utiliser des arbres.

Dans le cas contraire, cela signifie une fonction du genre:

Code :

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

maxElement( tableau[] , indicemin, indicemax )

Bien sur, le plus simple c'est de construire la liste des indices, triées dans l'ordre des valeurs du tableau. Ensuite il suffit de parcourir la liste des indices et de s'arreter des que l'indice est dans l'intervale [indicemin, indicemax]. Mais je ne vois toujours pas le rapport avec les arbres.

A moins de vouloir pré-calculer toutes les valeurs de la fonction pour tous les couples (indicemin, indicemax) ? Dans ce cas on peut limiter le nombre de valeur a pré-calculer en remarquant que:
- Si tableau[a]<tableau[a+1] alors maxElement(a,b) = maxElement(a+1,b)
et
- Si tableau[b]>tableau[b+1] alors maxElement(a,b+1) = maxElement(a,b)
Donc on doit donc pouvoir construire un arbre qui pour un couple (a,b) donné nous indique le plus "petit" couple (a_max,b_min) possedant le meme maxElement. Mais c'est quand meme louche cette histoire d'arbre

[johnkhm]

En fait, le sujet a été donné pour qu'on s'entraine sur les arbres. D'ou l'obligation de se servir des arbres... Ceci dit , l'astuce pour réduire le nombre de calculs a faire est pas mal

Merci

[Sivrît]

Je ne sais pas si c'est pertinent mais un tas me semble à l'ordre du jour. En arrangeant le tableau en tas on a un arbre binaire qui permet de trouver instantanément l'élément le plus grand. Et si l'on ajoute ou retire des éléments au tableau on a un complexité logarithmique pour maintenir la structure. Ca peut dépanner.