Эффективный обход однонаправленного дерева

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

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

Answer 3

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

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

Answer 4

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

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