週刊 spaghetti_source

Shuffle Tree

10:59

Shuffle Treeは「確率的・自己組織化平衡二分探索木」です．Splay Tree, Scapegoat Tree, Treap の知識があると理解しやすいかもしれません．

テクニカルレポート [Patel 2009] が2009年に公開されていますが，仕事自体（＝提案）は2002年だそうです．なかなか面白いので是非論文誌などに出して欲しいのですが，経過を見るに，期待は薄そうです．

• [Patel 2009] M. Patel: A randomized self-adjusting binary search tree, technical report, http://www.clockandflame.com/media/ShuffleTree_Aug2009.pdf, 2009.

内容

二分探索木で挿入・削除・検索などを行う際には上から再帰的な探索を行いますが，Shuffle Treeではその際に「深い」ノードを見つけたら，その部分を「再平衡化」します（cf. Scapegoat Tree: rebuiliding）．

深いノードの条件は，基本的には「深さが log n を超えたら」ですが，乱択化しておきます．探索開始ノードで c = [0, n] の乱数を発生させ，降りるたびに c = (c-1)/n と更新， c = 0 以降のノードは「深い」と判定して，「再平衡化」の対象にします．※きちんと確認していませんが，多分期待値 O(n) の乱数を生成して log(n) で消化すれば同等の結果になるはずです．

ここで，c = 0 とか c = n にすれば乱択にしなくてもいいんじゃないかと思うかもしれませんが，それぞれ以下の問題があってダメで，乱択化することに真に意味があります．

• 毎回 c = n とすると浅いところに log n サイズのパス構造ができたとき解消されずに残る
• 毎回 c = 0 とすると劣化版 Splay Tree （二段回転なし）になるが．これはかなり遅い

再平衡化の手法は，木の回転操作に基づきます．あるノードから再帰的に左（or 右）に探索した後に，その方向のノードを上に持ち上げるように二分探索木の回転を行います．たとえば普通の2分探索木の挿入は

  insert(u, key) =
    if !u: return new Node(key)
    b = u.key < key
    u.ch[b] = insert(u.ch[b], key)
    return u

と実装できますが，Shuffle Treeでは，これを

  insert(u, key, c) =
    if !u: return new Node(key)
    b = u.key < key
    u.ch[b] = insert(u.ch[b], key, (c-1)/2)
    return rotate(u, b, c)

と書き換えます．ここで rotate(u, b, c) は c = 0 かつ回転可能のときにのみ u.ch[b] を上に持ち上げる木の回転操作です．

元の論文には「木を探索する一般的な関数 traverse を書いて，挿入・削除・検索全部の操作を traverse で実装するのだ」と書いてありますが，使いやすい traverse が思いつかなかったので，以下の実装では，上のように，それぞれを書き換えています（※実測したところ，検索は回転しないほうが早かったので，非回転にしています）．使いやすい traverse がかけた方は，教えてくれると嬉しいです．

パフォーマンスなど

• 実装量は Treap (insert-remove) より10行ほど長い
• 全体的に，挿入は Treap より少し遅い
• 全体的に，検索・削除は Treap より少し早い
• ソート例では Splay Tree 一回り遅い
• ランダム例では Splay Tree より一回り早い

実装量がTreapより長いのは，むしろTreapが異常です．Shuffle Treeの実装量は非平衡の二分探索木実装量＋回転実装量なので，これを下回るほうが凄いのです．

その他面白い点としては，ノードに全く平衡性情報を覚えさせなくて良い点があります（cf. 赤黒木：色情報, Treap：優先度）．これはSplay Treeの自己組織化性と同じ性質です．得意なデータも Splay Tree とおなじく「局所性のあるデータ（近いデータへのアクセス頻度が高い）」ですが，Shuffle Tree のほうが全体としてパフォーマンスのバラつきが少ない傾向にあります．

実装例

template <class T>
struct ShuffleTree {
  struct Node {
    T key;
    Node *ch[2];
    Node(T key) : key(key) { ch[0] = ch[1] = 0; }
  } *root;
  int size;
  ShuffleTree() : root(0), size(0) { }

  Node *rotate(Node *n, int b, int c) {
    Node *m = n->ch[b];
    if (c > 0 || !m) return n;
    n->ch[b] = m->ch[!b];
    m->ch[!b] = n;
    return m;
  }
  void insert(T key) { root = insert(root, key, rand() % (1 + size++)); }
  Node *insert(Node *n, T key, int c) {
    if (!n) return new Node(key);
    int b = (n->key < key);
    n->ch[b] = insert(n->ch[b], key, (c-1)/2);
    return rotate(n, b, c);
  }
  Node* removeMin(Node *n, T &value) {
    if (!n->ch[0]) { value = n->key; return n->ch[1]; }
    n->ch[0] = removeMin(n->ch[0], value);
    return n;
  }
  void remove(T key) { root = remove(root, key, rand() % (1 + size--)); }
  Node *remove(Node *n, T key, int c) {
    if (!n) return n;
    if (n->key == key) {
      if (!n->ch[1]) return n->ch[0];
      n->ch[1] = removeMin(n->ch[1], n->key); 
      return n;
    }
    int b = (n->key < key);
    n->ch[b] = remove(n->ch[b], key, (c-1)/2);
    return rotate(n, b, c);
  }
  Node *find(T key) { return find(root, key); }
  Node *find(Node *n, T key) {
    if (!n || n->key == key) return n;
    return find(n->ch[n->key < key], key);
  }
};