Figuring a max repetitive sub-tree in an object tree

Posted by bonomo on Programmers See other posts from Programmers or by bonomo
Published on 2012-09-04T14:38:37Z Indexed on 2012/09/04 15:52 UTC
Read the original article Hit count: 420

Filed under:

algorithms

|

trees

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.

© Programmers or respective owner

Related posts about algorithms

Finding a problem in some task [closed]

as seen on Programmers - Search for 'Programmers'
Recently I competed in nation wide programming contest finals. Not unexpectedly all problems were algorithmic. I lost (40 points out of 600. Winner got ~300). I know why I lost very well - I don't know how to find actual problem in those obfuscated tasks which are life-blood of every competition.… >>> More
Genetic algorithms

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm trying to implement a genetic algorithm that will calculate the minimum of the Rastrigin functon and I'm having some issues. I need to represent the chromosome as a binary string and as the Rastrigin's function takes a list of numbers as a parameter, how can decode the chromosome to a list of… >>> More
understanding evaluation function

as seen on Programmers - Search for 'Programmers'
I am developing a chess program. And have made use of an alpha beta algorithm and a static evaluation function. I have successfully implemented both but I want to improve the evaluation function by automatically tuning the weights assigned to its features. At this point am totally confused about the… >>> More
How to know whether to create a general system or to hack a solution

as seen on Programmers - Search for 'Programmers'
I'm new to coding , learning it since last year actually. One of my worst habits is the following: Often I'm trying to create a solution that is too big , too complex and doesn't achieve what needs to be achieved, when a hacky kludge can make the fit. One last example was the following (see paste… >>> More
How to implement a genetic algorithm with distance, time, and cost

as seen on Programmers - Search for 'Programmers'
I want to make a solution to find the optimum route of school visit. For example, I want to visit 5 schools (A, B, C, D, E) in my city. Then I must find out what school I should visit first, then the second, then the third etc. with distance, time, and cost criteria. The problem is, I am confused… >>> More

Related posts about trees

Paged binary trees vs. AVL trees and B-trees

as seen on Stack Overflow - Search for 'Stack Overflow'
How are paged binary trees different from AVL trees and B-trees? >>> More
Minimum and maximum height of binary search trees, 2-3-4 trees and B trees.

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, note this is not homework. But can anyone tell me how you find the min/max height of B trees, 2-3-4 trees and binary search trees? Thanks >>> More
Difference between B Trees and 2-3-4 Trees

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, Could someone please explain to me the difference between B Trees and 2-3-4 Trees? And also how would you find the maximum and minimum height of each? Thanks >>> More
B- trees, B+ trees difference

as seen on Stack Overflow - Search for 'Stack Overflow'
In a B- tree you can store both keys and data in the internal/leaf nodes. But in a B+ tree you have to store the data in the leaf nodes only. Is there any advantage of doing the above in a B+ tree? Why not use B- trees instead of B+ trees everywhere? As intuitively they seem much faster. I mean why… >>> More
What is the usage of Splay Trees in the real world?

as seen on Programmers - Search for 'Programmers'
I decided to learn about balanced search trees, so I picked 2-3-4 and splay trees. What are the examples of splay trees usage in the real world? In this Cornell: http://www.cs.cornell.edu/courses/cs3110/2009fa/recitations/rec-splay.html I read that splay trees are 'A good example is a network router'… >>> More