Processing math: 100%
My Algorithm : kopricky アルゴリズムライブラリ

kopricky アルゴリズムライブラリ

Treap

コードについての説明(個人的メモ)

Treap は平衡二分探索木の一種で randomness によってその平衡性を保っている.
各ノードはキーおよび優先度を保持しており, 管理する木はキーについて二分探索木の性質を、優先度については(最大値)ヒープ木の性質を満たした構造となっている. 各ノードの優先度については例えば [0, 1] 上の一様分布を独立同分布とすることが多い(以下の実装は異なる).
ちなみに名前の由来は "Tree + Heap" のようだ.
自分の経験的には RBST や Splay Tree よりも速く動作することが多い.
元論文は "Randomized Search Trees" [Aragon, Seidel 1989]

時間計算量: 要素数を n としたとき insert, find, erase O(logn) (期待計算量)

コード

  1. template<typename _Key> class TreapNode {
  2. public:
  3.     const _Key key;
  4.     const unsigned int priority;
  5.     TreapNode *left, *right;
  6.     TreapNode(const _Key& _key) : key(_key), priority(xor128()), left(nullptr), right(nullptr){}
  7.     static unsigned int xor128(){
  8.         static unsigned int x = 123456789, y = 362436069, z = 521288629, w = 86675123;
  9.         unsigned int t = (x ^ (x << 11));
  10.         x = y, y = z, z = w;
  11.         return (w = (w ^ (w >> 19)) ^ (t ^ ( t >> 8)));
  12.     }
  13. };
  14.  
  15. // [-inf, key) [key, +inf)
  16. template<typename _Key>
  17. pair<TreapNode<_Key>*, TreapNode<_Key>*> split(TreapNode<_Key> *cur, const _Key& key){
  18.     if(!cur) return {nullptr, nullptr};
  19.     pair<TreapNode<_Key>*, TreapNode<_Key>*> res;
  20.     if(key <= cur->key){
  21.         res = split(cur->left, key), cur->left = res.second;
  22.         return {res.first, cur};
  23.     }else{
  24.         res = split(cur->right, key), cur->right = res.first;
  25.         return {cur, res.second};
  26.     }
  27. }
  28.  
  29. template<typename _Key>
  30. bool find(TreapNode<_Key> *cur, const _Key& key){
  31.     while(cur){
  32.         if(cur->key == key) return true;
  33.         cur = (key < cur->key ? cur->left : cur->right);
  34.     }
  35.     return false;
  36. }
  37.  
  38. template<typename _Key>
  39. TreapNode<_Key> *insert(TreapNode<_Key> *cur, TreapNode<_Key> *new_node){
  40.     if(!cur) return new_node;
  41.     if(cur->priority < new_node->priority){
  42.         pair<TreapNode<_Key>*, TreapNode<_Key>*> res = split(cur, new_node->key);
  43.         new_node->left = res.first, new_node->right = res.second;
  44.         return new_node;
  45.     }else if(new_node->key < cur->key){
  46.         cur->left = insert(cur->left, new_node);
  47.     }else{
  48.         cur->right = insert(cur->right, new_node);
  49.     }
  50.     return cur;
  51. }
  52.  
  53. template<typename _Key>
  54. TreapNode<_Key> *join(TreapNode<_Key> *left, TreapNode<_Key> *right){
  55.     if(!left || !right) return (left ? left : right);
  56.     if(left->priority < right->priority){
  57.         return right->left = join(left, right->left), right;
  58.     }else{
  59.         return left->right = join(left->right, right), left;
  60.     }
  61. }
  62.  
  63. template<typename _Key>
  64. pair<TreapNode<_Key>*, bool> erase(TreapNode<_Key> *cur, const _Key& key){
  65.     if(!cur) return make_pair(cur, false);
  66.     if(cur->key == key){
  67.         TreapNode<_Key> *res = join(cur->left, cur->right);
  68.         delete cur;
  69.         return make_pair(res, true);
  70.     }else if(key < cur->key){
  71.         pair<TreapNode<_Key>*, bool> res = erase(cur->left, key);
  72.         cur->left = res.first;
  73.         return make_pair(cur, res.second);
  74.     }else{
  75.         pair<TreapNode<_Key>*, bool> res = erase(cur->right, key);
  76.         cur->right = res.first;
  77.         return make_pair(cur, res.second);
  78.     }
  79. }

verify 用の問題

AOJ : Set: Delete 提出コード