平衡二分探索木（Balanced BST）は、動的集合操作を効率よく扱うための重要なデータ構造である。特に Treap および Splay 木は、それぞれ異なる戦略で平衡性を保ちながら、挿入・削除・検索などの基本操作を平均 $O(\log n)$ 時間で実現する。

単回転 Treap

Treap（Tree + Heap）は、各ノードにランダムな優先度（priority）を持たせ、二分探索木の性質とヒープの性質を同時に満たすことで平衡性を確率的に保つ。回転操作により、ヒープ条件が破れたときに再調整を行う。

void rotate(int &root, int dir) {
    int child = t[root].son[dir];
    t[root].son[dir] = t[child].son[!dir];
    t[child].son[!dir] = root;
    update(root);
    root = child;
    update(root);
}

挿入時には、通常の BST 通りに降りていき、その後、優先度に基づいて必要に応じて回転を行う。削除時は、対象ノードを葉または片方の子のみを持つ状態まで回転で押し下げ、その後削除する。

非回転 FHQ-Treap

FHQ-Treap（分割併合 Treap）は、回転を使わず、split と merge の二つの操作で木を操作する。これにより、永続化や区間操作への拡張が容易になる。

• split(root, k, L, R): 根が root の木を、値が $k$ 以下とそれより大きい部分に分割し、それぞれ L, R に格納。
• merge(L, R): 優先度に基づき、二つの木をマージ。

void split(int u, int key, int &L, int &R) {
    if (!u) { L = R = 0; return; }
    if (val[u] <= key) {
        L = u;
        split(rs(u), key, rs(u), R);
    } else {
        R = u;
        split(ls(u), key, L, ls(u));
    }
    update(u);
}

int merge(int L, int R) {
    if (!L || !R) return L | R;
    if (prio[L] > prio[R]) {
        rs(L) = merge(rs(L), R);
        update(L); return L;
    } else {
        ls(R) = merge(L, ls(R));
        update(R); return R;
    }
}

この方式では、挿入・削除・順位・k 番目の要素・前駆・後継などの操作がすべて split/merge を組み合わせて実現できる。

二重回転 Splay 木

Splay 木は、アクセスされたノードを根まで持ってくる（splay 操作）ことで、局所的な頻繁なアクセスに対して高速化を図る。splay 操作には zig, zig-zig, zig-zag の三種類があり、zig-zig と zig-zag では二重回転を行うことで平衡性を維持する。

void splay(int x, int goal = 0) {
    while (parent[x] != goal) {
        int y = parent[x], z = parent[y];
        if (z != goal)
            (is_right(x) == is_right(y)) ? rotate(y) : rotate(x);
        rotate(x);
    }
    if (!goal) root = x;
}

Splay 木は、区間操作（例：反転）にも適しており、[l, r] 区間を部分木として切り出すために、l-1 と r+1 を splay して中間部分を操作する手法が一般的である。

応用例

• 普通平衡樹：基本操作の実装比較（Treap / FHQ / Splay）。
• 文芸的平衡樹：区間反転クエリを FHQ-Treap または Splay で処理。遅延伝播フラグにより左右子を入れ替える。
• 二逼平衡樹：セグメント木の各ノードに平衡木を持たせ、区間内の順位・k 番目・前駆・後継を処理。FHQ-Treap を用いた実装が主流。
• 火星人 prefix：文字列のハッシュ値を FHQ-Treap で管理し、LCP（最長共通接頭辞）を二分探索で求める。
• 最長増加部分列（オンライン版）：挿入位置までの最大 DP 値を FHQ-Treap で取得し、新規要素の DP 値を決定。

これらのデータ構造は、問題の性質に応じて使い分けることが重要である。FHQ-Treap はコードの簡潔さと柔軟性に優れ、Splay 木は複雑な区間操作に強い。一方、単回転 Treap は理解の入り口として適しているが、実用性はやや劣る。