4

以下は、 Stack を使用せずに二分探索木を順番にトラバースする反復アルゴリズムです (first left child、次にparent、finally )。right child

（アイデア：全体のアイデアは、ツリーの一番左の子を見つけ、手元にあるノードの後継者を毎回見つけて、ノードがなくなるまでその値を出力することです。）

void In-Order-Traverse(Node root){
     Min-Tree(root); //finding left-most child
     Node current = root;
  while (current != null){
     print-on-screen(current.key);
     current = Successor(current);
  }
  return;
}

Node Min-Tree(Node root){ // find the leftmost child
   Node current = root;
   while (current.leftChild != null)
      current = current.leftChild;
   return current;
}

Node Successor(Node root){
  if (root.rightChild != null) // if root has a right child ,find the leftmost child of the right sub-tree
    return Min-Tree(root.rightChild);
  else{
    current = root;
    while (current.parent != null && current.parent.leftChild != current)
        current = current.parent;
    return current.parrent;
  }
}

このアルゴリズムの時間計算量は、BST にノードTheta(n)があることを前提としていると主張されていますがn、これは確かに正しいです。ただし、一部のノードは、サブツリー内のノードの数に依存する一定の回数を超えてトラバースされ、これらすべての訪問回数を合計しても時間の複雑さにはならないので、納得できません。Theta(n)

それを証明する方法についてのアイデアや直感はありますか?

4

3 に答える 3

4

ノードよりもエッジで推論する方が簡単です。Successor関数のコードに基づいて推論しましょう。

ケース1（then分岐）

右の子を持つすべてのノードについて、右のサブツリーに 1 回アクセスし (「右折」エッジ)、Min-Tree関数を使用して常に左のサブツリーにアクセスします (「左折」エッジ)。このようなトラバーサルは、エッジが一意であるパスを作成することを証明できます。トラバーサルにより、「右折」エッジに決してアクセスしないことが保証されるため、右の子を持つ他のノードから行われたトラバーサルではエッジが繰り返されません。ツリー上の他のノード。（構造による証明）。

ケース 2 (else分岐)

右の子 (ブランチ) を持たないすべてのノードについて、else「左折」エッジを作成するか、バイナリ ツリーのルートに遭遇するまで、「右折」エッジをたどって先祖にアクセスします。繰り返しになりますが、生成されたパスのエッジは一意であり、適切な子を持たない他のノードから作成された他のトラバーサルでは決して繰り返されません。それの訳は：

  • 開始ノードと次の「左折」エッジによって到達されるノードを除いて、その間にある他のすべてのノードには右の子があります (つまり、それらはelse分岐から除外されます)。もちろん、開始ノードには正しい子がありません。
  • 各ノードには一意の親があり (ルート ノードのみが親を持たない)、親へのパスは「左折」または「右折」のいずれかです (ノードは左の子または右の子です)。任意のノード (右の子条件を無視) が与えられた場合、パターンを作成するパスは 1 つだけです。多くの「右折」と「左折」です。
  • 間にあるノードには正しい子があるため、異なるノードから始まる 2 つのトラバーサルでエッジが現れる方法はありません。(現在、適切な子のないノードを検討しているため)。

(ここでの証明はかなり手を振っていますが、矛盾によって形式的に証明できると思います)。

エッジは一意であるため、ケース 1 のみ (またはケース 2 のみ) で横断されるエッジの総数は O(n) になります (ツリー内のエッジの数は頂点の数 - 1 に等しいため)。したがって、2 つのケースを合計すると、In-Order Traversal は O(n) になります。

各エッジが最大で 1 回しか訪問されていないことがわかっていることに注意してください。証明からすべてのエッジが訪問されたかどうかはわかりませんが、エッジの数は頂点の数によって制限されます。これはちょうどいいです。

これも Omega(n) (各ノードが 1 回訪問される) であることは容易にわかるため、Theta(n) であると結論付けることができます。

于 2013-04-19T02:45:39.673 に答える
0

ノードではなくエッジに注目します。（この写真をより直感的に見てください：http://i.stack.imgur.com/WlK5O.png）

このアルゴリズムでは、すべてのエッジが最大で 2 回訪問されると主張します (実際には、正確に 2 回訪問されます)。

1 回目は下方向にトラバースし、2 回目は上方向にトラバースします。エッジに 2 回以上アクセスするには、そのエッジを再び下方向にトラバースする必要があります: 下、上、下、....

エッジを 2 回下向きに訪問することは不可能であることを証明します。

を下方向に 2 回トラバースするとします。これはedge (u , v)、 の祖先の 1 つが のu子孫である後継者を持つことを意味しuます。

これは不可能です ：

上向きのエッジをトラバースするとき、次のエッジを見つけるために左折エッジを探していることを知っていますu。 (後続を見つけるために) 後続の右側に移動するuと、再び到達するため、edge (u,v)再び到達することは不可能です。(後継者を見つけるには、右または上に移動しますが、左には移動しません)

于 2013-04-19T16:02:38.040 に答える