Ultimate, God-like Algorithm

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

.

Relevant Pages

  • LOS Optimization Using Binary Tree Structures (with demo)
    ... fast way to calculate LOS using a binary tree (properly called a binary ... describe the visibility-dependency between tiles - as in describing ... Using octants ... The cool thing about using a relational-based LOS algorithm is that you ...
    (rec.games.roguelike.development)
  • Re: How come Ada isnt more popular?
    ... beneficial for the memory-management aspect of such an algorithm. ... When the GC hits it just traverses the tree ... E.g a chess playing program (any ... Furthermore generational garbage collection AFAIK has ...
    (comp.lang.ada)
  • Re: Question about decision tree algorithm in sqlserver2000
    ... If your target, on the other hand, is continuous, the algorithm will build regression trees that have regression formulae in nodes and leaves. ... if your target is continuous (i.e. a regression tree) than the lift chart is replaced by a scatter plot ...
    (microsoft.public.sqlserver.datamining)
  • Re: Question about decision tree algorithm in sqlserver2000
    ... if my target is discrete, the algorithm will ... build a classification tree. ... if your target is continuous (i.e. a regression tree) than the lift chart is replaced by a scatter plot ...
    (microsoft.public.sqlserver.datamining)
  • Comparing 2 Infinite Trees
    ... An infinite tree is described by including "self references" in place ... self reference makes the tree infinite. ... believe that I have an algorithm that can show equality in m * n time. ...
    (sci.math)
Loading