Структура данных для множеств деревьев.

Попытки позволяют эффективно хранить списки элементов. Префиксы являются общими, что позволяет экономить место.

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

Обычно я храню около 500 несбалансированных бинарных деревьев высотой менее 50.

РЕДАКТИРОВАТЬ

Мое приложение - это своего рода средство проверки моделей, использующее какие-то памятки. Представьте, что у меня есть состояние и следующие формулы: и где является сложной подформулой, и представьте, что я сначала хочу узнать, выполняется ли в . Я проверяю, выполняется ли и после длительного процесса я понимаю, что это так. Теперь я хочу знать, содержит ли в . Я хотел бы вспомнить тот факт, что имеет место, и заметить, что так что я могу получить в почти мгновенно.f = ϕ g = ( ϕ ∨ ψ ) ϕ f s ϕ g s f g ⇒ f g $s$$f = \phi$$g = (\phi \vee \psi)$$\phi$$f$$s$$\phi$$g$$s$$f$$g \Rightarrow f$$g$$s$
И наоборот, если я докажу, что не выполняется в , то я хочу сказать, что не сохраняется в почти мгновенно.т ф $g$$t$$f$$t$

Мы можем построить частичный порядок на формулах и иметь если . Для каждого состояния мы храним два набора формул; хранит максимальные формулы, которые сохраняются, а хранит минимальные формулы, которые не сохраняются. Теперь, учитывая состояние и формулу , я могу видеть, ли , или если в этом случае я сделано, и я знаю непосредственно, держит ли в .g ⇒ f s L ( s ) l ( s ) s g ∃ f ∈ L ( s ) , f ⇒ g ∃ f ∈ l ( s ) , g ⇒ f g $g \geq f$$g \Rightarrow f$$s$$L(s)$$l(s)$$s$$g$$\exists f \in L(s), f \Rightarrow g$$\exists f \in l(s), g \Rightarrow f$$g$$s$

В настоящее время и реализованы в виде списков, и это явно не оптимально, потому что мне нужно перебирать все сохраненные формулы по отдельности. Если бы мои формулы были последовательностями, и если частичный порядок был «является префиксом», то процесс может оказаться гораздо быстрее. К сожалению, мои формулы имеют древовидную структуру, основанную на , модальном операторе и атомарных предложениях.л ¬ , $L$$l$$\neg, \wedge$

Как указывают @Raphael и @Jack, я мог бы упорядочить деревья, но боюсь, что это не решит проблему, потому что интересующий меня частичный порядок не будет соответствовать «является префиксом».

Возможно, вы захотите проверить G-попытки . По сути, это структура данных, которую вы ищете, но она предназначена для использования с общими графиками, а не просто с деревьями. Таким образом, я не уверен, что у g-try есть хорошие теоретические гарантии - я думаю, что они используют алгоритм канонизации графа в качестве подпрограммы - но на практике они, кажется, работают хорошо.

(Не пугайтесь, что связанная статья о «сетевых мотивах в биологических сетях»: g-trie - это очень хорошая абстрактная структура данных для графов.)

Особой формой этого является постоянство : см. Статьи «Устойчивость структур данных Дрисколла, Сарнака, Слеатора и Тарьяна» и «Расположение плоской точки» с использованием деревьев постоянного поиска »Сарнака и Тарьяна, в которых хранятся семейства связанных деревьев.

Это звучит немного как лес ( непересекающиеся леса ) ...

Он амортизирует стоимость вставки с помощью метода, называемого объединением по рангу, и операции поиска с использованием сжатия пути . Я знаю, что есть постоянная версия этой структуры, разработанная Сильвен Кончон и Жаном-Кристофом Филлиатром, но я понятия не имею, совпадает ли это с той, о которой упоминает Джек ...

Как насчет минимальных автоматов деревьев ?

В «Чисто функциональных структурах данных» (1998) Крис Окасаки предлагает попытки двоичных деревьев с использованием агрегации типов (10.3.2).

Я не знаю, помогает ли это немедленно; данное решение может быть неосуществимо напрямую.

На языке программирования: если вы создаете деревья из общих подвыражений / trees / DAG, у вас будет хорошая компактная модель. Направленные ациклические графы. Тогда достаточно деревьев.

открытый класс Tree {String operation; Дерево [] поддеревья;

public int compareTo(Tree rhs) {
    if (rhs == null) return false;
    int cmp = operation.compareTo(rhs.operation);
    if (cmp == 0) {
        cmp = Arrays.compareTo(subtrees, rhs.subtrees);
    }
    return cmp;
}

...}

Карта commonSubExpressions = new HashMap ();

Tree get (String expressionSyntax) {Tree t = new Tree (); t.operation = ...; t.subtrees = ... рекурсивный вызов для получения подвыражений; Tree t2 = commonSubExpressions.get (t); if (t2 == null) {t2 = t; commonSubExpressions.put (t2, t2); } возврат t2; }}