私は1つの講義スライドを持っています： AVLツリーの中間要素を見つけるために、私はそれがmoddile要素に到達するまで要素を順番にトラバースします。それはO（N）を要する。AVLツリーを使用して中間要素を見つけるランタイム
私が正しく知っているのであれば、木構造では、AVLは常に2つの子に分かれているバイナリツリーなので、found要素はbase 2 O（logn）をとります。
しかし、なぜO（N）と表示されますか？
2人の子供に分かれていても完全な対称性は保証されません。たとえば、バランスの取れたバイナリツリーの中で最も不均衡なものを考えてみましょう。それぞれの右の子は、対応する左の子よりも深さが1です。 は、ツリーでは、中央の要素はあなたが、その後N/2番目に大きいノードを見つけ、あなたが持っているNどのように多くのノードを決定する必要があり
...どこかで右下の枝の左枝の中になります。これは、（ログN）プロセスではありません。
検討中のツリーはAVLツリーなので、スキューされたツリー構造はO（n）の場合ではないと仮定しません。数字（キー）値がわからないことについての説明が要因になることがあります。中間の要素について確かめるために、n/2の数を（順番に）カウントします。 – arunk2
私はちょうど 'Aを詳しく説明しようとしています。マシュレーギのコメント。
考慮中のツリーはAVLツリーなので、O（log n）の要素の保証された検出結果は、検索する要素（キー）と同じようにログとして保持されます。
問題は、指定されたデータ構造内の中間要素を識別しようとしていることです。それはAVLツリー（自己バランスBST）であるため、オーダートラベルで要素を昇順で取得できます。このプロパティを使用して、中央の要素を探したいとします。
アルゴリズムは次のようになります。 - すべてのノードが順序どおりにトラバースされ、@ n/2番目の位置に戻ります。これはO（n/2）、したがって全体の複雑さO（n）に合計される。
中間要素の値を知っていればO（log n）が必要ですが、中間要素は手前では分かっていないので、ツリー内の最小要素を（n/2 - 1）次の要素は中間の要素になります。 –