Una estructura de datos para conjuntos de árboles.

Los intentos permiten el almacenamiento eficiente de listas de elementos. Los prefijos se comparten, por lo que ahorra espacio.

Estoy buscando una forma similar de almacenar árboles de manera eficiente. Me gustaría poder verificar la membresía y agregar elementos, sabiendo si un árbol dado es un subárbol de algunos árboles almacenados o si existe un árbol almacenado, siendo también un subárbol del árbol dado.

Por lo general, almacenaría alrededor de 500 árboles binarios desequilibrados de altura inferior a 50.

EDITAR

Mi aplicación es algún tipo de verificador de modelos que usa algún tipo de memorización. Imagínese que tengo un estado y las fórmulas siguientes: f = φ y g = ( φ ∨ Psi ) con φ ser un subfórmula complejo, e imaginar que primero quiero saber si f tiene en s . Compruebo si ϕ se mantiene y después de un largo proceso, obtengo que ese es el caso. Ahora, quiero saber si g se mantiene en s . Me gustaría recordar el hecho de que f se mantiene y notar que g ⇒ $s$$f = \phi$$g = (\phi \vee \psi)$$\phi$$f$$s$$\phi$$g$$s$$f$$g \Rightarrow f$para que pueda derivar en s casi al instante. Por el contrario, si he demostrado que g no se mantiene en t , entonces quiero decir que f no se mantiene en t casi al instante.$g$$s$
$g$$t$$f$$t$

Podemos construir un orden parcial en las fórmulas y tener iff g ⇒ f . Para cada estado s , almacenamos dos conjuntos de fórmulas; L ( s ) almacena las fórmulas máximas que contienen y l ( s ) almacena las fórmulas mínimas que no contienen. Ahora, dado un estado sy una fórmula g , puedo ver si ∃ f ∈ L ( s ) , f ⇒ g , o si ∃ f ∈ l ( s $g \geq f$$g \Rightarrow f$$s$$L(s)$$l(s)$$s$$g$$\exists f \in L(s), f \Rightarrow g$ en cuyo caso he terminado y sé directamente si g se cumple en s .$\exists f \in l(s), g \Rightarrow f$$g$$s$

Actualmente, y L se implementan como listas y esto claramente no es óptimo porque necesito iterar a través de todas las fórmulas almacenadas individualmente. Si mis fórmulas fueran secuencias, y si el orden parcial fuera "es un prefijo de", entonces un trie podría resultar mucho más rápido. Desafortunadamente, mis fórmulas tienen una estructura de árbol basada en ¬ , ∧ , un operador modal y proposiciones atómicas.$L$$l$$\neg, \wedge$

Como señalan @Raphael y @Jack, podría secuenciar los árboles, pero me temo que no resolvería el problema porque el orden parcial en el que estoy interesado no correspondería a "es un prefijo de".

Es posible que desee consultar g-tries . Esta es esencialmente la estructura de datos que está buscando, pero diseñada para su uso con gráficos generales en lugar de solo árboles. Como tal, no estoy seguro de que los g-try tengan buenas garantías teóricas, creo que usan un algoritmo de canonización de gráficos como subrutina, pero en la práctica parecen funcionar bien.

(No tenga miedo de que el documento vinculado se trate de "motivos de red en redes biológicas": el g-trie es una estructura de datos abstractos perfectamente buena para gráficos).

Una forma especial de esto es la persistencia : consulte los documentos Cómo hacer que las estructuras de datos sean persistentes por Driscoll, Sarnak, Sleator y Tarjan, y la ubicación del punto planar utilizando árboles de búsqueda persistentes de Sarnak y Tarjan, que almacenan familias de árboles relacionados.

Esto suena un poco como un bosque (bosques disjuntos ) ...

Se amortiza el costo de inserción a través de una técnica llamada unión por rango y la operación de búsqueda mediante compresión de ruta . Sé que también hay una versión persistente de esta estructura desarrollada por Sylvain Conchon y Jean-Christophe Filliâtre, pero no tengo idea de si esto es lo mismo que Jack menciona ...

¿Qué pasa con los autómatas de árboles mínimos ?

En "Estructuras de datos puramente funcionales" (1998), Chris Okasaki propone intentos de árboles binarios utilizando la agregación de tipos (10.3.2).

No sé si esto es de inmediato ayuda; la solución dada allí podría no ser implementable directamente.

En la jerga del programador: si crea los árboles a partir de sub-expresiones / árboles / DAG comunes, tendría un buen modelo compacto. Gráficos acíclicos así dirigidos. Entonces un conjunto de árboles sería suficiente.

árbol de clase pública {Operación de cadena; Árbol [] subárboles;

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;
}

...}

Mapa commonSubExpressions = new HashMap ();

Tree get (String expressionSyntax) {Tree t = new Tree (); t.operation = ...; t.subtrees = ... llamada recursiva para subir subexpresiones; Árbol t2 = commonSubExpressions.get (t); if (t2 == nulo) {t2 = t; commonSubExpressions.put (t2, t2); } devuelve t2; }}