4

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)時間を作成します。

もっと良い方法はありますか?

4

1 に答える 1

6

サブツリーのサイズを格納するために AVL ツリーを拡張することは、メジアン クエリを最適化する必要がある場合、一般的にここでの最良のアプローチです。O(log n) の時間がかかりますが、これはかなり高速です。

中央値を何度も計算する場合は、拡張ツリーを使用し、中央値をキャッシュして O(1) で読み取ることができる可能性があります。挿入または削除を行うたびに、時間 O(log n) で中央値を再計算する必要がある場合があります。これにより処理が少し遅くなりますが、漸近コストには影響しません。

もう 1 つのオプションは、ツリー内のノードを介して双方向リンク リストをスレッド化することです。これにより、一定時間内にノードから後続ノードまたは先行ノードに移動できます。これを行うと、中央の要素へのポインターを格納し、挿入または削除時に、ポインターを必要に応じて左または右に移動できます。中央値自体を削除すると、ポインタを左右に​​移動できます。これは拡張を必要とせず、少し高速になる可能性がありますが、各ノードに 2 つのポインターが追加されます。

お役に立てれば!

于 2014-05-22T18:08:21.137 に答える