Oberon space
General Category => Общий раздел => Тема начата: vlad от Ноябрь 26, 2013, 09:10:57 pm
-
Вобщем ничего такого сложного, но поскольку я на нее потратил сильно больше времени, чем казалось она того стоит (может просто тупил, да), то решил поделиться. ИМХО как вариант для собеседования тоже подойдет.
Дано: дерево в виде таблицы id'шек:
parent_id id
--------------
10 1
10 2
20 3
-1 20
20 10
parent_id = -1 означает корень, корней может быть больше одного
Плучить: таблицу отсортированную так, что каждому следующему parent_id предшествует его "объявление" в виде id. Т.е., для данного примера это будет:
parent_id id
--------------
-1 20
20 3
20 10
10 1
10 2
Решаем на любом языке (оберон как всегда интереснее всего :)
Решение на чистом SQL (из него все пошло) тоже интересно :)
-
Решение на чистом SQL (из него все пошло) тоже интересно :)
Решение на SQL работало на том основании, что id генерировались последовательно и родитель всегда создавался первым. Соответственно, банальный "ORDER BY parent_id, id" замечательно решал задачу. Случай перемещения из одного родителя в другой был довольно редок и про него забыли. Но в один прекрасный день (сегодня, гхм) он о себе напомнил. Пришлось переписывать на питоне :)
-
Решение в лоб (-1 корень, как я понял): :)
function print_tree(t, key)
for _, elem in pairs(t) do
if elem[1] == key then
print(elem[1], elem[2])
print_tree(t, elem[2])
end
end
end
local t = {
{10, 1},
{10, 2},
{20, 3},
{-1, 20},
{20, 10}
}
print_tree(t, -1)ps Просто вывод на экран.
-
Решение в лоб (-1 корень, как я понял): :)
Зачет! Получилось слишком просто, усложним задачу :) Как насчет детектирования сирот?
P.S. Можно еще поработать над сложностью. В данном варианте получается что-то типа O(n^depth), где n - количество записей, а depth глубина дерева (какая-то усредненная).
-
Решаем на любом языке (оберон как всегда интереснее всего :)
Решение на чистом SQL (из него все пошло) тоже интересно :)
Это не сортировка, а обход дерева в ширину (горизонтальный обход).
На нормальном языке: построить дерево, обойти в ширину :)
На SQL сводится к изучению рекурсивных извратов для конкретной реализации.
-
Не обязательно обход в ширину. Это вполне себе может топологическая сортировка.
-
Решение в лоб (-1 корень, как я понял): :)
Зачет! Получилось слишком просто, усложним задачу :) Как насчет детектирования сирот?
Ну просто флаг в таблицу добавить, и отобрать потом по нему ентих сирот.
P.S. Можно еще поработать над сложностью. В данном варианте получается что-то типа O(n^depth), где n - количество записей, а depth глубина дерева (какая-то усредненная).
В реальных задачах делается ровно так же, только у таблицы есть индекс по ключу.
-
Не обязательно обход в ширину. Это вполне себе может топологическая сортировка.
Может быть, но все зависит от требований. Например, есть один родитель с кучей детей. При топологической сортировке без извратов дети будут в случайном порядке. А при построении и обходе дерева легко добиться, чтобы дети были отсортированы.
P.S. Хотя для топологической, кажется, тоже легко написать соотв. функцию сравнения.