algorithm - 式ツリーの評価

Question

アルゴリズムに関する Skiena の本には、次の質問が含まれています。

1) n 個のノードが与えられた場合、O(n) 時間で二分木として与えられた式を評価します。

2) DAG で n ノードと m エッジが与えられた場合、O(n+m) 時間で DAG として与えられた式を評価します。

最初の質問の方法を考えることができました：

evaluate(node) {
     if(node has children){
          left_val = evaluate(node->left);
          right_val = evaluate(node->right);

          // find operation symbol for node and use it as
          // val = left_val operation right_val

          return val;
     }
     else {
          return node_value;
     }
}

各ノードに 1 回アクセスするため、O(n) 時間かかります。

この本には解決策がありませんので、これが正しいかどうか誰か教えてください。

また、誰でも2番目の質問の解決策を提案できますか?

ありがとう。

Answer 1

最初の方法は私にはうまく見えます。

DAGの場合、ツリーを変更して各ノードにキャッシュされた値を追加できる場合は、同じアルゴリズムを少し調整して使用し、オペレーターノードにキャッシュされた値がある場合に再帰しないようにすることができます。これはO（n + m）時間である必要があります（ノードごとに最大1つの算術演算、エッジごとに最大1つのポインタールックアップ）。明示的に：

evaluate(node) {
     if (node has value) {
          return node->value;
     } else {
          left = evaluate(node->left);
          right = evaluate(node->right);

          // find operation symbol for node and use it as
          // val = left_val operation right_val

          node->value = val;
          return val;
     }
}