Как обновить дерево из списка его узлов быстрее, чем для O (n ^ 2)? - PullRequest
Новая
       10

Как обновить дерево из списка его узлов быстрее, чем для O (n ^ 2)?

3 голосов
/ 16 февраля 2012

Дано: список N узлов.Каждый узел состоит из 2 чисел: nodeID и parentID.parentID может быть null (если это корневой узел).

Существует ли алгоритм для воссоздания дерева из этого списка узлов со сложностью по времени лучше, чем O (N ^ 2)?

Каждый узел может иметь 0 или более дочерних элементов.

Краткое описание алгоритма со сложностью O (N ^ 2): 

  find a root Node, put it to a Queue
  while Queue is not empty
      parentNode = Queue.pop()
      loop through nodes
          if currentNode.parentId = parentNode.id
              parentNode.addChild(currentNode)
              queue.push(currentNode)
              nodes.remove(currentNode)

Кажется, что этот алгоритм имеетO (N ^ 2) временная сложность (с небольшим коэффициентом, может быть, 0,25).Но я могу ошибаться при расчете сложности здесь.

Ответы [ 3 ]

2 голосов
/ 16 февраля 2012

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

Сделайте это в два концептуальных шага с хеш-таблицей:

  1. Сначала создайте хеш-таблицу, которая связывает идентификаторы узла с их фактическим узлом.
  2. Затем найдите родительский узел на основе родительского узлаИдентификатор в хэш-таблице и добавление дочернего элемента к этому родителю.

Более программно: 

for each node
    add node to hash table indexed by node's parent
for each node
    if parent is null set node as the root
    otherwise look up in the hash table the parent from the parent ID of the node
    add the node as a child of the found parent

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

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

В целом, это должно быть в среднем O(N).

1 голос
/ 17 февраля 2012

Я не знаю, что вы вводите, но давайте предположим, что это какой-то неупорядоченный список.

Затем вы можете создать древовидную структуру, просто поместив их в структуру данных, которая позволяет искать их по их ID узла. Например, массив будет делать это. Затем у вас есть дерево, которое связано только в направлении родителей. Преобразование из неупорядоченного списка в этот массив возможно за линейное время, если предположить, что идентификаторы узла уникальны.

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

1 голос
/ 16 февраля 2012

Для каждого узла инициализируйте список дочерних элементов и для каждого узла обновите список дочерних элементов самого себя.Сложность O (n). 

For node in NodeList:
    node.childList = []

For node in NodeList:
    if node.parent is not NULL:
        node.parent.childList.append(&node)

Если родительская ссылка недоступна, создайте хэш-карту.FWIW, лучшая сложность отображения хеша в худшем случае - O (logn) для каждой вставки или поиска.Таким образом, конечная сложность становится O (nlogn).

...