Если есть одно большое, статичное дерево, и вы будете искать множество поддеревьев в одном и том же большом дереве, вы можете захотеть аннотировать каждый узел набором хешей всех его поддеревьев на заданную глубину в зависимости от того, сколько памяти вы используете. готовы потратить на эту функциональность. Затем создайте карту из хеш-значений в набор узлов, которые являются корнями поддерева с этим хеш-значением. Затем просто проверьте каждый из них, предположительно, намного дешевле, чем обход, для хеша корня дерева запросов на ту же глубину.
у некоторый код, который использует дерево (обычное дерево, которое может иметь неограниченное количество узлов, но без пересечения, то есть два родительских узла не будут указывать на один и тот же дочерний узел). Во всяком случае, две вещи:
1) Существуют ли известные алгоритмы поиска поддерева в дереве.
2) Существуют ли какие-либо библиотеки Java (или библиотеки в этом отношении), которые уже реализуют этот алгоритм? Даже если их нет, кто-нибудь может порекомендовать какую-либо хорошую библиотеку дерева Java общего назначения?
Я хочу использовать эти деревья для хранения данных в формате дерева, а не для их возможностей поиска.
Чтобы немного расширить: я использую дерево как часть игры, чтобы вести историю того, что происходит, когда происходят определенные события. Например, A может поразить B, который может поразить два A, которые могут поразить еще два A и т.д.
Это будет выглядеть примерно так:
A
|
B
/
A
/ \
A A
/ \
A A
Конечно, есть нечто большее, чем просто А и В. То, что я хочу сделать, - это то, что (для системы достижений) я могу сказать, когда, скажем, А достиг двух А:
A
/ \
A A
Я хочу иметь возможность легко узнать, содержит ли первое дерево это поддерево. И я не хочу писать весь код для этого, если мне не нужно :)