Самый эффективный алгоритм для добавления ветвей дерева

Question

Я должен построить добавить ветви (узлы) в виде дерева.Я изо всех сил пытаюсь определить, какова самая низкая O (n) техника.

Мои данные представлены следующим образом:

Id  ParentId    Value

0   null        Bob
1   0           Amy
2   1           Susan
3   1           Matt
4   2           Keith
5   4           Craig
6   4           Derrick

Таким образом, дерево будет выглядеть так:

Все, что я могу придумать, - это алгоритм n ^ 2, который для каждой записи сканирует все остальные записи, чтобы определить, принадлежат ли они подузлу.Я также удаляю записи из массива для сканирования по мере их добавления.Таким образом, если память служит (это, вероятно, нет), то чуть меньше n ^ 2.

Существуют ли более эффективные методы?

Answer 1

Предполагая, что ваш язык имеет какой-то тип массива list / vector / resizable, это довольно просто.

Создайте пустой список для каждого идентификатора.Выполните итерацию по каждой строке, и если ParentId не равен NULL, добавьте Id в список ParentId.

Теперь у вас есть дочерние элементы для каждой записи за O (n) раз.