# A data structure for sets of trees.

Tries allow for efficient storage of lists of elements. The prefixes are shared so it is space efficient.

I am looking for a similar way to efficiently store trees. I would like to be able to check for membership and to add elements, knowing if a given tree is a subtree of some stored trees or if there exists a stored tree being a subtree of the given tree is also desirable.

I would typically store about 500 unbalanced binary trees of height less than 50.

EDIT

My application is some kind of model checker using some sort of memoization. Imagine I have a state $s$ and the following formulae: $f = \phi$ and $g = (\phi \vee \psi)$ with $\phi$ being a complex subformula, and imagine I first want to know if $f$ holds in $s$. I check if $\phi$ holds and after a lengthy process I obtain that it is the case. Now, I want to know if $g$ holds in $s$. I would like to remember the fact that $f$ holds and to notice that $g \Rightarrow f$ so that I can derive $g$ in $s$ almost instantly.
Conversely, if I have proved that $g$ does not hold in $t$, then I want to tell that $f$ does not hold in $t$ almost instantly.

We can build a partial order on formulae, and have $g \geq f$ iff $g \Rightarrow f$. For each state $s$, we store two sets of formulae; $L(s)$ stores the maximal formulae that hold and $l(s)$ stores the minimal formulae that do not hold. Now given a state $s$ and a formula $g$, I can see if $\exists f \in L(s), f \Rightarrow g$, or if $\exists f \in l(s), g \Rightarrow f$ in which case I am done and I know directly whether $g$ holds in $s$.

Currently, $L$ and $l$ are implemented as lists and this is clearly not optimal because I need to iterate through all stored formulae individually. If my formulae were sequences, and if the partial order was "is a prefix of" then a trie could prove much faster. Unfortunately my formulae have a tree like structure based on $\neg, \wedge$, a modal operator, and atomic propositions.

As @Raphael and @Jack points out, I could sequentialise the trees, but I fear it would not solve the problem because the partial order I am interested in would not correspond to "is a prefix of".

-
Just a quick idea: Have you tried sequentialising trees (perform an in-order traversal, list the visited nodes accordingly and add special elements for up resp down movements) and storing those in a trie? Of course, this would "only" allow checks for left subtrees, in a sense. – Raphael Apr 22 '11 at 19:41
What if you simply used a serialisation $S$ of trees with the following property: $T$ is a subtree of $T'$ if and only if $S(T)$ is a substring of $S(T')$? Constructing such an $S$ is straightforward [if you first find a canonical form of your trees]. After that, your question is equivalent to substring matching, which is a widely-studied problem in stringology. – Jukka Suomela Apr 23 '11 at 1:19
Take a look at term indexing. – starblue Apr 23 '11 at 18:47
Another quick idea would be to store all trees t1,t2,.. in one big tree T, remembering for each edge the set of trees it is part of. Then, to determine if f is a subtree of one of the stored trees you first determine if f is a subtree in T and if yes, then intersect all the edge-label sets of that subtree. The answer is yes iff the intersection is non-empty. (You could also combine the two steps). – Martin B. Apr 26 '11 at 16:00

You might want to check out g-tries. This is essentially the data structure you're looking for, but designed for use with general graphs instead of just trees. As such, I'm not sure that g-tries have good theoretical guarantees -- I think they use a graph canonization algorithm as a subroutine -- but in practice they seem to work well.

(Don't be scared that the linked paper is about "network motifs in biological networks": the g-trie is a perfectly good abstract data structure for graphs.)

-

A special form of this is persistence: See papers Making Data Structures Persistent by Driscoll, Sarnak, Sleator, & Tarjan, and Planar Point Location Using Persistent Search Trees by Sarnak & Tarjan, which store families of related trees.

-
Thank you for the references. I cannot access Making Data Structures Persistent at the moment, but I am somewhat familiar with the concept of persistence. However, I do not see how I can use persistence to solve my problem. I actually want to use have dictionnaries that map trees to boolean and the same tree could be a key to different values in different dictionnaries. – Abdallah Apr 22 '11 at 8:06
Since I wasn't sure what your application was, I triggered off your analogy to tries, which store strings by sharing prefixes. Your comment that "the same tree could be a key to different values in different dictionaries" doesn't seem to fit with tries either, however. Perhaps you just want some collection of signature for a tree (and all its subtrees) that you can look up? (e.g., using Catalan numbers for binary trees or Prufer codes for labeled trees.) – Jack Apr 22 '11 at 18:35

This sounds a little bit like a forest (disjoint-set forests)...

It amortizes the cost of insertion through a technique called union by rank and the search operation using path compression. I know there's also a persistent version of this structure developed by Sylvain Conchon and Jean-Christophe Filliâtre but I have no idea if this is the same as that which Jack mentions...

-

-

In "Purely Functional Data Structures" (1998), Chris Okasaki proposes tries of binary trees using type aggregation (10.3.2).

I don't know wether this is immediately helps; the solution given there might not be implementable directly.

-

In programmer lingo: If you create the trees from common sub-expressions/trees/DAGs, you would have a nice compact model. So Directed Acyclic Graphs. Then a set of trees would suffice.

public class Tree { String operation; Tree[] subtrees;

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


... }

Map commonSubExpressions = new HashMap();

Tree get(String expressionSyntax) { Tree t = new Tree(); t.operation = ...; t.subtrees = ... recursive call to get on subexpressions; Tree t2 = commonSubExpressions.get(t); if (t2 == null) { t2 = t; commonSubExpressions.put(t2, t2); } return t2; } }

-