Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Microsoft SQL Server Новый топик    Ответить
 Выбор помеченого поддерева  [new]
Дядя Петя Вася
Member

Откуда:
Сообщений: 1368
итак есть дерево - 2 таблицы - одна с узлами, вторая с отношениями - сын - батяня.
Есть третья таблица - помеченные узлы.
Нужно выбрать поддерево с силуэтом помеченных узлов, алгоритм простой - идем от корня вниз до самого нижнего помеченного узла, все что попало попадает в результат. Причем в результате надо пометить 1 если это помеченный узел и 0 если непомеченный.
declare @t table(id int, descr varchar(20))
insert @t select 1, 'корень'
insert @t select 2, 'поддерево1'
insert @t select 3, 'поддерево2'
insert @t select 4, 'поддерево3'
insert @t select 5, 'поддерево4'
insert @t select 6, 'поддерево5'
insert @t select 7, 'поддерево6'
insert @t select 8, 'поддерево7'
;

declare @link table(id int, parent int)
insert @link select 2, 1
insert @link select 3, 2
insert @link select 4, 1
insert @link select 5, 4
insert @link select 6, 4
insert @link select 7, 1
insert @link select 8, 7
;

declare @point table(point int)
insert @point select 2
insert @point select 5
insert @point select 8


вывод будет
1 0
2 1
4 0
5 1
7 0
8 1

К сообщению приложен файл. Размер - 17Kb
9 ноя 16, 19:29    [19876629]     Ответить | Цитировать Сообщить модератору
 Re: Выбор помеченого поддерева  [new]
Дядя Петя Вася
Member

Откуда:
Сообщений: 1368
естественно на пути от корня до низа может быть много помеченных узлов - рисовать вломы было.
9 ноя 16, 19:30    [19876635]     Ответить | Цитировать Сообщить модератору
 Re: Выбор помеченого поддерева  [new]
buser
Member

Откуда: Санкт-Петербург
Сообщений: 4539
Дядя Петя Вася, идите от отмеченных узлов вверх!
9 ноя 16, 19:44    [19876684]     Ответить | Цитировать Сообщить модератору
 Re: Выбор помеченого поддерева  [new]
Дядя Петя Вася
Member

Откуда:
Сообщений: 1368
buser
Дядя Петя Вася, идите от отмеченных узлов вверх!

повторятьться будут проходы, хотя на худой конец сгодится.
9 ноя 16, 20:00    [19876745]     Ответить | Цитировать Сообщить модератору
 Re: Выбор помеченого поддерева  [new]
buser
Member

Откуда: Санкт-Петербург
Сообщений: 4539
+
не как руководство к действию
;with rolluptree
as
(
	select id, parent, 1 as marked from @link lnk where exists(select * from @point n where n.point = lnk.id)
	union all
	select link.id, link.parent, 0
	from @link link 
		join rolluptree on rolluptree.parent = link.id
)
select ids, min(marked)
from rolluptree 
unpivot (ids for val in ([id], [parent]) ) unpiv
group by ids
9 ноя 16, 23:25    [19877410]     Ответить | Цитировать Сообщить модератору
 Re: Выбор помеченого поддерева  [new]
iljy
Member

Откуда:
Сообщений: 8711
Дядя Петя Вася,

;with cte as
(
	select point id, 1 marked
	from @point
		union all
	select l.parent, 0
	from cte c join @link l on l.id = c.id
)
select id, MAX(marked) marked
from cte
group by id
10 ноя 16, 01:24    [19877665]     Ответить | Цитировать Сообщить модератору
 Re: Выбор помеченого поддерева  [new]
Mike_za
Member

Откуда: Москва
Сообщений: 1176
Внезапно может оказаться, что while сделает cte со свистом.
10 ноя 16, 01:29    [19877672]     Ответить | Цитировать Сообщить модератору
 Re: Выбор помеченого поддерева  [new]
Владислав Колосов
Member

Откуда:
Сообщений: 8717
Дядя Петя Вася,

перейдите к использованию иерархического типа. В это случае Вы легко отфильтруете по результату оставшиеся узлы и не потребуются лишние прогоны.
10 ноя 16, 10:28    [19878068]     Ответить | Цитировать Сообщить модератору
 Re: Выбор помеченого поддерева  [new]
Akina
Member

Откуда: Зеленоград, Москва, Россия
Сообщений: 21194
Дядя Петя Вася
buser
Дядя Петя Вася, идите от отмеченных узлов вверх!
повторятьться будут проходы, хотя на худой конец сгодится.
Отмечайте пройденные узлы. Наткнувшись на отмеченный узел, прерывайтесь (выше тоже всё помечено) и начинайте обработку следующего. Узлы на обработку берите в порядке возрастания этажа (расстояния до корня).
10 ноя 16, 10:35    [19878087]     Ответить | Цитировать Сообщить модератору
 Re: Выбор помеченого поддерева  [new]
buser
Member

Откуда: Санкт-Петербург
Сообщений: 4539
Дядя Петя Вася, если к посаженному дереву, к его узлам, добавить уровень... станет еще эффективнее
10 ноя 16, 11:04    [19878192]     Ответить | Цитировать Сообщить модератору
 Re: Выбор помеченого поддерева  [new]
Дядя Петя Вася
Member

Откуда:
Сообщений: 1368
iljy
Дядя Петя Вася,

;with cte as
(
	select point id, 1 marked
	from @point
		union all
	select l.parent, 0
	from cte c join @link l on l.id = c.id
)
select id, MAX(marked) marked
from cte
group by id

красивое решение в плане минимума кода, в плане оптимизации конечно тут перебор. А вот если надо найти в поддереве? то есть задача та же но ищем в в поддереве с вершиной в X. Я вот вижу что можно заджойнить на выборку этого поддерева.
10 ноя 16, 15:42    [19879833]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить