3

特別な要件を持つAVLツリーに基づいてランクツリーを作成しようとしています。ノードを含むAVLツリーがあり、各ノードに2つのフィールドがあると仮定します。

id, priority

私のAVLツリーはidでソートされており、次の関数もあります。

foo(currentId, delta)

currentIdこの関数によって以下のすべてのIDの優先度を下げると、複雑さO（log n）で機能する必要があるため、私の質問は、ノードをatでdelta ポップできるようにするためにどの追加情報を格納する必要があるかです。highest priority任意の段階with complexity O(1)（fooも使用した後！）。

P.S.右側のサブツリーに最大優先度、左側のサブツリーに最大優先度に関する情報を保存しようとしましたが、その後に多くの変更が必要fooです。O（log n）以上のものが必要になります。木についての良いアイデアや良い本を事前に感謝します。

4

1 に答える 1

1

各サブツリーに表示される最大優先度を格納するのではなく、親pを持つ各ノードcについて、cのサブツリーの最大優先度とpのサブツリーの最大優先度の差をcに格納します。このようにして、O（log n）時間で優先度の範囲を更新し、O（log n）時間で最大優先度の要素を見つけることができます。

于 2011-01-07T02:10:11.550 に答える