Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I am trying to solve a problem of finding a max repetitive sub-tree in an object tree.

By the object tree I mean a tree where each leaf and node has a name. Each leaf has a type and a value of that type associated with that leaf. Each node has a set of leaves / nodes in certain order.

Given an object tree that - we know - has a repetitive sub-tree in it.

By repetitive I mean 2 or more sub-trees that are similar in everything (names/types/order of sub-elements) but the values of leaves. No nodes/leaves can be shared between sub-trees.

Problem is to identify these sub-trees of the max height.

I know that the exhaustive search can do the trick. I am rather looking for more efficient approach.

share|improve this question
add comment

2 Answers

up vote 2 down vote accepted

You can hash your sub-trees: for each node, generate a hash value based on the values of interest (i.e., excluding leaf values) and the hash values of its children, in order.

Use this hash to insert your nodes into an appropriately-sized hash table, and check collisions to determine which are actually repetitive, and which are accidental.

share|improve this answer
    
Hah, exactly what I was going to suggest, but I've not got the algorithm design experience to really back up whether or not this is a good route so I didn't post.. thanks for indirectly validating my idea :) –  Jimmy Hoffa Sep 4 '12 at 19:07
add comment

You could trade off some storage for computation:

On insert check for similarity with parent and if found, copy "similar tree counter" from parent and increment for child. What you do with that is up to you. Either leave it in a tree or a keep a map somewhere indexed on the head of each sub-tree.

At minimum you're only doing n-1 comparisons, not counting whatever accounting you choose to do to keep track of the sub-trees.

share|improve this answer
add comment

Your Answer

 
discard

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.