math - ツリー トラバーサル メソッドのビッグ O 表記

Question

ツリー構造内のすべてのノード (事前順トラバーサル) がすべての祖先ノードにも触れなければならないメソッドの実行時の複雑さはどれくらいですか? O(n * avg(木の高さ))? つまり、メソッド/関数の実行時の複雑さは O(n * avg(tree-height)) ですか? （平均的な場合）。

avg(tree-height) は (min + max) / 2 として定義できるかもしれませんが、

Answer 1

誤解しているかもしれませんが、すべてのノード (n) を通過し、ノードごとに各祖先に触れる必要があると言っている場合 (最悪の場合: バランスの取れたバイナリ ツリーで n をログに記録する)、それはO(n*Log(n)). 定数は Big O 表記には適用されませんが、(以下の @interjay が指摘したように) 平均は適用される可能性があります。

アンバランスなツリーを想定すると、すべての先祖に触れる最悪のケースは約n/2であり、これは大きな O のちょうど n です。