バイナリツリートラバーサルの複雑さ

Question

データ構造内のバイナリツリーのインオーダー、ポストオーダー、およびプリオーダートラバーサルの時間の複雑さは何ですか？それはO（n）かO（log n）かO（n^2）か？

Answer 1

O(n)です。これは、各ノードを1回トラバースするためです。むしろ、各ノードの作業量は一定です（残りのノードに依存しません）。

Answer 2

TravesalはどのノードでもO（n）です。なぜなら、あなたは各ノードに一度ヒットしているからです。ルックアップは、ツリーが何らかの整理スキーマ（バイナリ検索ツリー）を持っている場合に、O（n）よりも小さくなる可能性のある場所です。

Answer 3

O（n）と言います。 私はバランスの取れた木のためにやっています、すべての木に適用可能です。

T（N）= 2 * T（N/2）+ 1 ---------->（1）

T（N/2）、あなたが再帰を使用すると仮定すると 右サブツリーではT（n/2）、ベースケースでは「1」である。

簡略化では、（1）あなたはトラバーサル（inorderまたはpreorderまたはpost order）がオーダーO（n）であることを証明できます。

Answer 4

In-Order、Pre-Order、およびPost-Orderトラバーサルは、Depth-Firstトラバーサルです。

グラフの場合、Depth First Traversalの複雑さはO（n + m）です.nはノードの数、mはエッジの数です。

バイナリツリーもグラフなので、ここでも同じことが適用されます。 これらの深さ優先トラバーサルの複雑さはO（n + m）です。

バイナリツリーの場合、ノードから発信できるエッジの数は2に制限されるため、バイナリツリーの最大エッジ数はn-1です。ここでnはノードの総数です。

複雑さはO（n + n-1）になります。これはO（n）です。