永続 RBST を撃墜するケース

背景

RBSTはコピー可能は嘘という疑惑 が興味深かったので僕もいろいろ試してみたところ，要素数 $n$ に対してそこそこの確率で木の高さが $n/4$ 程度になるクエリのパターンを見つけました．

テストケース

RBSTはコピー可能は嘘という疑惑 のテストケースに対して，一旦 split してそのまま merge するという一見なんの意味もない操作を付け加えただけです．なんでこれで劇的にバランスが悪くなるのか僕にもわかりません．

int main() {
  RBST<Value> tr; 
  tr = tr.insert(0, 1); //trは1ノード

  srand(time(nullptr)); //このブロックは乱数を適当に消費するためにあります
  int rn = rand() % 10000;
  for (int i = 0; i < rn; i++) {
    int sz = tr.count();
    tr = tr.merge(tr); 
    tr = tr.split(sz).first; //同じものをくっつけて分離するだけの意味のない動作
  }
  cout << tr.count() << endl;
  assert(tr.count() == 1);

  for (int i = 0; i < 20000; i++) {
    int sz = tr.count();
    cout << sz << endl;
    RBST<Value> tr1, tr2;
    tie(tr, ignore) = tr.split(tr.count() / 2 + 1);
    tie(tr1, tr2) = tr.split(tr.count() / 2 + 1); //いったん分離して
    tr = tr1.merge(tr2);  // そのままくっつける
    tr = tr.merge(tr);
    printf("%d\n", tr.max_depth());
  }

  //ここでtrはバランスが崩れまくっている(ことがある)はず
  printf("%d\n", tr.max_depth());
    
  return 0;  
}

可視化

試しに，木のバランスが露骨に悪くなった時の形状を出力してみました．2本の長いパスのいずれかに頂点が集中してしまっている状態のようです．