Ultimate, God-like Algorithm

osbornc@gmail.com · science forum beginner Joined: 25 Dec 2005 Posts: 21

I desire an algorithm to test two infinitely large, rooted, ordered
trees for equality, where each node of a tree is associated with some
value.

For finite trees, comparison is simple:

Two finite trees A and B are equal iff the values of the root nodes are
equal, the root nodes each have the same number of children, and the
i(th) subtree of the root of A is equal to the i(th) subtree of the
root of B.

An infinite tree is described by including "self references" in place
of some of the leaf nodes. A self reference Y is a reference to a
parent node X, indicating that the subtree rooted at X should be
inserted in place of Y. Since X is a parent of Y, the existence of any
self reference makes the tree infinite. Note that although the tree is
infinite, its description is finite.

Given two infinite tree descriptions M and N, of sizes m and n, I
believe that I have an algorithm that can show equality in m * n time.

It works by labeling all nodes of M from 1...m and all nodes of N from
1...n.
The algorithm then mirrors the algorithm for the finite-tree case, but
when a self-reference is encountered it expands the self-reference.

The algorithm keeps track of which nodes from M it has compared to
nodes in N. That is, if it has compared node 1 in M to node 3 in N, it
remembers the pair (1, 3). When the algorithm is about to compare 1 to
3 again, it knows it has already checked this case and backs off.

Since there are only m * n pairs, there can be at most m * n steps.

The algorithm returns true unless at least one pair fails (that is, the
nodes differ in value or number of children).

I hope this made some bit of sense.

My question is, is this is good algorithm? Is it optimal?

Thanks,
Chris Osborn

Google