o(logn)のrbtreeでアルゴリズムを見つける
-
19-09-2019 - |
質問
次のアクションでできるデータ構造を見つける必要があります。
- ビルド(s、k)-o(nlogn)
- 検索(s、k)-o(logn)
- insert(s、k)-o(logn)
- delete(s、k)-o(logn)
- Decrawes -upto(s、k、d)-o(logn) - この方法は、<= kです。
明らかな最初の選択はredblacktreeでした。
ただし、O(logn)のDecrase-uptoに関する解決策には至ることはできません。 kがツリーの最大キーよりも大きい場合はどうなりますか?その場合、ツリー全体を更新する必要があります。
誰かがそうでなければ提案できますか?多分いくつかのヒント?
解決
ツリーの各ノードに追加の値を保存できます。デルタと呼びましょう。すべての子孫に保存されたキーにノードのデルタを追加して、実際のキーを取得します。したがって、特定のノードでキーの実際の値を取得するには、すべてのデルタをルートからそのノードに合計し、この合計を保存されたキーに追加します。
やる Decrease-Upto
, 、ルートから1つのパスでO(log n)ノードのデルタを変更するだけです。
この操作後にツリーの構造を変更する必要はありません。キーの順序付けが変更されないためです。
所属していません StackOverflow