<p>You might want to check out <a href="http://portal.acm.org/citation.cfm?id=1774422&amp;dl=ACM">g-tries</a>. 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.</p>

<p>(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.)</p>

CC BY-SA 3.0
2011-04-30T01:43:24.803Z
2011-04-30T01:43:24.803Z
Joshua Grochow
<p>A special form of this is <em>persistence</em>: See papers Making Data Structures Persistent by Driscoll, Sarnak, Sleator, &amp; Tarjan, and Planar Point Location Using Persistent Search Trees by Sarnak &amp; Tarjan, which store families of related trees.</p>

CC BY-SA 3.0
2011-04-22T08:06:49.107Z
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
CC BY-SA 3.0
2011-04-22T18:35:58.980Z
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
CC BY-SA 3.0
2011-04-21T23:17:11.603Z
2011-04-21T23:17:11.603Z
Jack
<p>What about <a href="http://en.wikipedia.org/wiki/Tree_automaton" rel="nofollow">minimal tree automata</a>?</p>

CC BY-SA 3.0
2011-04-25T17:54:23.167Z
2011-04-25T17:54:23.167Z
Sylvain
<p>This sounds a little bit like a forest (<a href="http://en.wikipedia.org/wiki/Disjoint-set_data_structure#Disjoint-set_forests" rel="nofollow">disjoint-set forests</a>)...</p>

<p>It amortizes the cost of insertion through a technique called <em>union by rank</em> and the search operation using <em>path compression</em>. I know there's also a <a href="http://research.microsoft.com/en-us/um/people/crusso/ml2007/slides/puf-wml07-slides.pdf" rel="nofollow">persistent</a> 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...</p>

CC BY-SA 3.0
2011-04-23T13:03:30.293Z
2011-04-23T13:03:30.293Z
Rehno Lindeque
<p>In "Purely Functional Data Structures" (1998), Chris Okasaki proposes tries of binary trees using type aggregation (10.3.2). </p>

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

CC BY-SA 3.0
2011-05-10T20:58:03.480Z
2011-05-10T20:58:03.480Z
Raphael
<p>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.</p>

<p>public class Tree {
    String operation;
    Tree[] subtrees;</p>

<pre><code>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;
}
</code></pre>

<p>...
}</p>

<p>Map commonSubExpressions = new HashMap();</p>

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

CC BY-SA 3.0
2011-05-11T13:32:50.090Z
2011-05-11T13:32:50.090Z
Joop Eggen
<p>Tries allow for efficient storage of lists of elements.  The prefixes are shared so it is space efficient.</p>

<p>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.</p>

<p>I would typically store about 500 unbalanced binary trees of height less than 50.</p>

<p><strong>EDIT</strong></p>

<p>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.<br>
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.</p>

<p>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$.</p>

<p>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.</p>

<p>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".</p>

CC BY-SA 3.0
2011-04-22T19:41:51.160Z
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
CC BY-SA 3.0
2011-04-23T01:19:01.293Z
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
CC BY-SA 3.0
2011-04-23T18:47:29.380Z
Take a look at *term indexing*.
starblue
CC BY-SA 3.0
2011-04-26T16:00:13.790Z
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.
<ds.data-structures><tree><model-checking>
A data structure for sets of trees.
Abdallah
# A data structure for sets of trees.

(Asked by: username_0 on 2011-04-21)

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".

**Tags:** ds.data-structures, tree, model-checking
> **Comments:**
> **username_1**: 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.  
> **username_2**: 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.  
> **username_3**: Take a look at *term indexing*.  
> **username_4**: 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).  

---

## 6 answers

### Answer by username_5 on 2011-04-30. Score: 5 | Accepted answer

You might want to check out [g-tries](http://portal.acm.org/citation.cfm?id=1774422&dl=ACM). 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.)


---

### Answer by username_6 on 2011-04-21. Score: 4

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.

> **Comments:**
> **username_0**: 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.  
> **username_6**: 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.)  

---

### Answer by username_7 on 2011-04-25. Score: 1

What about [minimal tree automata](http://en.wikipedia.org/wiki/Tree_automaton)?


---

### Answer by username_8 on 2011-04-23. Score: 1

This sounds a little bit like a forest ([disjoint-set forests](http://en.wikipedia.org/wiki/Disjoint-set_data_structure#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](http://research.microsoft.com/en-us/um/people/crusso/ml2007/slides/puf-wml07-slides.pdf) 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...


---

### Answer by username_1 on 2011-05-10. Score: 0

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.


---

### Answer by username_9 on 2011-05-11. Score: 0

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


---

