CODEWITHSUNDEEP
algorithmgraphtime-complexityexpression-trees
bollock1
bollock1

Reputation: 85

Extending a expression tree evaluation algorithm

This is a recursive algorithm that I came up with. I've seen examples of algorithms that are similar to this in books.

f(n)
  if n is an integer
    return n
  else
    l = left child of n
    r = right child of n
    return f(l) n f(r)

1]

It can be used to evaluate expression trees like the one shown on the left in the above image in Θ(n) time. As long as this is all correct, I want to extend it to evaluate expression trees like the one on the right, where common subexpressions are de-duplicated. I think the algorithm can evaluate these types of trees correctly, but I am not sure of the time that it will take. Perhaps some method of storing subtrees should be used? Such as:

f(n, A)
  if n is an integer
    return node
  else
    if n has more than 1 parent AND n is in A (A is a list of stored subtrees)
       return n from A
    else
      l = left child of n
      r = right child of n
      s = f(l, A) n f(r, A)
      add s to list A
      return s

Is this extension correct? It seems really messy. Also I have a feeling it would run in O(n2) time because the function would be called on n nodes and during each call it would have to iterate over a list of stored nodes that has an upper bound of n. Can this be done in better than quadratic time?

Upvotes: 0

Views: 121

Answers (1)

collapsar
collapsar

Reputation: 17238

Processing a DAG should work fine if you store the result of a subgraph evaluation at the operator node upon the first visit. Any subsequent visit of that node would not trigger a recursive call to evaluate the subexpression but simply return the stored value. The technique is called 'memoization'. The run time is basically the number of edges in the graph, assuming all operator evaluations are O(1).

Pseudocode:

f(n)
  if n is an integer
    return n
  else
    if property evalResult of n is defined
       return property evalResult of n
    else
      l = left successor of n
      r = right successor of n
      s = f(l) n f(r)
      set property evalResult of n to s
      return s

Upvotes: 1

Related Questions