最近、二分木に関するこの質問に出くわしました。
任意のバランスの取れていないツリーが与えられた場合、それが単一値 (すべての要素が同じ値) であるかどうかを判断するための big-O は何ですか。
上記の場合、バランスの取れたツリーと線形ツリーのどちらが最悪の複雑さを引き起こしますか?
これは質問に対する私の答えです：
ツリーが単値かどうかを判断するには、各ノードをチェックする必要があります。したがって、複雑さは O(n) です。
ノードの数が同じであれば、線形ツリーでもバランス ツリーでも、同じ数の比較が行われます。したがって、複雑さは同じになります。
これは正しいです？
任意の二分木が与えられた場合、最悪の場合、すべてのノードを検査して、それらが同じ値を持つかどうかを判断する必要があります。ここで使用できる単純な敵対的引数があります。ツリー内の個別の値の間に関係がないため、アルゴリズムがすべての値を調べない場合、敵対者は n - 1 個の値がすべて同じであるツリーを提供する可能性があります。最後の値を確認しなかった場合、敵対者は、その値をアルゴリズムの指示とは逆に設定することで、アルゴリズムを誤ったものにする可能性があります。
一方、二分探索木について話している場合、時間 O(h) でこれを解くことができます。ここで、h は木の高さです。具体的には、最初と最後の値を見て、それらが同じかどうかを確認してください。その場合、ツリー内のすべての中間値は同じでなければなりません。そうでない場合は、2 つの異なる値を確認したことになります。これは、完全にバランスの取れたツリーでは時間 O(log n) で実行され、縮退リンク リストでは O(n) で実行されます。これは、一般的なバイナリ ツリーのケースよりも興味深い質問であるため (少なくとも、私の意見では)、元の質問が求めていたものだったのではないかと思います。
お役に立てれば！