スプレイ木

プログラミング

スプレイ木とは

  • SleatorとTarjanによって紹介
  • 自己調整を行う平衡二分探索木
    • アクセスした頂点がルートにくるように「スプレイ操作」を繰り返し行う
  • 頂点へのアクセスに偏りがある場合に有効(ある頂点によくアクセスするなど)
    • 逆に一様にアクセスする場合は効率が良くない
  • スプレイ操作
    • zig
      • ある頂点xの親頂点p(x)がルートならば、頂点xと親頂点p(x)の辺をつなぎかえる
    • zig-zig
      • 親頂点p(x)がルートでなく、頂点xも親頂点p(x)も左側(または右側)の場合、親頂点p(x)と親頂点p(x)の親頂点g(x)について辺をつなぎかえ、次にxとp(x)について辺をつなぎかえる
    • zig-zag
      • 親頂点p(x)がルートでなく、頂点xが左側の子で親頂点が右側の子(またはその逆)のとき、xとp(x)の辺をつなぎかえ、次にxと新たなp(x)の辺をつなぎかえる

スプレイ木の実装

  • Spaghetti Sourceを少し自分の使いやすいように直した
    • 論文中のsimple top-down splayによる実装
#include <iostream>

template<class T>
class splay_tree {
  //頂点クラス
  struct node {
    T key;
    node *l, *r;
    node(T k, node *l = 0, node *r = 0):key(k), l(l), r(r){ }
  };
  //ルート頂点
  node *root;
  //スプレイ操作(simple top-down splay)
  node* splay(T x, node *t){
    if(!t) return t;
    node N(x);
    node *l = &N, *r = &N;
    node *s;
    while(true){
      if(x < t->key){
        if(t->l && x < t->l->key){
          //rotate right
          s = t->l;
          t->l = s->r;
          s->r = t;
          t = s;
        }
        if(!t->l) break;
        //link right
        r->l = t;
        r = t;
        t = t->l;
      }else if(x > t->key){
        if(t->r && x > t->r->key){
          //rotate left
          s = t->r;
          t->r = s->l;
          s->l = t;
          t = s;
        }
        if(!t->r) break;
        //link left
        l->r = t;
        l = t;
        t = t->r;
      }else break;
    }
    //assemble
    l->r = t->l;
    r->l = t->r;
    t->l = N.r;
    t->r = N.l;
    return t;
  }

  void delete_subtree(node *t){
    if(!t) return;
    delete_subtree(t->l);
    delete_subtree(t->r);
    delete t;
  }
public:
  //検索
  bool find(T x){
    if(!root) return false;
    root = splay(x, root);
    if(x == root->key) return true;
    return false;
  }
  //追加
  void insert(T x){
    if(!root) root = new node(x);
    else{
      root = splay(x, root);
      if(x < root->key){
        node *t = new node(x, root->l, root);
        root->l = 0;
        root = t;
      }else if(x > root->key){
        node *t = new node(x, root, root->r);
        root->r = 0;
        root = t;
      }
    }
  }
  //削除
  void erase(T x){
    if(!find(x)) return;
    if(!root->l){
      root = root->r;
    }else{
      node *t = root->r;
      root = splay(x, root->l);
      root->r = t;
    }
  }

  splay_tree(): root(0){ }
  ~splay_tree(){
    delete_subtree(root);
  }  
};



void print_result(splay_tree<int> &st, int v){
  if(st.find(v)){
    std::cout << v << " find" << std::endl;
  }else{
    std::cout << v << " not find" << std::endl;
  }
}

int main(){
  splay_tree<int> st;

  st.insert(3);
  st.insert(4);
  st.insert(6);
  st.insert(5);
  st.insert(7);
  st.insert(2);

  print_result(st, 1);
  print_result(st, 3);
  print_result(st, 5);
  print_result(st, 7);
  print_result(st, 9);
  
  return 0;
}

参考文献