Treap(set)

keyword:

カートに追加

overview

Treapとは,次を満たす確率的平衝二分探索木である. - keyについてみると,木は二分探索木になっている. - priority(randomized)についてみると,木はHeapになっている. 実装したTreapは,map(set)のような機能を持つだけ. split/mergeも出来ない. keyはユニーク&これ以上Nodeを追加しないという条件を加えれば区間クエリは書けそう. 例えば『キーがx以下のNodeにyを加算する』は,treap[x]とtreap[x].childlen[0]に対してLazy実装で実現できる.

usage

value_t& Treap::operator[](key_t key)
; keyに対応するvalの参照を得る.無いなら作る.
unique_ptr& Treap::find(key_t key)
; keyに対応するvalのスマートポインタの参照を得る.
; keyに対応するvalが存在しないなら,空のスマートポインタの参照を得る.
void Treap::erase(key_t key)
; keyを削除する.

references

https://www.slideshare.net/iwiwi/2-12188757
http://www.prefield.com/algorithm/container/treap.html

code