2
$\begingroup$

I have the following tree structure holding sets of values in it:

     Node ({a, b})
     /          \
  Node ({c})   Node ({d, e})
               /            \
           Node ({f, g})    Node({h})

I want to check if e is in the tree - I would need to traverse from parent to children and find the node. I don't necessarily start from the root. I could start from Node({d, e}) and see if there is i in that subtree.

One thing I could do is to change the data structure for every Node to have values from all descendants, so the top one would be:

Node({a, b, c, d, e, f, g, h})

and the right child would be Node({d, e, f, g, h})

I would be trading memory for speed.

Another alternative is I could have a reverse index from value to Nodes that have it or descendants.

Each option has a trade-offs.

My question is: is there some specialized data structures that I am not aware of, that help with this kind of problem? Something dedicated to efficiently answering the query I am looking for.

Improve this question
$\endgroup$
6
  • $\begingroup$ Is the intersection of "the original sets" always empty? $\endgroup$
    – greybeard
    Commented Oct 11 at 6:25
  • $\begingroup$ (State all operations to be supported.) $\endgroup$
    – greybeard
    Commented Oct 11 at 6:31
  • 1
    $\begingroup$ Are there some conditions/limits/relationships on the sets stored in the nodes? like that there is some ordering? (e.g., all elements under a left child are less than all elements under a right child?) $\endgroup$
    – D.W. ♦
    Commented Oct 11 at 7:48
  • $\begingroup$ How does your idea work for a million items? $\endgroup$
    – gnasher729
    Commented Oct 12 at 7:07
  • $\begingroup$ There are no restrictions on the sets. Use of letters might be seem there is some ordering on them, but there isn't. $\endgroup$
    – gruszczy
    Commented Oct 12 at 17:48

3 Answers 3

Reset to default
1
$\begingroup$

If the tree is immutable, you can build an Euler tour. This is basically a depth-first traversal where you write down the times of entering and exiting every node. Call these $in[u]$ and $out[u]$ for every node $u$.

This information gives you $\mathcal{O}(1)$ ancestor queries: Node $u$ is an ancestor of node $v$ if and only if $in[u] < in[v]$ and $out[u] > out[v]$.

Next, as you proposed, build an index from every value to the node it belongs to (assuming the values are indexable or hashable). Then, given a query like „is value $val$ in node $u$”, you can look up the node that $val$ belongs to and check if $u$ is its ancestor.

Improve this answer
$\endgroup$
1
  • $\begingroup$ OK, so this is neat, you are suggesting to break down into two: 1) For value X - which nodes have it 2) For my current node N - is any of the nodes that have X descendant of N $\endgroup$
    – gruszczy
    Commented Oct 12 at 17:54
0
$\begingroup$

Not sure if that helps, but a somewhat related data structure is the PH-tree. Each node can contain up to 2^k entries (data or subnodes), for low "k" that means maximal 4 or 8 entries. Nodes can be stored as arrays or lists.

To find the correct entry, we take, e.g. for the root node, the first "k" bits of the value that we want to look up. If the node is stored as an array, these "k" bits give us directly the array index of the entry (subnode or data). In case of a list, we do a binary search.

As you observed correctly, storing an array can quickly become unreasonable wrt memory consumption. The alternative is to store entries as a list.

Now, there are some variants of implementations, but the original implementation (Java) calculates which representation (array or list) requires less memory and then dynamically changes the representation in a node to optimize for memory consumption.

Note The PH-tree is described as multidimensional index, but the internal concept is independent of that. It is relatively easy to one-dimensional values, such as letters) in the tree.

Disclaimer: the PH-tree is my own work.

Improve this answer
$\endgroup$
0
$\begingroup$

With every node you just store the smallest and largest item in the complete sub tree. Of course your tree must be sorted in some way to make this information useful.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.