2

私が読んでいる論文は、

関数を計算するための線形時間アルゴリズムがあることは簡単にわかります。l()

ここでl()、一番左の子を指定します (入力と出力の両方がツリーの後順トラバーサルになります)。ただし、ツリー内のノードの数が単純なO(n^2)実装しか考えられません。n

例として、次のツリーを考えてみましょう。

  a
 / \
c   b

ポストオーダー トラバーサルでは、ツリーはc b a. 対応する関数l()は を与えるはずc b cです。

これが時間内の私の実装O(n^2)です。

public Object[] computeFunctionL(){
    ArrayList<String> l= new ArrayList<String>();
    l= l(this, l);
    return l.toArray();
}

private ArrayList<String> l(Node currentRoot, ArrayList<String> l){
    for (int i= 0; i < currentRoot.children.size(); i++){
        l= l(currentRoot.children.get(i), l);
    }
    while(currentRoot.children.size() != 0){
        currentRoot= currentRoot.children.get(0);
    }
    l.add(currentRoot.label);
    return l;
}

ツリーは次のように作成されます。

public class Node {
private String label;
private ArrayList<Node> children= new ArrayList<Node>();
...
4

3 に答える 3

1

ノードごとに O(1) 時間でこの情報を計算できる単純な再帰アルゴリズムがあります。合計ノード数が n であるため、これは合計 O(n) 時間で実行されます。

基本的な考え方は、次の再帰的な洞察です。

  • 左の子を持たない任意のノード n の場合、l(n) = n です。
  • それ以外の場合、n が子 L を離れた場合、l(n) = l(L) になります。

これにより、各ノードにその l 値で注釈を付けるこの再帰アルゴリズムが生じます。

function computeL(node n) {
   if n is null, return.

   computeL(n.left)
   computeL(n.right)

   if n has no left child:
      set n.l = n
   else
      set n.l = n.left.l

お役に立てれば！

于 2013-11-08T23:49:59.297 に答える