0

In linux system.

If I have two binary trees, tree A has millions of nodes, while tree B has only a few hundred nodes.

I want to check if B is a subtree of A.

One solution I am thinking is, say, A uses 50Mb of the memory, and the addresses are contiguous, while B uses 1Kb. If B is part of A, the addresses of B would be a subset of A's addresses (I guess?).

So can I use tree A’s memory address range and B’s memory address range to determine if B is a subtree of A?

UPDATE: I think if we are using static memory allocation, and there is one node that refers to the same pointer as the root of B refers to, probably when we find that node, we can determine B is a subtree of A.

user4394476
  • 65
  • 2
  • 10
  • I dont get the question. Maybe some clarification. – user3344003 May 31 '15 at 20:24
  • @user3344003Just modified, please tell me if it is still ambiguous to you :p – user4394476 May 31 '15 at 20:36
  • Are A and B in the address space of a single process? – user3344003 May 31 '15 at 20:42
  • @user3344003 If they are in different processes, then there is no need to do this check I think? So let's assume they are in the same process. – user4394476 May 31 '15 at 20:49
  • It's not safe to assume anything about the memory addresses of the contents of these trees. Each node that was provided by the memory allocator could have come from anywhere, such a previously deleted bit of memory from elsewhere. I think you need to walk tree A looking for B, then once you find it, walk both trees in lockstep and confirm that every child in B has the same child in A. – Ron Kuper Jun 01 '15 at 01:18
  • @RonKuper What I am saying is to define some constraints to see if the 'memory address' strategy possible under the certain circumstance. – user4394476 Jun 01 '15 at 12:15

1 Answers1

0

You cannot use the memory addresses of A and B to check for the equality of A and B.

An alternative is to generate a hash of the B tree. Then do a depth first traversal of A, generating the hash of the subtrees of A. If the hash of a subtree of A matches the hash of B, then verify that B matches that particular A subtree.

See this for generating a hash from a tree.

Community
  • 1
  • 1
Craig S. Anderson
  • 6,966
  • 4
  • 33
  • 46