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;