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 !