Как быстро получить всех родителей для всех листьев в дереве?

У меня есть, возможно, большая корневая древовидная структура, которую я хочу преобразовать в матрицу X * Y, где X — количество листьев в дереве, а Y — количество узлов в дереве со степенью больше 1, т. е. корневой узел и внутренний узлы. Матрица должна быть заполнена следующим образом:

Mi,j = { 0, если лист i имеет предка j, 1 в противном случае

Например, это дерево:

      --A 
     /
    1   B
   / \ /
  /   3  
 /     \
0       C
 \ 
  \   --D
   \ /
    2
     \--E

переведет в эту матрицу:

  0 1 2 3
A T T F F
B T T F T
C T T F T
D T F T F
E T F T F

Поскольку деревья могут стать довольно большими (возможно, около 100 000 листьев), мне было интересно, есть ли более умный/быстрый способ сделать это, чем обход дерева для каждого из листовых узлов. Такое чувство, что где-то в этой задаче есть какой-то алгоритм, но я пока не разобрался. Может быть, кто-то может помочь?

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


algorithm data-structures tree graph-algorithm
person Stefan Seemayer    schedule 05.09.2012    source источник
comment
Я думаю, что самая большая проблема здесь - это сама матрица - одно тривиальное улучшение состояло бы в том, чтобы хранить только список предков для каждого листа, но даже в этом случае вы все равно не можете получить намного быстрее (по крайней мере, в терминах большого O), чем обход всех предков, так как вы все равно должны добавить их в список. Возможно, вам следует подумать о том, как именно вы собираетесь использовать эти данные и действительно ли вам нужно хранить все это явно, и тогда может появиться что-то лучшее.   -  person Ivan Vergiliev    schedule 05.09.2012
comment
К сожалению, я привязан к матричной структуре данных, поскольку она понадобится мне в качестве входных данных для дальнейших шагов, когда я не вижу, как можно включить список предков. Спасибо, что указали на это, однако!   -  person Stefan Seemayer    schedule 05.09.2012

Ответы (1)


arrow_upward
1
arrow_downward

Я бы выбрал обход после заказа.

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

decalrations для функций, которые мы будем использовать:

list merge(list1,list2) //merges two lists and creates a new list
list create() // creates a new empty list
void add(list,e) // appends e to the list
void setParent(leaf,node) //sets (in your matrix) node as a parent of leaf

Псевдокод:

list Traverse(root):
  if (root == nil):
      l <- create()
      return l
  else if (root is leaf):
      l <- create()
      add(l,root)
      return l
  else: 
      l1 <- Traverse(root.left)
      l2 <- Traverse(root.right)
      l <- merge(l1,l2)
      for each leaf in l:
          setParent(leaf,root)
      return l

Время O(n*m) - на настройку матрицы (правда сам алгоритм O(nlogn) времени на сбалансированное дерево).

Если вы хотите предотвратить инициализацию O(n*m), вы можете инициализируйте матрицу в O(1), а затем запустите описанный выше алгоритм в O(nlogn). Хотя это даст лучшую асимптотическую сложность, я сомневаюсь, что на самом деле это будет быстрее.

person amit    schedule 05.09.2012
comment
Спасибо! Я придумал что-то подобное во время обеденного перерыва (с использованием логических операций над столбцами выходной матрицы, в основном с использованием той же стратегии обхода), но ваше, вероятно, более быстрое и более общее решение. - person Stefan Seemayer; 05.09.2012