Алгоритм выбора узлов и их родителей в дереве

Question

Допустим, у вас есть древовидная структура:

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

Я представил это в базе данных примерно так:

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

Я хотел бы написать функциюданный уровень вернет все узлы на этом уровне и их родителей.

Например:

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

Есть мысли?

Answer 1

Здесь я перебираю уровни, добавляя каждый к таблице с уровнем, на котором он находится.

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)

Answer 2

Бесстыдно копируя из Джейсона, я сделал решение без функции, которое я протестировал с postgresql (у которого есть функции - возможно, это сработало бы из коробки).

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;

Оператор обновления является чистым SQL и должен повторяться для каждого уровня, чтобы заполнить таблицу.

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)

Я начал с 'level = 1', а не '0' для a, поэтому разница.

Answer 3

Решение для MySQL далеко не идеальное.

Предполагая, что максимальная глубина дерева известна:

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

Это даст вам каждый узел и его глубину. После этого тривиально выбрать каждый элемент, глубина которого меньше X.

Если глубина дерева неизвестна или значительно велика, то решение является итеративным, как сказал другой автор.

Answer 4

Обычный способ сделать это, если в вашем варианте SQL нет специальной нестандартной функции, это построить таблицу путей, в которой есть следующие столбцы:

• parent_key
• child_key
• PATH_LENGTH

Чтобы заполнить эту таблицу, вы используете рекурсивный или процедурный цикл, чтобы найти всех родителей, прародителей, прабабушек и т. Д. Для каждого элемента в вашем списке элементов. Рекурсия или цикл должны продолжаться до тех пор, пока вы не прекратите находить более длинные пути, которые возвращают новые пары.

В конце концов, у вас будет список записей, которые сообщают вам такие вещи, как (a, b, 1), (a, f, 2), (a, h, 3) и т. Д. Затем, чтобы получить все то есть на уровне x и выше, вы делаете отдельный выбор для всех дочерних элементов с path_length <= x (объединенным с корнем, если только вы не включили запись (null, root, 0), когда вы запустили рекурсию / цикл . </p>

Было бы неплохо, если бы SQL лучше справлялся с ориентированными графами (деревьями), но, к сожалению, вы должны обмануть его с помощью дополнительных таблиц, подобных этой.

Answer 5

Я не знаю много о базах данных или их терминологии, но сработает ли это, если вы выполнили совместное произведение таблицы с собой N раз, чтобы найти все элементы на уровне N?словами, выполните запрос, в котором вы ищите все записи, у которых есть родитель А. Это вернет вам список всех его дочерних элементов.Затем повторите запрос, чтобы найти детей каждого из этих детей.Повторяйте эту процедуру, пока не найдете всех детей на уровне N.

Таким образом, вам не придется предварительно вычислять глубину каждого элемента.

Answer 6

SQL не всегда хорошо справляется с этими рекурсивными проблемами.

Некоторые платформы СУБД позволяют вам использовать Распространенные табличные выражения , которые фактически являются запросами, которые сами себя вызывают, позволяя выполнять рекурсию через структуру данных. В MySQL это не поддерживается, поэтому я рекомендую вам использовать несколько запросов, созданных и управляемых скриптом, написанным на другом языке.