13

関連する質問:バイナリ ツリー O(N) のインオーダー ツリー トラバーサルの時間の複雑さ? 、ただし、反復子は O(1) スペースのみの消費を許可しているのに対し、再帰によるトラバーサル (O(log N) スペース内) に基づいています。

C++ では、通常、標準コンテナーのイテレーターをインクリメントすることは O(1) 操作であるという要件があります。ほとんどのコンテナでは自明に証明されていますが、その他のコンテナでmapは少し難しいようです。

  • amapがスキップ リストとして実装されている場合、結果は明らかです。
  • ただし、それらはしばしば赤黒木として (または少なくとも二分探索木として) 実装されます。

そのため、順序通りのトラバーサル中に、「次の」値に簡単に到達できない瞬間があります。たとえば、左のサブツリーの右下の葉を指している場合、次にトラバースするノードはルートであり、数depth歩離れています。

アルゴリズムの複雑さ (「ステップ」の観点から) がO(1)に償却されたことを「証明」しようとしましたが、これは問題ないようです。しかし、私はまだデモンストレーションを行っていません。

これは、深さ 4 のツリーについてトレースした小さな図です。(ノードの場所にある) 数字は、順序どおりのトラバーサル中にそのノードから次のノードに移動するステップの数を表します。

       3
   2       2
 1   1   1   1
1 2 1 3 1 2 1 4

注: これがより大きなツリーのサブツリーである場合、右端の葉のコストは 4 です。

ノードの合計数が 15 の場合、合計は 28 です。したがって、ノードあたりのコストは平均で 2 未満であり、(それが維持されれば) 償却コストとしては優れています。そう：

  • 順序通りのトラバーサル中、バランスの取れた (完全な) 二分探索木に対してイテレータを実際に O(1) インクリメントしていますか?
  • 完全ではない二分探索木をカバーするように結果を拡張できますか?
4

1 に答える 1

12

はい、償却されたコストはO(1)、任意のツリーの反復ごとです。

証明は、各ノードを「訪問」した回数に基づいています。
葉は一度だけ訪れます。なし リーフは最大 3 回訪問されます。

  1. 親からノード自体に移動するとき。
  2. 左のサブツリーから戻るとき
  3. 右のサブツリーから戻るとき

ノードへの訪問はこれ以上ないため、各ノードの訪問数を合計すると、 よりも小さい数が得られる3nため、すべてのノードを合わせた合計訪問数は でありO(n)、O(1)ステップごとに償却されます。

（完全なツリーには n/2 の葉があるため、2n遭遇したものを取得しています。訪問の合計が2nどのツリーよりも小さくなることを示すことができると思いますが、この「最適化」はここでは範囲外ですIMO)。

ステップごとの最悪のケースはO(h)で、これはO(logn)バランスの取れたツリーにありますがO(n)、場合によってはそうなる可能性があります。

PS 赤黒ツリーが C++ でどのように実装されているかはわかりませんが、ツリー データ構造にparent各ノードのフィールドが含まれている場合、再帰スタックを置き換えてO(1)スペースを消費できるようになります。n(このようなフィールドを格納すること自体が「不正行為」であるため、これはもちろん「ごまかし」O(n)です)。

于 2012-10-14T13:12:51.050 に答える