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)時間を作成します。
もっと良い方法はありますか?