Oracle

Calcul des valeurs des noeuds d'un arbre

Le 08/01/2016, par islamov2000, Membre expérimenté

J'ai développé une procédure qui calcule valeurs des nœuds d'un arbre donné.
La procédure base sur l'idée de récursivité, c’est vraiment un casse tête pour l’implémenter.
Donc, j'ai pensé à modéliser mon idée sous un SQL/Oracle en mettant la requête générique valable pour n'importe quel arbre .
L'arbre doit être introduit dans une table. cette dernière comporte 03 champs: pere, fils et valeur.

Les nœuds sont présentés comme suite dans la table:

Pere	Fils	Valeur
A	B	null

Les feuilles sont présentés comme suite dans la table:

Pere	Fils	Valeur
B	null	3

REQUETE:

Code :

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
39
with tab as 
( 
 select 'A' pere, 'B' fils, null valeur from dual union
 select 'A', 'C', null from dual union
select 'B', 'D', null from dual union
select 'B', 'E', null from dual union
select 'D', 'H', null from dual union
select 'E', 'I', null from dual union
select 'E', 'J', null from dual union
select 'J', null, 8 from dual union
select 'I', null, 15 from dual union
select 'H', null, 32 from dual union
select 'C', 'F', null from dual union
select 'F', null, 7 from dual union
select 'C', 'G', null from dual union
select 'G', 'K', null from dual union
select 'G', 'L', null from dual union
select 'L', 'M', null from dual union
select 'K', null, 2 from dual union
select 'M', null, 22 from dual 
)

select distinct D.* from 
(
      select noeud,sum(valeur)over(partition by noeud),chemin , arbre  from
      (
            select distinct regexp_substr(B.chemin,'[^(#)]+',1,level) noeud,valeur,B.chemin ,arbre from
            (
                    select t.valeur ,level niveau ,sys_connect_by_path(pere,'#') chemin,LPAD('-', 5*(level), '-')||pere  arbre
                    from tab t
                    start with pere ='A'--RACINE
                    connect by   prior fils=pere
            )B
            connect by level <=length(B.chemin)/2
      )C
      where noeud is not null 
)D
where noeud=substr(chemin,length(chemin))
order by chemin

Schéma du l'arbre:

Billet blog