Discussion :

[sjrd]

Bonjour,

Le contexte

Dans le cadre d'un mini-projet de mon cours d'informatique (autant le dire tout de suite), j'ai développé un algorithme de "placement" d'arbre (pas forcément binaire). Le but étant de donner des positions aux noeuds de l'arbre, de façon à l'afficher de manière optimale (en minimisant l'espace requis en largeur).

L'algo fonctionne bien, et le projet tout autant. Mais pour "peaufiner" mon rapport, j'aimerais parvenir à déterminer la complexité de cet algorithme.

Ce que j'ai fait

Je suis bien parvenu à écrire mon équation de récurrence, ainsi qu'un certain nombre de relations importantes. J'ai également résolu les deux cas extrêmes : celui une racine à N-1 enfants qui eux-mêmes n'ont jamais d'enfant O(N) ; et celui où chaque noeud à 1 et 1 seul enfant, sauf celui tout en bas qui n'en a évidemment pas : O(N²).

La question

Comme tout ça est très dur à écrire dans un post de forum, j'ai attaché une page PDF qui sort de LaTeX, avec tout ce que j'ai su faire.

Par contre, je ne parviens pas à résoudre cette équation dans le cas général, et je n'ai aucune preuve que le cas 2 - celui en O(N²) - soit le pire cas

Si vous pouviez m'aider à me dépatouiller de ce léger problème, ce serait super chouette

d'avance

[acx01b]

salut

peux tu expliquer rapidement ce que fait ton algorithme (la fonction T ?)

[sjrd]

Oui bien sûr.

Comme je l'ai dit, le but final est de donner des positions aux noeuds de l'arbre. En tout cas des positions en abscisses et relatives, par rapport à la position du parent du noeud. Et ce pour afficher l'arbre de la façon la plus étroite possible.

Chaque noeud X a donc un attribut xRelPos, qui est cette position par rapport à son parent. Ainsi que deux listes de valeurs lefts et rights qui sont ceci : pour chaque étage à partir de X, lefts contient la position (relativement à celle de X) du noeud le plus à gauche (parmi le sous-arbre dont la racine est X). De même, rights contient la position, à chaque étage, du noeud le plus à droite. Ces deux listes ont une longueur égale à la profondeur du sous-arbre dont la racine est X.

Mon algo, sur le noeud X, fait ceci :

1. Appliquer l'algo à tous les enfants de X.
2. Donner des positions relatives à ses enfants, les plus proches les uns des autres, mais en ne superposant pas la liste rights d'un enfant à la liste lefts de l'enfant qui le suit.
3. Calculer les listes lefts et rights de X, en fonction des positions données aux enfants, et de leurs listes lefts et rights.

Le cas de base de la récursion, c'est que les listes lefts et rights des noeuds feuilles contiennent toutes l'unique élément 0.0.
A la fin, on dit que la position relative de la racine est 0.0.

Le (1), c'est le T(ni, pi). Le (2), c'est en O(mP). Et le (3) est en O(P), ce qui est donc "écrasé" par le O(mP).

Est-ce que c'est clair ? Ou je réécris tout ça en pseudo-code ?

[Nemerle]

disons oui, précise, car tantôt tu parles de position et tantôt tu parles de listes...

[sjrd]

Donc voici mon type de données principale :

Code :

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

1
2
3
4
5
6
7
8
Soit TNode un type record avec les champs :
  label: entier - Etiquette du noeud de l'arbre
  fils: array of TNode - liste des enfants du noeud
  posFromFirst: flottant - position par rapport au premier frère
  xRelPos: flottant - position en abscisse par rapport à son parent
  lefts: array of flottant - liste des positions les plus à gauche dans le sous-arbre
  rights: array of flottant - liste des pos les plus à droite dans le sous-arbre
FinSoit

Fonction de traitement sur un noeud en général, qui est fonction récursive :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
procedure PlaceRelTree(Node: TNode)
  Si Node est une feuille de l'arbre (il n'a pas d'enfant) Alors
    Node.lefts <- [0.0] // tableau à 1 élément dont celui-ci est 0.
    Node.rights <- [0.0]
  Sinon
    PourTout Enfant dans Node.fils Faire
      PlaceRelTree(Enfant)
    FinPourTout
    (Node.lefts, Node.rights) <- PlaceChildren(Node.fils)
  FinSi
FinProc

La fonction PlaceChildren est un peu complexe : elle va donner des valeurs correctes à posFromFirst et xRelPos pour chaque enfant.
Et je sais qu'elle est en O(m.P), sachant que m est le nombre de fils, et P la profondeur du sous-arbre dont la racine est Node.

[acx01b]

salut

pour minorer et majorer tu peux dire
NF = nombre de feuilles

alors on a

P(P+1)/2 < X < P(P+1)/2*NF

où X est le nombre "d'instructions" exécutées et P la profondeur de l'arbre

[sjrd]

Merci Donc globalement ce serait en Omega(P²) et en O(P²*NF). C'est déjà beaucoup plus précis que ma vague conjecture en O(N²)

Est-ce que tu pourrais expliquer un tout petit peu comment tu arrives à ce résultat, stp ?

[acx01b]

salut

on regarde les étages de l'arbre: Mi nombre de noeuds du ième étage

(la racine est au 0 ième étage, ses fils au premier, leurs fils au deuxième ...)

ensuite on groupe les appels à PlaceChildren par l'étage du noeud (sa profondeur dans l'arbre)
et parmis ces noeuds on regarde celui qui a un sous arbre le plus profond

ensuite on majore tout ça (profondeur des sous arbres en dessous des noeuds de l'étage i, et nombre de noeuds de l'étage i)

on a donc P - i profondeur max sous un noeud du ième étage

et voila on fait la somme de tous les étages pour ça qu'on a P + P-1 + P-2...
= P (P + 1)

le nombre de noeud par étage étant majoré entre autre par le nombre de feuille

[sjrd]

Super J'ai dû réfléchir un peu pour comprendre, mais j'y suis.

beaucoup pour ton aide