Treap は平衡二分探索木の一種で randomness によってその平衡性を保っている.
各ノードはキーおよび優先度を保持しており, 管理する木はキーについて二分探索木の性質を、優先度については(最大値)ヒープ木の性質を満たした構造となっている.
各ノードの優先度については例えば [0, 1] 上の一様分布を独立同分布とすることが多い(以下の実装は異なる).
ちなみに名前の由来は "Tree + Heap" のようだ.
自分の経験的には RBST や Splay Tree よりも速く動作することが多い.
元論文は "Randomized Search Trees" [Aragon, Seidel 1989]
時間計算量: 要素数を $n$ としたとき insert, find, erase $\O (\log n)$ (期待計算量)
- template<typename _Key> class TreapNode {
- public:
- const _Key key;
- const unsigned int priority;
- TreapNode *left, *right;
- TreapNode(const _Key& _key) : key(_key), priority(xor128()), left(nullptr), right(nullptr){}
- static unsigned int xor128(){
- static unsigned int x = 123456789, y = 362436069, z = 521288629, w = 86675123;
- unsigned int t = (x ^ (x << 11));
- x = y, y = z, z = w;
- return (w = (w ^ (w >> 19)) ^ (t ^ ( t >> 8)));
- }
- };
- // [-inf, key) [key, +inf)
- template<typename _Key>
- pair<TreapNode<_Key>*, TreapNode<_Key>*> split(TreapNode<_Key> *cur, const _Key& key){
- if(!cur) return {nullptr, nullptr};
- pair<TreapNode<_Key>*, TreapNode<_Key>*> res;
- if(key <= cur->key){
- res = split(cur->left, key), cur->left = res.second;
- return {res.first, cur};
- }else{
- res = split(cur->right, key), cur->right = res.first;
- return {cur, res.second};
- }
- }
- template<typename _Key>
- bool find(TreapNode<_Key> *cur, const _Key& key){
- while(cur){
- if(cur->key == key) return true;
- cur = (key < cur->key ? cur->left : cur->right);
- }
- return false;
- }
- template<typename _Key>
- TreapNode<_Key> *insert(TreapNode<_Key> *cur, TreapNode<_Key> *new_node){
- if(!cur) return new_node;
- if(cur->priority < new_node->priority){
- pair<TreapNode<_Key>*, TreapNode<_Key>*> res = split(cur, new_node->key);
- new_node->left = res.first, new_node->right = res.second;
- return new_node;
- }else if(new_node->key < cur->key){
- cur->left = insert(cur->left, new_node);
- }else{
- cur->right = insert(cur->right, new_node);
- }
- return cur;
- }
- template<typename _Key>
- TreapNode<_Key> *join(TreapNode<_Key> *left, TreapNode<_Key> *right){
- if(!left || !right) return (left ? left : right);
- if(left->priority < right->priority){
- return right->left = join(left, right->left), right;
- }else{
- return left->right = join(left->right, right), left;
- }
- }
- template<typename _Key>
- pair<TreapNode<_Key>*, bool> erase(TreapNode<_Key> *cur, const _Key& key){
- if(!cur) return make_pair(cur, false);
- if(cur->key == key){
- TreapNode<_Key> *res = join(cur->left, cur->right);
- delete cur;
- return make_pair(res, true);
- }else if(key < cur->key){
- pair<TreapNode<_Key>*, bool> res = erase(cur->left, key);
- cur->left = res.first;
- return make_pair(cur, res.second);
- }else{
- pair<TreapNode<_Key>*, bool> res = erase(cur->right, key);
- cur->right = res.first;
- return make_pair(cur, res.second);
- }
- }
AOJ : Set: Delete 提出コード