Loading [Contrib]/a11y/accessibility-menu.js
$\newcommand{\O}{\mathrm{O}}$ My Algorithm : kopricky アルゴリズムライブラリ

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

Treap

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

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

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

コード

  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 提出コード