2011-03-16 12 views
5

Digamos que tiene una estructura de árbol de la siguiente manera:algoritmo para seleccionar los nodos y sus padres en un árbol

 a   [Level 0] 
/| \ 
    b c d  [Level 1] 
/\ | 
e f g  [Level 2] 
    | /\ 
    h i j [Level 3] 

he representado esto en una base de datos de este modo:

node parent 
------------ 
a  null 
b  a 
c  a 
d  a 
[...] 
h  f 
i  g  

me gustaría les gusta escribir una función que, dado un nivel, devolverá todos los nodos en ese nivel y sus padres.

Por ejemplo:

f(0) => { a } 
f(1) => { a, b, c, d } 
f(2) => { a, b, c, d, e, f, g } 

¿Alguna idea?

+2

¿Está buscando hacer esto en SQL? –

+2

¿Ha considerado simplemente almacenar la profundidad en la base de datos también? – Amber

+0

Sí, debería haber aclarado. Estoy buscando una solución SQL. –

Respuesta

3

Aquí repito los niveles, agregando cada uno a la tabla con el nivel en el que está.

create table mytable (
    node varchar(80), 
    parent varchar(80), 
    constraint PK_mytable primary key nonclustered (node) 
) 

-- index for speed selecting on parent 
create index IDX_mytable_parent on mytable (parent, node) 

insert into mytable values ('a', null) 
insert into mytable values ('b', 'a') 
insert into mytable values ('c', 'a') 
insert into mytable values ('d', 'a') 
insert into mytable values ('e', 'b') 
insert into mytable values ('f', 'b') 
insert into mytable values ('g', 'd') 
insert into mytable values ('h', 'f') 
insert into mytable values ('i', 'g') 
insert into mytable values ('j', 'g') 

create function fn_level (@level int) returns @nodes table (Node varchar(80), TreeLevel int) 
as begin 
    declare @current int 
    set @current = 0 
    while @current <= @level begin 
     if (@current = 0) 
      insert @nodes (Node, TreeLevel) 
      select node, @current 
      from mytable 
      where parent is null 
     else 
      insert @nodes (Node, TreeLevel) 
      select mt.node, @current 
      from @nodes n 
       inner join mytable mt on mt.parent = n.Node 
      where n.TreeLevel = (@current - 1) 
     set @current = @current + 1 
    end 
    return 
end 

select * from fn_level(2) 
+0

Veo en los comentarios ahora que está usando MySQL, comencé esta respuesta de SQL Server antes de que se publicara. Avíseme si debería eliminarlo. –

0

SQL no siempre maneja estos problemas recursivos muy bien.

Algunas plataformas DBMS le permiten usar Common Table Expressions que son efectivamente consultas que se llaman a sí mismas, lo que le permite recurse a través de una estructura de datos. No hay soporte para esto en MySQL, por lo que le recomendaría que use múltiples consultas construidas y administradas por un script escrito en otro idioma.

1

La manera habitual de hacer esto, a menos que su sabor de SQL tiene una función no estándar especial para él, es la construcción de una tabla de ruta que tiene estas columnas:

  • parent_key
  • child_key
  • PATH_LENGTH

para llenar esta tabla, se utiliza un bucle recursivo o de procedimiento para encontrar toda la altura ents, abuelos, bisnietos, etc. para cada artículo en su lista de artículos. La recursión o bucle debe continuar hasta que dejes de encontrar rutas más largas que devuelven pares nuevos.

Al final, tendrá una lista de registros que le dirá cosas como (a, b, 1), (a, f, 2), (a, h, 3) etc. Luego, para obtener todo lo que está en el nivel x y superior, haces una selección clara en todos los hijos con una longitud de ruta < = x (unida a la raíz, a menos que hayas incluido un registro de (nulo, raíz, 0) cuando comenzaste tu recursión/looping.

sería bueno si SQL estaban mejor en el manejo dirigido gráficos (árboles), pero por desgracia hay que engañar con mesas adicionales como esto.

1

Una solución para MySQL es menos que ideal.

Suponiendo que la profundidad máxima del árbol es conocido:

SELECT 
    nvl(e.node, nvl(d.node, nvl(c.node, nvl(b.node, a.node)))) item 
, nvl2(e.node, 5, nvl2(d.node, 4, nvl2(c.node, 3, nvl2(b.node, 2, 1)))) depth 
FROM table t AS a 
LEFT JOIN table t AS b ON (a.node = b.parent) 
LEFT JOIN table t AS c ON (b.node = c.parent) 
LEFT JOIN table t AS d ON (c.node = d.parent) 
LEFT JOIN table t AS e ON (d.node = e.parent) 
WHERE a.parent IS NULL 

Esto le dará todos los nodos y de profundidad. Después de eso, es trivial seleccionar cada elemento que tenga una profundidad inferior a X.

Si no se conoce la profundidad del árbol, o si es significativamente grande, la solución es iterativa, como ha dicho otro afiche.

1

Copiando desvergonzadamente de Jason, hice una solución sin funciones que probé con postgresql (que tiene funciones, tal vez hubiera funcionado de la caja).

create table tree (
    node char(1), 
    parent char(1) 
); 

insert into tree values ('a', null); 
insert into tree values ('b', 'a'); 
insert into tree values ('c', 'a'); 
insert into tree values ('d', 'a'); 
insert into tree values ('e', 'b'); 
insert into tree values ('f', 'b'); 
insert into tree values ('g', 'd'); 
insert into tree values ('h', 'f'); 
insert into tree values ('i', 'g'); 
insert into tree values ('j', 'g'); 

ALTER TABLE tree ADD level int2; 
-- 
-- node parent level 
-- a - 1 
-- b a a.(level + 1) 
-- c a a.(level + 1) 
-- e b b.(level + 1) 
-- root is a: 
UPDATE tree SET level = 0 WHERE node = 'a'; 
-- every level else is parent + 1: 
UPDATE tree tout  -- outer 
    SET level = (
    SELECT ti.level + 1 
    FROM tree ti -- inner 
    WHERE tout.parent = ti.node 
    AND ti.level IS NOT NULL) 
    WHERE tout.level IS NULL; 

La declaración de actualización es sql pura, y debe repetirse para cada nivel, para completar la tabla.

kram=# select * from tree; 
node | parent | level 
------+--------+------- 
a |  |  1 
b | a  |  2 
c | a  |  2 
d | a  |  2 
e | b  |  3 
f | b  |  3 
g | d  |  3 
h | f  |  4 
i | g  |  4 
j | g  |  4 
(10 Zeilen) 

Empecé con 'level = 1', no '0' for a, por lo tanto la diferencia.

0

No sé mucho sobre bases de datos, o su terminología, pero ¿funcionaría si realizara un producto conjunto de una tabla consigo mismo N veces para encontrar todos los elementos en el nivel N?

En otras palabras, realice una consulta en la que busque todas las entradas que tengan el padre A. Esto le devolverá una lista de todos sus elementos secundarios. Luego, repita la consulta para encontrar los hijos de cada uno de estos niños. Repita este procedimiento hasta que encuentre todos los niños en el nivel N.

De esta manera no tendría que calcular previamente la profundidad de cada elemento.

Cuestiones relacionadas