Создание дерева из списка кортежей

Question

Кажется, я сейчас слепой, поэтому мне нужно спросить здесь. Я хочу отсортировать список кортежей, которые выглядят так:

(id, parent_id, value)

Так что это представление дерева в виде плоского списка списков узлов дерева.

Например, ввод

(1, None, '...')
(3, 2', '...')
(2, 1, '...')
(4, 1, '...')
(5, 2, '...')
(6, None, '...')

Должен ли он потом так сортироваться

(1, None, '...')
(2, 1, '...')
(3, 2', '...')
(5, 2, '...')
(4, 1, '...')
(6, None, '...')

Любая подсказка будет высоко оценена. Заранее спасибо.

Answer 1

Python сортирует кортежи слева направо, поэтому если вы упорядочите свои кортежи так, чтобы первый ключ сортировки был первым элементом и т. Д., Это было бы достаточно эффективно.

Сопоставление списка кортежей с деревом неясно из того, что вы описываете. Пожалуйста, нарисуйте или объясните более подробно. Например, ваш пример выглядит так:

_{(источник: sabi.net )}

Если у вас есть два узла без родителя, это больше похоже на лес, чем на дерево. Что вы пытаетесь изобразить с помощью дерева? Что означает «отсортированный» в этом контексте?

Answer 2

Я не уверен, что вполне понимаю, что именно вы пытаетесь сделать, но если у вас есть лес в виде списка узлов, вы не можете просто прочитать его и построить древовидную структуру, а затем записать как обход хлеба всех деревьев? Любая конкретная причина, чтобы избежать этого?

Answer 3

Оливер, если я правильно понимаю, я думаю, что вы можете либо (а) извлечь все кортежи из вашей базы данных в словарь или список, а затем построить дерево, ИЛИ ЖЕ (b) используйте предложение ORDER BY при извлечении кортежей, чтобы они были в том порядке, в котором вы добавите их в дерево.

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

Roland