Какой самый эффективный / элегантный способ разбить плоский стол на дерево?

Question

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

Id   Name         ParentId   Order
 1   'Node 1'            0      10
 2   'Node 1.1'          1      10
 3   'Node 2'            0      20
 4   'Node 1.1.1'        2      10
 5   'Node 2.1'          3      10
 6   'Node 1.2'          1      20

Вот диаграмма, где мы имеем [id] Name. Корневой узел 0 вымышленный.

                       [0] ROOT
                          /    \ 
              [1] Node 1          [3] Node 2
              /       \                   \
    [2] Node 1.1     [6] Node 1.2      [5] Node 2.1
          /          
 [4] Node 1.1.1

Какой минималистичный подход вы бы использовали для вывода этого в HTML (или текст, если на то пошло) как правильно упорядоченное, правильно отступающее дерево?

Предположим, что у вас есть только базовые структуры данных (массивы и хеш-карты), нет причудливых объектов со ссылками родитель / потомок, нет ORM, нет фреймворка, только две ваши руки. Таблица представлена ​​в виде набора результатов, к которому можно получить произвольный доступ.

Псевдокод или простой английский в порядке, это чисто концептуальный вопрос.

Бонусный вопрос: существует ли принципиально лучший способ хранения древовидной структуры, подобной этой, в СУБД?

---

ИЗМЕНЕНИЯ И ДОПОЛНЕНИЯ

Чтобы ответить на вопрос одного комментатора ( Mark Bessey ): корневой узел не нужен, потому что он все равно никогда не будет отображаться. ParentId = 0 - это соглашение для выражения "это верхний уровень". Столбец «Порядок» определяет порядок сортировки узлов с одним и тем же родителем.

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

Дерево может быть сколь угодно глубоким. Каждый узел может иметь N детей. Однако я не имел в виду дерево «миллионов записей».

Не путайте мой выбор имен узлов ('Node 1.1.1') с тем, на что можно положиться. С таким же успехом узлы можно было бы назвать «Фрэнк» или «Боб», структура имен не подразумевается, это просто для того, чтобы сделать их читаемыми.

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

Answer 1

Если элементы расположены в древовидном порядке, как показано в вашем примере, вы можете использовать что-то вроде следующего примера Python:

delimiter = '.'
stack = []
for item in items:
  while stack and not item.startswith(stack[-1]+delimiter):
    print "</div>"
    stack.pop()
  print "<div>"
  print item
  stack.append(item)

То, что это делает, поддерживает стек, представляющий текущую позицию в дереве. Для каждого элемента в таблице он выталкивает элементы стека (закрывая соответствующие элементы div), пока не найдет родителя текущего элемента. Затем он выводит начало этого узла и помещает его в стек.

Если вы хотите вывести дерево, используя отступы, а не вложенные элементы, вы можете просто пропустить операторы print, чтобы напечатать div, и вывести число пробелов, равное кратному размеру стека, перед каждым элементом. Например, в Python:

print "  " * len(stack)

Вы также можете легко использовать этот метод для создания набора вложенных списков или словарей.

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

idx = {}
idx[0] = []
for node in results:
  child_list = []
  idx[node.Id] = child_list
  idx[node.ParentId].append((node, child_list))

Это создает дерево массивов кортежей (!). idx [0] представляет корень (и) дерева. Каждый элемент массива представляет собой 2-кортеж, состоящий из самого узла и списка всех его дочерних элементов. После создания вы можете удерживать idx [0] и сбрасывать idx, если только вы не хотите обращаться к узлам по их ID.

Answer 2

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

Затем, пожертвовав небольшим количеством памяти, особенно если ваше дерево редкое и / или несбалансированное, вы можете, с небольшим количеством математической математики, получить доступ ко всем строкам случайным образом, сохраняя ваше дерево, сначала ширину в массиве, вот так ( для двоичного дерева):

String[] nodeArray = [L0root, L1child1, L1child2, L2Child1, L2Child2, L2Child3, L2Child4] ...

Вы знаете свою длину строки, вы знаете это

Я сейчас на работе, поэтому не могу тратить на это много времени, но с интересом могу принести немного кода для этого.

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

Answer 3

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

Редактировать: Сначала я прочитал бы всю таблицу в массив, чтобы она не запрашивала БД повторно. Конечно, это не будет практично, если ваш стол очень большой.

После того, как структура построена, я должен сначала пройти через нее на глубину и распечатать HTML.

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

Answer 4

Подумайте об использовании инструментов nosql, таких как neo4j, для иерархических структур. например, сетевое приложение, такое как linkedin, использует couchbase (другое решение nosql)

Но используйте nosql только для запросов уровня витрины данных, а не для хранения / обслуживания транзакций