Эффективное перемещение однонаправленного дерева

Question

У меня есть однонаправленное дерево объектов, в котором каждый объект указывает на родителя. Учитывая объект, мне нужно получить все его поддерево потомков, как набор объектов. Объекты фактически не находятся в какой-либо структуре данных, но я могу легко получить коллекцию всех объектов.

Наивный подход состоит в том, чтобы исследовать каждый объект в партии, посмотреть, является ли данный объект предком, и сохранить его в стороне. Это не будет слишком эффективным ... Он несет накладные расходы O (N * N), где N - количество объектов.

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

Мой вопрос: Есть ли эффективный алгоритм, который я здесь игнорирую?

Спасибо,

Юваль = 8-)

Answer 1

Как уже упоминалось, постройте хэш-таблицу/карту объектов в список своих (прямых) детей.

Оттуда вы можете легко найти список прямых детей вашего «целевого объекта», а затем для каждого объекта в списке повторите процесс.

Вот как я сделал это в Java и использовать дженерики, с очередью вместо любого рекурсии:

public static Set<Node> findDescendants(List<Node> allNodes, Node thisNode) { 

    // keep a map of Nodes to a List of that Node's direct children 
    Map<Node, List<Node>> map = new HashMap<Node, List<Node>>(); 

    // populate the map - this is O(n) since we examine each and every node 
    // in the list 
    for (Node n : allNodes) { 

     Node parent = n.getParent(); 
     if (parent != null) { 

      List<Node> children = map.get(parent); 
      if (children == null) { 
       // instantiate list 
       children = new ArrayList<Node>(); 
       map.put(parent, children); 
      } 
      children.add(n); 
     } 
    } 


    // now, create a collection of thisNode's children (of all levels) 
    Set<Node> allChildren = new HashSet<Node>(); 

    // keep a "queue" of nodes to look at 
    List<Node> nodesToExamine = new ArrayList<Node>(); 
    nodesToExamine.add(thisNode); 

    while (nodesToExamine.isEmpty() == false) { 
     // pop a node off the queue 
     Node node = nodesToExamine.remove(0); 

     List<Node> children = map.get(node); 
     if (children != null) { 
      for (Node c : children) { 
       allChildren.add(c); 
       nodesToExamine.add(c); 
      } 
     } 
    } 

    return allChildren; 
} 

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

Answer 2

Ваш вопрос немного абстрактно, но nested sets (прокрутите вниз, может быть немного слишком MySQL конкретным) может быть вариантом для вас. Это чрезвычайно быстро для операций чтения, хотя любые модификации довольно сложны (и должны в среднем изменять половину дерева).

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

Answer 3

Базы данных работают одинаково, поэтому делайте то, что делают базы данных. Создайте хэш-таблицу, которая отображает от родителя к списку-детей. Это берет O (n). Затем использование этой хэш-таблицы сделает поиск и запросы потенциально более эффективными.

Answer 4

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

Пока вы строите дерево, создайте хэш-таблицу. Хэш-таблица ускорит поиск в будущем объектов (O (1) против O (n)).