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

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

Scapegoat Tree

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

Scapegoat Tree は平衡二分探索木の一種で insert, erase, find の操作をならし $\O (\log n)$ で行うことのできるデータ構造である.
構造は非常に簡単であり, ざっくり言うとあるノードの深さがある程度深くなったらその頂点を含む偏った部分木が存在することが言え, その部分木全体を最適な平衡二分探索木になるように構築し直すことで平衡性を保とうという方法である.
再構築にかかる最悪計算量は要素数について線形であるが, そのような再構築が起こる回数はよく抑えることができ, 結局各操作をならし $\O(\log n)$ で行えることが言える.
元論文は "Scapegoat Trees" [Galpcrin, Rivest 1993]

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

コード

  1. template<typename _Key> class ScapegoatTree {
  2. private:
  3.     struct node {
  4.         const _Key key;
  5.         unsigned int size;
  6.         node *left, *right;
  7.         node(const _Key& _key) : key(_key), size(1), left(nullptr), right(nullptr){}
  8.         void eval(){
  9.             size = 1;
  10.             if(left) size += left->size;
  11.             if(right) size += right->size;
  12.         }
  13.     };
  14.     bool find(const node *cur, const _Key& key) const {
  15.         while(cur){
  16.             if(cur->key == key) return true;
  17.             cur = (key < cur->key ? cur->left : cur->right);
  18.         }
  19.         return false;
  20.     }
  21.     void subtree_dfs(node *cur, vector<node*>& euler_tour) const {
  22.         if(cur->left) subtree_dfs(cur->left, euler_tour);
  23.         euler_tour.push_back(cur);
  24.         if(cur->right) subtree_dfs(cur->right, euler_tour);
  25.     }
  26.     node *build_pbbt_rec(const int l, const int r, const vector<node*>& euler_tour){
  27.         if(r - l == 0) return nullptr;
  28.         else if(r - l == 1){
  29.             node * const cur = euler_tour[l];
  30.             cur->left = cur->right = nullptr;
  31.             return cur->eval(), cur;
  32.         }
  33.         const int mid = (l + r) / 2;
  34.         node * const cur = euler_tour[mid];
  35.         cur->left = build_pbbt_rec(l, mid, euler_tour);
  36.         cur->right = build_pbbt_rec(mid + 1, r, euler_tour);
  37.         return cur->eval(), cur;
  38.     }
  39.     node *build_perfect_balanced_binary_tree(node *cur){
  40.         if(!cur) return nullptr;
  41.         vector<node*> euler_tour;
  42.         subtree_dfs(cur, euler_tour);
  43.         return build_pbbt_rec(0, (int)euler_tour.size(), euler_tour);
  44.     }
  45.     node *insert(node *cur, node *new_node, int depth, bool& balanced){
  46.         if(!cur){
  47.             balanced = (depth <= floor(log_val * log2(max_element_size)));
  48.             return new_node;
  49.         }else if(cur->key <= new_node->key){
  50.             cur->right = insert(cur->right, new_node, depth + 1, balanced);
  51.             cur->eval();
  52.             if(balanced || cur->right->size <= alpha * cur->size) return cur;
  53.         }else{
  54.             cur->left = insert(cur->left, new_node, depth + 1, balanced);
  55.             cur->eval();
  56.             if(balanced || cur->left->size <= alpha * cur->size) return cur;
  57.         }
  58.         balanced = true;
  59.         return build_perfect_balanced_binary_tree(cur);
  60.     }
  61.     node *join(node *left, node *right){
  62.         if(!left || !right) return left ? left : right;
  63.         else if(left->size < right->size){
  64.             right->left = join(left, right->left);
  65.             return right->eval(), right;
  66.         }else{
  67.             left->right = join(left->right, right);
  68.             return left->eval(), left;
  69.         }
  70.     }
  71.     void check(){
  72.         if(size() >= alpha * max_element_size) return;
  73.         root = build_perfect_balanced_binary_tree(root);
  74.         max_element_size = size();
  75.     }
  76.     pair<node*, bool> erase(node *cur, const _Key& key){
  77.         if(!cur) return {nullptr, false};
  78.         else if(cur->key == key){
  79.             node *res = join(cur->left, cur->right);
  80.             delete cur;
  81.             return {res, true};
  82.         }else if(key < cur->key){
  83.             pair<node*, bool> res = erase(cur->left, key);
  84.             cur->left = res.first;
  85.             return cur->eval(), make_pair(cur, res.second);
  86.         }else{
  87.             pair<node*, bool> res = erase(cur->right, key);
  88.             cur->right = res.first;
  89.             return cur->eval(), make_pair(cur, res.second);
  90.         }
  91.     }
  92.     void clear(node *cur){
  93.         if(cur->left) clear(cur->left);
  94.         if(cur->right) clear(cur->right);
  95.         delete cur;
  96.     }
  97.     node *root;
  98. public:
  99.     const double alpha, log_val;
  100.     size_t max_element_size;
  101.     ScapegoatTree(const double _alpha=2.0/3.0)
  102.         : root(nullptr), alpha(_alpha), log_val(-1.0 / log2(alpha)), max_element_size(0){}
  103.     // ~ScapegoatTree(){ if(root) clear(root); }
  104.     bool empty() const { return !root; }
  105.     size_t size() const { return empty() ? 0 : root->size; }
  106.     bool find(const _Key& key) const { return find(root, key); }
  107.     void insert(const _Key& key){
  108.         max_element_size = max(max_element_size, size() + 1);
  109.         bool balanced = true;
  110.         root = insert(root, new node(key), 0, balanced);
  111.         assert(balanced);
  112.     }
  113.     bool erase(const _Key& key){
  114.         pair<node*, bool> res = erase(root, key);
  115.         root = res.first, check();
  116.         return res.second;
  117.     }
  118. };

verify 用の問題

AOJ : Set: Delete 提出コード
Atcoder : データ構造 提出コード