Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have a data structure described as following:

- It's a collection of trees.
- Each tree has the same structure.
- Each tree has information of diferent nature.

A example of this data structure:

    4 - - - - - - - 'a' - - - - - - - 3.5 
   / \              / \               / \
  3   1           'f' 'y'           1.0 3.1
     / \              / \               / \
    4   7           'e' 'f'           2.3 7.7

If you see, ignoring the contents of each tree, each of them is just the same tree (the same hierarchy, the same structure). The first contains natural numbers, the second one, characters, and the third one, floating numbers.

The idea of this data structure is that diferent classes (in a C++ program for example) explore diferent "layers" of this tree, in order to each class uses only the information this class needs, ignoring the remaining information. In other words, each class sees only one tree.

Does this data structure match with a hypertree or can it be reformulated/adapted to a hypertree? Or just they are isomorphic trees put together is a same data structure?

share|cite|improve this question

migrated from Dec 16 '12 at 19:51

This question came from our site for theoretical computer scientists and researchers in related fields.

No, this is not a hypertree. You have parallel trees (see parallel arrays). – Tyson Williams Dec 11 '12 at 13:43

You can describe what's going on here with the notion of a functor, extending things which you would do naturally with three different types (ints, chars, and floats) to trees over these types.

What you have is in effect only a single tree, e.g. $$ T = \left\{\mspace{45mu}\begin{array}{c@{}c@{}c} & (4,a\mspace{-18mu}&,3.5) \\ &/&\backslash \\ &\mspace{-60mu}(3,f,1.0) & (1,y\mspace{-36mu}&,3.1) \\ & & /&\backslash \\ & &\mspace{-60mu}(4,e,2.3) & (7,f,7.7)\mspace{-60mu} \end{array}\mspace{50mu}\right\} $$ and mappings from this tree over tuples, to the trees which are visible by the classes, $$ A = \left\{\mspace{-10mu}\begin{array}{c} 4 \\ \;/ \;\;\backslash & \\ \;3 \quad 1 \\ \;~ \quad\; / \;\; \backslash \\ \;~ \quad\;4 \quad7 \end{array}\mspace{-10mu}\right\}, \qquad B = \left\{\mspace{-10mu}\begin{array}{c} a \\ \;/ \;\backslash & \\ \,f \quad y \\ \,~ \quad\; / \;\; \backslash \\ \,~ \quad\;e \quad f \end{array}\mspace{-10mu}\right\}, \qquad C = \left\{\mspace{-20mu}\begin{array}{c} 3.5 \\ \,/ \;\;\backslash & \\ \;1.0 \quad 3.1 \\ \;~ \quad\;\;\;\; / \;\; \backslash \\ \;~ \quad\;\;\;\; 2.3 \quad 7.7 \end{array}\mspace{-10mu}\right\}. $$ The mappings which carry $T \mapsto A$, $T \mapsto B$, and $T \mapsto C$ can be desribed in terms of the projectors $$\begin{align*} \pi_1 \;\;:\;\; \text{int} \times \text{char} \times \text{float} &\to\;\; \text{int} \;, \\ \pi_2 \;\;:\;\; \text{int} \times \text{char} \times \text{float} &\to\;\; \text{char} \;, \\ \pi_3 \;\;:\;\; \text{int} \times \text{char} \times \text{float} &\to\;\; \text{float} \;. \end{align*}$$ Each of these "projector" maps $\pi_j$ can be extended to a mapping on trees, using the tree functor which carries all functions $f: A \to B$ to functions on trees, $\text{Tree}(f) : \text{Tree}(A) \to \text{Tree}(B)$ in the obvious way, preserving the tree structure for any given tree, and applying the function $f$ to each node in the tree. Thus $$\begin{align*} A &= \Bigl[\text{Tree}(\pi_1)\Bigr](T), \\ B &= \Bigl[\text{Tree}(\pi_2)\Bigr](T), \\ C &= \Bigl[\text{Tree}(\pi_3)\Bigr](T). \end{align*}$$ So these trees are just the images of $T$ under projection maps in the natural way; they aren't meaningfully independent of one another, and what the classes do which can only access one of these trees is that they can only access information about $T$ through these projections.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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