19
$\begingroup$

Consider unlabeled, rooted binary trees. We can compress such trees: whenever there are pointers to subtrees $T$ and $T'$ with $T = T'$ (interpreting $=$ as structural equality), we store (w.l.o.g.) $T$ and replace all pointers to $T'$ with pointers to $T$. See uli's answer for an example.

Give an algorithm that takes a tree in the above sense as input and computes the (minimal) number of nodes that remain after compression. The algorithm should run in time $\cal{O}(n\log n)$ (in the uniform cost model) with $n$ the number of nodes in the input.

This has been an exam question and I have not been able to come up with a nice solution, nor have I seen one.

$\endgroup$
  • $\begingroup$ And what is “the cost”, “the time”, the elementary operation here? The number of nodes visited? The number of edges traversed? And how is the size of the input specified? $\endgroup$ – uli Mar 9 '12 at 18:11
  • $\begingroup$ This tree compression is an instance of hash consing. Not sure if that leads to a generic counting method. $\endgroup$ – Gilles Mar 9 '12 at 20:35
  • $\begingroup$ @uli I clarified what $n$ is. I think "time" is specific enough, though. In non-concurrent settings, this is equivalent to counting operations which is in Landau terms equivalent to counting the elementary operation occuring most often. $\endgroup$ – Raphael Mar 10 '12 at 11:14
  • $\begingroup$ @Raphael Of course I can take a guess what the intended elementary operation should be and will probably pick the same as everybody else. But, and I know I am pedantic here, whenever “time bounds” are given it is important to state what is being counted. Is it swaps, compares, additions, memory accesses, inspected nodes, traversed edges, you name it. It is like omitting the unit of measurement in physics. Is it $10\,\mathrm{kg}$ or $10\,\mathrm{ms}$? And I suppose memory accesses are almost always the most frequent operation. $\endgroup$ – uli Mar 10 '12 at 11:44
  • $\begingroup$ @uli These are the sort of details that “uniform cost model” is supposed to convey. It's painful to define precisely what operations are elementary, but in 99.99% of cases (including this one) there's no ambiguity. Complexity classes fundamentally do not have units, they do not measure the time it takes to perform one instance but the way this time varies as the input gets larger. $\endgroup$ – Gilles Mar 10 '12 at 14:07
10
$\begingroup$

Yes, you can perform this compression in $O(n \log n)$ time, but it is not easy :) We first make some observations and then present the algorithm. We assume the tree is initially not compressed - this is not really needed but makes analysis easier.

Firstly, we characterize 'structural equality' inductively. Let $T$ and $T'$ be two (sub)trees. If $T$ and $T'$ are both the null trees (having no vertices at all), they are structurally equivalent. If $T$ and $T'$ are both not null trees, then they are structurally equivalent iff their left children are structurally equivalent and their right children are structurally equivalent. 'Structural equivalence' is the minimal fixed point over these definitions.

For example, any two leaf nodes are structurally equivalent, as they both have the null trees as both their children, which are structurally equivalent.

As it is rather annoying to say 'their left children are structurally equivalent and so are their right children', we will often say 'their children are structurally equivalent' and intend the same. Also note we sometimes say 'this vertex' when we mean 'the subtree rooted at this vertex'.

The above definition immediately gives us a hint how to perform the compression: if we know the structural equivalence of all subtrees with depth at most $d$, then we can easily compute the structural equivalence of the subtrees with depth $d+1$. We do have to do this computation in a smart way to avoid a $O(n^2)$ running time.

The algorithm will assign identifiers to every vertex during its execution. An identifier is a number in the set $\{ 1, 2, 3, \dots, n \}$. Identifiers are unique and never change: we therefore assume we set some (global) variable to 1 at the start of the algorithm, and every time we assign an identifier to some vertex, we assign the current value of that variable to the vertex and increment the value of that variable.

We first transform the input tree into (at most $n$) lists containing vertices of equal depth, together with a pointer to their parent. This is easily done in $O(n)$ time.

We first compress all the leaves (we can find these leaves in the list with vertices of depth 0) into a single vertex. We assign this vertex an identifier. Compression of two vertices is done by redirecting the parent of either vertex to point to the other vertex instead.

We make two observations: firstly, any vertex has children of strictly smaller depth, and secondly, if we have performed compression on all vertices of depth smaller than $d$ (and have given them identifiers), then two vertices of depth $d$ are structurally equivalent and can be compressed iff the identifiers of their children coincide. This last observation follows from the following argument: two vertices are structurally equivalent iff their children are structurally equivalent, and after compression this means their pointers are pointing to the same children, which in turn means the identifiers of their children are equal.

We iterate through all the lists with nodes of equal depth from small depth to large depth. For every level we create a list of integer pairs, where every pair corresponds to the identifiers of the children of some vertex on that level. We have that two vertices in that level are structurally equivalent iff their corresponding integer pairs are equal. Using lexicographic ordering, we can sort these and obtain the sets of integer pairs that are equal. We compress these sets to single vertices as above and give them identifiers.

The above observations prove that this approach works and results in the compressed tree. The total running time is $O(n)$ plus the time needed to sort the lists we create. As the total number of integer pairs we create is $n$, this gives us that the total running time is $O(n \log n)$, as required. Counting how many nodes we have left at the end of the procedure is trivial (just look at how many identifiers we have handed out).

$\endgroup$
  • $\begingroup$ I haven't read your answer in detail, but I think you've more or less reinvented hash consing, with a weird problem-specific way of looking up nodes. $\endgroup$ – Gilles Mar 10 '12 at 2:56
  • $\begingroup$ @Alex “children of strictly smaller degree” degree should probably be depth? And despite CS-trees growing downward I find “height of a tree” less confusing than “depth of a tree”. $\endgroup$ – uli Mar 10 '12 at 3:40
  • $\begingroup$ Nice answer. I feel like there should be a way to get around sorting. My second comment on @Gilles answer is valid here, too. $\endgroup$ – Raphael Mar 10 '12 at 11:10
  • $\begingroup$ @uli: yup, you're right, I've corrected it (not sure why I confused those two words). Height and depth are two subtly different concepts, and I needed the latter :) I thought I'd stick to the conventional 'depth' rather than confuse everyone by swapping them. $\endgroup$ – Alex ten Brink Mar 10 '12 at 11:39
4
$\begingroup$

Compressing a non-mutable data structure so that it does not duplicate any structurally equal subterm is known as hash consing. This is an important technique in memory management in functional programming. Hash consing is a sort of systematic memoization for data structures.

We're going to hash-cons the tree and count the nodes after hash consing. Hash consing a data structure of size $n$ can always be done in $O(n\:\mathrm{lg}(n))$ operations; counting the number of nodes at the end is linear in the number of nodes.

I will consider trees as having the following structure (written here in Haskell syntax):

data Tree = Leaf
          | Node Tree Tree

For each constructor, we need to maintain a mapping from its possible arguments to the result of applying the constructor to these arguments. Leaves are trivial. For nodes, we maintain a finite partial map $\mathtt{nodes} : T \times T \to N$ where $T$ is the set of tree identifiers and $N$ is the set of node identifiers; $T = N \uplus \{\ell\}$ where $\ell$ is the sole leaf identifier. (In concrete terms, an identifier is a pointer to a memory block.)

We can use a logarithmic-time data structure for nodes, such as a balanced binary search tree. Below I'll call lookup nodes the operation that looks up a key in the nodes data structure, and insert nodes the operation that adds a value under a fresh key and returns that key.

Now we traverse the tree and add the nodes as we go along. Although I'm writing in Haskell-like pseudocode, I'll treat nodes as a global mutable variable; we'll only ever be adding to it, but the insertions need to be threaded throughout. The add function recurses on a tree, adding its subtrees to the nodes map, and returns the identifier of the root.

insert (p1,p2) =
add Leaf = $\ell$
add (Node t1 t2) =
    let p1 = add t1
    let p2 = add t2
    case lookup nodes (p1,p2) of
      Nothing -> insert nodes (p1,p2)
      Just p -> p

The number of insert calls, which is also the final size of the nodes data structure, is the number of nodes after maximum compression. (Add one for the empty tree if needed.)

$\endgroup$
  • $\begingroup$ Can you give a reference for "Hash consing a data structure of size $n$ can always be done in $O(nlg(n))$ operations"? Note that you will need balanced trees for nodes in order to achieve the desired runtime. $\endgroup$ – Raphael Mar 10 '12 at 11:02
  • $\begingroup$ I was only considering hashing substructures to numbers in a structured way so that independently computing the hash for the same tree would always yield the same result. Your solution is fine, too, provided we have mutable datastructures on our hands. I think it can be cleaned up a tad, though; the interleaving of insert and add should be made explicit and a function that actually solves the problem should be given, imho. $\endgroup$ – Raphael Mar 10 '12 at 11:03
  • 1
    $\begingroup$ @Raphael Hash consing relies on a finite map structure over tuples of pointers/identifiers, you can implement that with logarithmic time for lookup and add (e.g. with a balanced binary search tree). My solution does not require mutability; I make nodes a mutable variable for convenience, but you can thread it throughout. I'm not going to give full code, this is not SO. $\endgroup$ – Gilles Mar 10 '12 at 14:02
  • 1
    $\begingroup$ @Raphael Hashing structures, as opposed to assigning them arbitrary numbers, is a bit dodgy. In the uniform cost model, you can encode anything into a large integer and do constant-time operations on it, which is not realistic. In the real world, you can use cryptographic hashes to have a de facto one-to-one mapping from infinite sets to a finite range of integers, but they're slow. If you use a non-crypto checksum as the hash, you need to think about collisions. $\endgroup$ – Gilles Mar 10 '12 at 14:10
3
$\begingroup$

Here is another idea that aims at (injectively) encoding the structure of trees into numbers, rather than just labelling them arbitrarily. For that, we use that any number's prime factorisation is unique.

For our purposes, let $E$ denote an empty position in the tree, and $N(l,r)$ a node with left subtree $l$ and right subtree $r$. $N(E,E)$ would be a leaf. Now, let

$\qquad \displaystyle \begin{align*} f(E) &= 0 \\ f(N(l,r)) &= 2^{f(l)}\cdot 3^{f(r)} \end{align*}$

Using $f$, we can compute the set of all subtrees contained in a tree bottom-up; in every node, we merge the sets of encodings obtained from the children and add a new number (which can be computed in constant time from the children's encodings).

This last assumption is a stretch on real machines; in this case, one would prefer to use something similar to Cantor's pairing function instead of exponentiation.

The runtime of this algorithm depends on the structure of the tree (on balanced trees, $\cal{O}(n \log n)$ with any set implementation that allows union in linear time). For general trees, we would need logarithmic time union with a simple analysis. Maybe a sophisticated analysis can help, though; note that the usual worst-case tree, the linear list, admits $\cal{O}(n \log n)$ time here, so it is not so clear what the worst-case may be.

$\endgroup$
1
$\begingroup$

As pictures are not allowed in comments:

enter image description here

top left: an input tree

top right: the subtrees rooted in nodes 5 and 7 are isomorphic too.

lower left and right: the compressed trees are not uniquely defined.

Note that in this case the size of the tree has gone down from $7+5|T|$ too $6+|T|$.

$\endgroup$
  • $\begingroup$ This is indeed an example of the desired operation, thanks. Note that your final examples are identical if you do not distinguish between original and added references. $\endgroup$ – Raphael Mar 10 '12 at 10:59
-1
$\begingroup$

Edit: I read the question as T and T′ were children of the same parent. I took the definition of compression to be recursive as well, meaning you could compress two previously compressed subtrees. If that's not the actual question, then my answer may not work.

$O(n \log n)$ begs for a $T(n) = 2T(n/2) + cn$ divide and conquer solution. Recursively compress nodes and compute the number of descendants in each subtree after compression. Here's some python-esque pseudo code.

def Comp(T):
   if T == null:
     return 0
   leftCount = Comp(T.left)
   rightCount = Comp(T.right)
   if leftCount == rightCount:
     if hasSameStructure(T.left, T.right):
       T.right = T.left
       return leftCount + 1
     else
       return leftCount + rightCount + 1    

Where hasSameStructure() is a function that compares two already compressed subtrees in linear time to see if they have the exact same structure. Writing a linear time recursive function that traverses each and checks if the one subtree has a left child every time the other one does etc. shouldn't be hard.

Let $n_\ell$ and $n_r$ be the sizes of the left and right subtrees respectively (after compression). Then the running time is $$ T(n) = T(n_1) + T(n_2) + O(1) \mbox{ if $n_\ell \neq n_r$} $$ and $$ 2T(n/2) + O(n) \mbox{ otherwise} $$

$\endgroup$
  • $\begingroup$ What if the subtrees are not siblings? Care for ((T1,T1),(T2,T1)) T1 can be saved twice by using a pointer two the third occurence. $\endgroup$ – uli Mar 9 '12 at 20:01
  • $\begingroup$ @uli I'm not sure what you're saying. I read the question as $T$ and $T'$ were children of the same parent. If that's not the actual question, then my answer may not work. I took the definition of compression to be recursive as well, meaning you could compress two previously compressed subtrees. $\endgroup$ – Joe Mar 9 '12 at 20:28
  • $\begingroup$ The questions merly states that two subtress are identified as isomorphic. Nothing is said about them having the same parent. If a subtree T1 appears three times in a tree, as in my previous example ((T1,T1),(T1,T2)) two occurences can be compressed by pointing to the third orccurence. $\endgroup$ – uli Mar 9 '12 at 20:35

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.