Простой способ найти поддерево в дереве

Question

Я пишу некоторый код, который использует Дерево (обычное дерево, которое может иметь неограниченное количество узлов, но без пересечения, т.е. два родительских узла не будут указывать на один и тот же дочерний узел). Во всяком случае, две вещи:

1) Существуют ли известные алгоритмы поиска поддерева в дереве.

2) Есть ли библиотеки Java (или библиотеки в этом отношении), которые уже реализуют этот алгоритм? Даже если их нет, кто-нибудь может порекомендовать какую-либо хорошую библиотеку дерева Java общего назначения?

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

Чтобы немного расширить: я использую дерево как часть игры, чтобы вести историю того, что происходит, когда происходят определенные события. Например, A может поразить B, который может поразить два A, которые могут поразить еще два A и т. Д.

Это будет выглядеть примерно так:

    A
    |
    B
   /
  A 
 / \  
A   A
   / \
  A   A

Конечно, есть нечто большее, чем просто А и В. То, что я хочу сделать, - это то, что (для системы достижений) сможет определить, когда, скажем, А достиг двух А:

  A
 / \
A   A

Я хочу иметь возможность легко узнать, содержит ли первое дерево это поддерево. И я не хочу писать весь код для этого, если мне не нужно:)

Answer 1

Выглядит как простой алгоритм: найдите корень дерева поиска в дереве игры и проверьте, являются ли дети дерева поиска подмножеством детей в дереве игры.

Из ваших объяснений я не уверен, есть ли в дереве поиска

  A
 / \
A   A

должно соответствовать этому дереву:

  A
 /|\
A C A

(т.е. если несоответствующие дети должны игнорироваться.)

В любом случае, вот код, с которым я только что поиграл. Это полностью работающий пример и поставляется с основным методом и простым классом Node. Не стесняйтесь играть с ним:

import java.util.Vector;

public class PartialTreeMatch {
    public static void main(String[] args) {
        Node testTree = createTestTree();
        Node searchTree = createSearchTree();

        System.out.println(testTree);
        System.out.println(searchTree);

        partialMatch(testTree, searchTree);
    }

    private static boolean partialMatch(Node tree, Node searchTree) {
        Node subTree = findSubTreeInTree(tree, searchTree);
        if (subTree != null) {
            System.out.println("Found: " + subTree);
            return true;
        }
        return false;
    }

    private static Node findSubTreeInTree(Node tree, Node node) {
        if (tree.value == node.value) {
            if (matchChildren(tree, node)) {
                return tree;
            }
        }

        Node result = null;
        for (Node child : tree.children) {
            result = findSubTreeInTree(child, node);

            if (result != null) {
                if (matchChildren(tree, result)) {
                    return result;
                }
            }
        }

        return result;
    }

    private static boolean matchChildren(Node tree, Node searchTree) {
        if (tree.value != searchTree.value) {
            return false;
        }

        if (tree.children.size() < searchTree.children.size()) {
            return false;
        }

        boolean result = true;
        int treeChildrenIndex = 0;

        for (int searchChildrenIndex = 0;
                 searchChildrenIndex < searchTree.children.size();
                 searchChildrenIndex++) {

            // Skip non-matching children in the tree.
            while (treeChildrenIndex < tree.children.size()
                  && !(result = matchChildren(tree.children.get(treeChildrenIndex),
                                              searchTree.children.get(searchChildrenIndex)))) {
                treeChildrenIndex++;
            }

            if (!result) {
                return result;
            }
        }

        return result;
    }

    private static Node createTestTree() {
        Node subTree1 = new Node('A');
        subTree1.children.add(new Node('A'));
        subTree1.children.add(new Node('A'));

        Node subTree2 = new Node('A');
        subTree2.children.add(new Node('A'));
        subTree2.children.add(new Node('C'));
        subTree2.children.add(subTree1);

        Node subTree3 = new Node('B');
        subTree3.children.add(subTree2);

        Node root = new Node('A');
        root.children.add(subTree3);

        return root;
    }

    private static Node createSearchTree() {
        Node root = new Node('A');
        root.children.add(new Node('A'));
        root.children.add(new Node('A'));

        return root;
    }
}

class Node {
    char value;
    Vector<Node> children;

    public Node(char val) {
        value = val;
        children = new Vector<Node>();
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();

        sb.append('(');
        sb.append(value);

        for (Node child : children) {
            sb.append(' ');
            sb.append(child.toString());
        }

        sb.append(')');

        return sb.toString();
    }
}

Answer 2

Вы ищете какие-то конкретные ограничения для поддерева? Если нет, то простого обхода l должно быть достаточно для идентификации поддеревьев (в основном каждый узел рассматривается как корень поддерева).

Я полагаю, вы обнаружите, что API, который вам нужен для дерева, сильно зависит от вашего конкретного приложения - настолько, что общие реализации не очень полезны. Возможно, если бы вы могли сообщить нам, для какого приложения будет использоваться дерево, мы могли бы сообщить подробности.

Кроме того, если вы просто используете дерево для хранения данных, вы можете спросить себя, зачем вам дерево. Этот ответ должен также ответить на вопрос в моем предыдущем абзаце.

Answer 3

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

Answer 4

Интересно, есть ли расширение алгоритма Кнута, которое будет более эффективным, чем наивный обход ...