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?

  • 6
    $\begingroup$ No, this is not a hypertree. You have parallel trees (see parallel arrays). $\endgroup$ 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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