Clever Geek Handbook

Hash for tree structure

How do I define a hash function for a tree structure that only depends on the tree structure and is the same regardless of the node labels?

For example, 2-1-3-4 must have the same hash function as 1-4-2-3 or 4-1-3-2.

+3


source to share


2 answers


Find the center of the tree. Then run the recursive algorithm as such from the center:

recurse(u, p):

    hash = INITH
    vector childrenhash = {}

    for each (u,v) in G:
        if v!=p:
            childrenhash.insert(recurse(v,u))

    childrenhash.sort()

    for elem in childrenhash:
        hash = (hash * (elem xor PR)) % MOD

    return hash


Select appropriate values ​​for INITH

, MOD

and PR

.

Two isomorphic trees will share the same hash.

+2


source


If you throw away the node labels, the rest is the number of children for each node. This way you can just count the number of children for each node and write them all in one line (array, vector, ...).

Example:

   a             2       
  / \           / \      
 b   c    =>   0   2     =>  2,0,2,0,0
    / \           / \
   d   e         0   0

Now, suppose you say the following trees are to be considered equal:



   a              a      
 / | \          / | \    
b  c  d        b  c  d   
  / \  \      / \    |   
 d   e  f    d   e   f

You can add another transformation step to the same idea: sort the children:

    a                 3                   3       
  / | \             / | \               / | \     
 b  c  d     =>    0  2  1      =>     0  1   2     =>  3,0,1,2,0,0,0
   / \  \            / \  \               |  / \   
  d   e  f          0   0  0              0 0   0 


      a                 3                 3        
    / | \             / | \             / | \      
   b  c  d   =>      2  0  1    =>     0  1   2     =>  3,0,1,2,0,0,0
  / \    |          / \    |              |  / \   
 d   e   f         0   0   0              0 0   0

I'll probably follow the idea in @gilleain's link: https://math.stackexchange.com/questions/1604260/algorithm-for-equality-of-trees-of-restricted-depth

+2


source






More articles:


All Articles