AVLツリーがある場合、それから中央値を取得するための最良の方法は何ですか？中央値は、ソートされたリストでインデックスceil（n / 2）（インデックスは1から始まります）を持つ要素として定義されます。
したがって、リストが
1 3 5 7 8
中央値は5です。リストが
1 3 5 7 8 10
中央値は5です。
ツリーを拡張できる場合は、各ノードにサブツリーのサイズ（ノード数）を知らせるのが最善だと思います（つまり、1 + left.size + right.size）。これを使用すると、インデックスを比較してトラバースできるため、私が考えることができる最善の方法は、中央値検索O（lg n）時間を作成します。
もっと良い方法はありますか？
サブツリーのサイズを格納するために AVL ツリーを拡張することは、メジアン クエリを最適化する必要がある場合、一般的にここでの最良のアプローチです。O(log n) の時間がかかりますが、これはかなり高速です。
中央値を何度も計算する場合は、拡張ツリーを使用し、中央値をキャッシュして O(1) で読み取ることができる可能性があります。挿入または削除を行うたびに、時間 O(log n) で中央値を再計算する必要がある場合があります。これにより処理が少し遅くなりますが、漸近コストには影響しません。
もう 1 つのオプションは、ツリー内のノードを介して双方向リンク リストをスレッド化することです。これにより、一定時間内にノードから後続ノードまたは先行ノードに移動できます。これを行うと、中央の要素へのポインターを格納し、挿入または削除時に、ポインターを必要に応じて左または右に移動できます。中央値自体を削除すると、ポインタを左右に移動できます。これは拡張を必要とせず、少し高速になる可能性がありますが、各ノードに 2 つのポインターが追加されます。
お役に立てれば！