0

この順序付けられたシーケンスを表す平衡二分探索木があるとします。

A<B<C<D<E<F<G<H

要素の1つ、たとえばFが与えられた場合、結果がこの順序付けられたシーケンスを表すように、ツリーを効率的に変換するにはどうすればよいですか？

F<G<H<A<B<C<D<E?

Fから右への要素は、他のすべての要素の前に移動されました。これは、通常の意味での「木の回転」とは何の関係もないことに注意してください。ここでの回転は、要素の順序という意味で発生します。これは、二重リンクリストの「ローテーション」の意味と同じです。たとえば、問題が二重にリンクされたリストに関するものであり、バイナリ検索ツリーに関するものではない場合、解決策は簡単です。

E.next := null
F.prev := null
H.next := A
A.prev := H

平衡二分探索木のための効率的な解決策はありますか？

実装上の注意：

一見すると、これに効率的なアルゴリズムがあったとしても、移動された要素の値を更新して二分探索木の不変条件を保持する必要があるため、あまり役に立たないように思われるかもしれません（左の子は少ないです） 、右の子の方が大きい）。ただし、これは当てはまりません。Nを法とするモジュラー算術の場合、ノードの値を変更せずに、次数を一定時間で固定できます。ノードの順序が次のように定義されているとします。

(A < B) if and only if ((A.value - C) mod N) < ((B.value - C) mod N)

ここで、A.value、B.value、およびCは、 [0、N）の範囲の整数です。これをグラフィカルに解釈すると、 N個の点が周囲に広がった円があり、 Cが最小点になり、次にC + 1、C + 2など、C +（N-1）までの点が続きます。 、これが最大のポイントです。

とにかく、Fとそれに続くすべての要素を前面に移動した後、 Cを変更することで、ツリーの不変条件を簡単に修正できます。

C := F.value
4

1 に答える 1

2

一般に、これは O(N) 時間未満では実行できません。少しの変更で O(log N) でバランスを取り戻せますが、ブランチ全体を切り取って別の場所に貼り付けるのは大きな変更です。

n 個の要素を抽出して 1 つずつ挿入すると、O(n log N) かかります。n が大きい場合、O(N) 時間で実行できるツリー全体を再構築する価値があります。

とはいえ、順序通りのトラバーサルのシーケンス全体を循環リストとして扱うことができます。「最初」と見なす要素へのポインターを維持し、一部の要素を「最後」から「最初」に、またはその逆に移動する場合は、それを変更するだけです。順番にシーケンスにアクセスしたい場合は、ポイントされた要素 (「最初の」) から開始し、順番にトラバーサルを続け、ツリーの最後をラップします。右端の要素にアクセスしたら、左端に進みます。再び「最初の」要素に到達したら停止します。

于 2013-02-26T06:50:19.223 に答える