Discussion :

[samche]

Bonjour,

J'ai lu et appliqué (en partie et sous php/mysql via une classe qui gère ma table) l'excellent article à l'adresse suivante:
http://sql.developpez.com/arborescence/

Je me heurte à deux soucis:
- le tri par ordre alphabétique
- le déplacement d'un sous-arbre sous un item

En reprenant un extrait de l'exemple de l'article ci-dessus, j'aurais souhaité obtenir ceci :
- transport
++- marin
++++- paquebot
++++- planche à voile
++++- voilier
++- terrestre
++++- camion
++++- moto
++++- velo
++++- voiture

L'affichage donné dans l'article s'appuie sur un tri sur la borne de gauche par contre je ne trouve pas le moyen de trier mes libellés. J'utilise un champs "rang" pour indiquer la profondeur de l'item dans l'arborescence (ici transport vaut 1, marin et terrestre valent 2, le reste vaut 3, ...).

Mon deuxieme probleme consiste à déplacer un sous-arbre sous un autre item. J'ai eu beau griffoner plusieurs simulations, je bloque sur la méthode pour mettre par exemple terrestre (et tous ses enfants) en-dessous marin.

Si quelqu'un s'est déjà penché sur ces algos, je lui serai reconnaissant qu'il m'en fasse profiter

Merci

[Nemerle]

Bonjour,

j'ai fait des trucs comme ça il y a 3 ans! Quel est ton problème pour couper/insérer un sous-arbre dans ton arbre??? C'est bien ce que tu veux faire?

Soit B le sous-arbre de racine le noeud b que tu veux détacher de A pour le placer sous le noeud c, "à droite".

0. Note bg(b),bd(b),bg(c) et bd(c) les valeurs initiales des bords G&D de b et c.
1. Il faut calculer la "longueur" L de B, soit bd(b)-bg(b)+1, et "dupliquer" B dans une table temporaire, avec ses bords D&G.
2. Tu "tues" B dans A, et pour tout noeud x de A tel que bg(x)>bd(b), tu retranches L de ses bords G&D
Rq: si bd(c) était inférieur à bg(b), la valeur bg et bd de c n'a pas changé après le point 2. Sinon, c a maintenant pour bord gauche bg(c)-L.

3.Note bg'(c) et bd'(c) les nouvelles valeurs de bords G&D pour c après le point 2.
4. Ensuite pour tous les x de A tel que bg(x)>bd'(c), tu ajoutes L à ses bords G&D.
5. Enfin tu "recopies" B sous c, en sachant que le bord gauche de la racine de B aura pour valeur bd'(c) dans A. Et pour finir tu ajoutes L à bd'(c).


Bon, j'ai écris un peu rapidement, mais l'idée est là!

Un exemple:

[samche]

En lisant ta réponse, il m'est venu une idée qu'il faudra que je teste... le principe est le meme que tu exposes mais avec la meme table qui contiendrait 2 graphes (dont un temporaire), ce qui éviterait trop de requetes.....

Je me doutai qu'il s'agirait d'un couper-coller mais je me bornai à essayer de trouver une solution plus "élégante" qui consisterait à juste modifier les bornes sans avoir à supprimer/insérer le sous-arbre, c'est mon coté reveur

Je me heurte toujours au probleme du tri. Je peux bien sur tester chacune des zones à trier et les trier séparément mais ce sera très vite long à executer dès lors qu'il y aura trop d'éléments. On perd aussi l'avatange de la représentation intervallaire ce qui est dommage.

C'est néanmoins la solution que je vais choisir en attendant que la table gonfle et qu'elle ne me pose pas de problème.... et ça c'est mon coté optimiste

Merci Nemerle pour cette solution

[Nemerle]

quand t'auras implémenté, tes temps de traitements m'intéressent!

On a passé + de 2 mois à tuner le code, car on gérait à l'époque des arbres à plusieurs centaines de milliers de noeuds !!

PS: je ne comprends pas ton autre problème, explique ...

[samche]

wow!! plusieurs milliers de noeuds!!!! je ne pense pas en arriver jusque là en tout cas

Mon deuxieme probleme c'est pour le tri par ordre alphabétique des éléments. Imagines le meme arbre que présenter dans le tutos mais où chacun des éléments d'un sous-arbre est trié par ordre alphabétique.

La requete pour sortir l'arbre tel qu'il est affiché c'ets ORDER BY la borne de gauche... logique... Le soucis, c'est que ça ne tient pas compte du contenu et ce serait plus classe (et plus simple pour l'utilisateur surtout) si les données apparaissaient par ordre alphabétique.

A part faire le tri sur le contenu de chacun des noeuds, je vois pas

[ludo00002]

Voici un exemple de code en SQL Firebird que j'ai conçu pour trier un arbre en représentation intervallaire.
J'ai été obligé d'utiliser un algorithme récursif.(J'ai essayé sans, mais en vain...)
Le principe est simple.
J'ai une nomenclature qui fait référence à un article. Je fais donc un tri par référence article du sous-arbre donné. Ensuite je recalcule les bornes BG et BD du nouveau sous-arbre.

COMMIT WORK;
SET AUTODDL OFF;
SET TERM ^ ;

/* Stored procedures */

CREATE PROCEDURE "SP_TREE_SORT_VUE_ANM"
(
"BG_SUIV" INTEGER,
"BG_P" INTEGER,
"BD_P" INTEGER,
"NIVEAU_P" INTEGER,
"RECURS" SMALLINT
)
RETURNS
(
"ID_S" INTEGER,
"BG_S" INTEGER,
"BD_S" INTEGER,
"NIVEAU_S" INTEGER,
"REF_ID_S" INTEGER,
"QTE_S" DOUBLE PRECISION,
"REF_ART_S" VARCHAR(32),
"ANM_DATE_VALIDITE" TIMESTAMP
)
AS
BEGIN EXIT; END ^


ALTER PROCEDURE "SP_TREE_SORT_VUE_ANM"
(
"BG_SUIV" INTEGER,
"BG_P" INTEGER,
"BD_P" INTEGER,
"NIVEAU_P" INTEGER,
"RECURS" SMALLINT
)
RETURNS
(
"ID_S" INTEGER,
"BG_S" INTEGER,
"BD_S" INTEGER,
"NIVEAU_S" INTEGER,
"REF_ID_S" INTEGER,
"QTE_S" DOUBLE PRECISION,
"REF_ART_S" VARCHAR(32),
"ANM_DATE_VALIDITE" TIMESTAMP
)
AS
--declare variable BG_Suiv integer;
declare variable BG integer;
declare variable BD integer;
declare variable Niveau integer;
-- declare variable REF_ART varchar(32);
-- declare variable BD_P integer;
-- declare variable BG_P integer;
-- declare variable Niveau_P integer;
declare variable ID integer;
declare BD_Suiv integer;
declare Ecart integer;
declare Deplacement integer;
declare REF_ID integer;
declare Qte double precision;
declare Ref varchar(32);
begin
-- BG_Suiv=BG_P;
for select ANM_ID,ANM_BG,ANM_BD,REF_ART,ANM_QTE,ANM_NIVEAU,ANM_REF_ID,ANM_DATE_VALIDITE
from Art_Nomenclature inner join Article on Article_ID=ANM_REF_ID
where ANM_BD<:BD_P and ANM_BG>:BG_P and ANM_Niveau=:Niveau_P+1
order by REF_ART
into :ID,:BG,:BD,:REF,:QTE,:NIVEAU,:REF_ID,:ANM_DATE_VALIDITE
do
begin
Ecart=BD-BG;
BG_Suiv=BG_Suiv+1;
Deplacement=BG-BG_Suiv;
REF_ID_S= REF_ID;
NIVEAU_S=NIVEAU;
QTE_S=QTE;
REF_ART_S=REF;
BG_S=BG_SUIV;
BD_Suiv=BG_Suiv+Ecart;
BD_S=BD_SUIV;
ID_S=ID;
suspend;
if (Ecart>1) then
begin
if (RECURS=1) then
for select ID_S,BG_S,BD_S,Niveau_S,REF_ID_S,QTE_S,REF_ART_S,:ANM_DATE_VALIDITE
from SP_TREE_SORT_VUE_ANM(:BG_SUIV,:BG,:BD,:NIVEAU_S,:RECURS)
into :ID_S,:BG_S,:BD_S,:Niveau_S,:REF_ID_S,:QTE_S,:REF_ART_S,:ANM_DATE_VALIDITE
do
begin
suspend;
end
end --end Ecart>1
BG_Suiv=BD_Suiv;
end --end for
end
^

SET TERM ; ^
COMMIT WORK;
SET AUTODDL ON;

[Nemerle]

Merci ludo, je vais regarder tout ça avec intérêt!

Je pense toutefois que le récursif "doit" disparaitre si tu travailles un jour sur de grosse volumétrie (un spécialiste pour me contredire?)

nous, à l'époque, se devant d'implémenter le tri et même l'insertion d'arbres dans un arbre, on a fait zéro récursion...

[HanLee]

Merci ludo, je vais regarder tout ça avec intérêt!

Je pense toutefois que le récursif "doit" disparaitre si tu travailles un jour sur de grosse volumétrie (un spécialiste pour me contredire?)

nous, à l'époque, se devant d'implémenter le tri et même l'insertion d'arbres dans un arbre, on a fait zéro récursion...

Si la fonction récursive ne peut pas être mise sous forme terminale, alors oui il faut la faire disparaître pour de grosses volumétries.

[ZZelle]

Je pense toutefois que le récursif "doit" disparaitre si tu travailles un jour sur de grosse volumétrie (un spécialiste pour me contredire?)

Ca semble surtout bizarre d'utiliser une fonction récursive dans un arbre représenté sous forme intervallaire alors que c'est justement une structure qui est conçu pour 'casser' la lourdeur de la représentation récursive des arbres.

Mon deuxieme probleme c'est pour le tri par ordre alphabétique des éléments. Imagines le meme arbre que présenter dans le tutos mais où chacun des éléments d'un sous-arbre est trié par ordre alphabétique.

La solution la plus simple si ton arbre A n'est pas trop gros est peut-être tt simplement de concevoir des fonctions/requêtes d'insertion dans un arbre intervallaire déjà trié. Puis d'insérer la totalité des éléments de ton arbre A dans un arbre At initialement vide qui sera par construction trié (grâce à la fonction précédente d'insertion !).

[Nemerle]

Ca semble surtout bizarre d'utiliser une fonction récursive dans un arbre représenté sous forme intervallaire alors que c'est justement une structure qui est conçu pour 'casser' la lourdeur de la représentation récursive des arbres.

+1

Mon deuxieme probleme c'est pour le tri par ordre alphabétique des éléments. Imagines le meme arbre que présenter dans le tutos mais où chacun des éléments d'un sous-arbre est trié par ordre alphabétique.

A mon avis, le plus simple, c'est d'ajouter 2 champs en plus des bords gauche et droit: profondeur, et rang.

Profondeur: c'est évident!
rang: pour tous les sous-noeuds d'un noeud donné, le rang te donne sa position lexicographique par rapport aux autres sous-noeuds.

[lunarnet76]

à tous je sais que j'arrive après la bataille mais je viens de passer plusieurs heures à chercher comment faire pour déplacer un sous arbre dans un arbre en représentation intervallaire et j'ai enfin réussi alors je vous file mon algo, je l'ai tester sur 5 arbres différents et ca marche, j'espère donc que çà marche en permanence ...
(j'ai tester mon algo en PHP / MySQL donc vous étonner pas des références a une bdd ^^)
Je me suis largement inspiré de la réponse de Nemerle :

1- calculer la longueur L du sous-arbre que l'on déplace
2- déplacer le sous arbre dans une table temporaire ( enfin dans une base de donnée, sinon faut le garder en mémoire quoi)
3- détruire le sous arbre (purement et simplement un DELETE)
4- récupérer les informations du père (le nœud auquel on va ajouter le sous arbre)
5- on renumérote l'arbre:

• enlever L a toutes les bornes supérieurs des éléments ayant
  borne supérieur du sous arbre < borne supérieur de l'élément < borne supérieur du pére
• enlever L a toutes les bornes inférieurs des éléments ayant
  borne supérieur du sous arbre < borne inférieur de l'élément < borne inférieur du pére

6- on renumérote le sous arbre (qui est toujours dans la table temporaire) :

• calcul = borne supérieur du pére - borne inférieur du sous arbre + L
• on ajoute aux bornes supérieurs et inférieurs du sous arbre ce calcul

7- on réimporte le sous arbre dans l'arbre
8- on vide la table temporaire

et voila

bon pour ceux qui font du PHP / MySQL voila l'algo

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
33
34
35
36
37
38
 
<?php
// le sous arbre
$sousArbre=array('sup'=>5,'inf'=>10);
 
// calcul de la longueur du sous arbre
$l=$sousArbre['sup']-$sousArbre['inf']+1;
 
// On déplace le sous arbre dans une table temporaire, et on le supprime de l'arbre
mysql_query('INSERT INTO table_arbre_temp SELECT * FROM table_arbre WHERE inf>='.$sousArbre['inf'].' AND sup<='.$sousArbre['sup']);
mysql_query('DELETE FROM table_arbre WHERE inf>='.$sousArbre['inf'].' AND sup<='.$sousArbre['sup']);
 
// Le pére a qui on va tout ajouter
$requete=mysql_query('SELECT * FROM table_arbre WHERE id='.$idpere);
$pere=mysql_fetch_assoc($requete);
 
// Renumérotation de l'arbre
mysql_query('
	UPDATE table_arbre SET    
		sup=sup - '.$l.'
	WHERE  sup > '.$sousArbre['sup'].' AND sup<'.$pere['sup']
);
mysql_query('
	UPDATE table_arbre SET    
		inf=inf - '.$l.'
	WHERE  inf > '.$sousArbre['sup'].' AND inf<'.$pere['sup']
);
 
// On calcul la différence entre la pseudo borne sup du pére et la borne inf du sous arbre => renumérotation du sous arbre
$calcul=$pere['sup']-$sousArbre['inf']-$l;
mysql_query('UPDATE table_arbre_temp SET inf=inf+'.$calcul.',sup=sup+'.$calcul);
 
// On rajoute le sous arbre a l'arbre
mysql_query('INSERT INTO table_arbre SELECT * FROM table_arbre_temp');
 
// On vide la table temporaire
mysql_query('TRUNCATE TABLE table_arbre_temp');
?>

[Aurélien LEQUOY]

je déterre ce topic mais il existe un solution en 3 updates