0
$\begingroup$

I have stumbled upon a problem; unfortunately, I do not know the proper terminology to be used which hinders me in thinking about the problem and explaining the problem. I am not even sure this is the right place to ask the question. Let me know if it should be asked somewhere else.

I will explain the problem below but raise the question at this point. Is there any terminology I should be aware of which could clarify the problem below? Is the problem similar to any known problem? Perhaps it already has a name? If not, do you see if there is any part of the description below which is a known problem?

Thanks.

Let $A$ and $B$ both be trees where each node is a set of labels. Let $f$ be a function which given a tree and a node in the tree calculates a value. It is known that the value of an ancestor is the sum of its children.

I am given the values of $f$ for the nodes in $A$. The problem is to compute the values for nodes in $B$.

Let $a$ and $b$ be a node in $A$ and $B$, respectively; we have the following cases: 1. labels($a$) = labels($b$) 2. labels($a$) is a proper subset of labels($b$) 3. labels($b$) is a proper subset of labels($a$) 4. labels($a$) is disjoint of labels($b$)

A node $b$ in case 1 would just have its value set to the value of node $a$.

If an ancestor in $b$ has all its children set, then the ancestor can be calculated by summing the children.

In case 2, we know that node $b$ is at least the value of $a$; if we find nodes in $A$ so that they together are exactly the set of labels in $b$, then we can set $b$ to the sum of these nodes.

In case 3, we could attempt to set the value to $a$, and then hope to find how much we need to deduct. If we can find values for these set of labels: labels($b$) difference labels($a$), then we can deduct the sum of those values and get the value of node $b$.

  • 0
    This reminds me a little bit of some implementations of the [rope data structure](http://en.wikipedia.org/wiki/rope_(data_structure)), where each non-leaf node stores pointers to the left-part and the right-part of the string it represents, and also stores the weight of the "string" it represents (the total of the weight of the left-part and the right-part), and several different ropes can share some of their leaves and (in some cases) a few of their non-leaf nodes.2011-12-10

0 Answers 0