あけましておめでとうございます。
この記事は traP Advent Calendar 2019 12月21日分のはずだった記事です。大変遅れてしまいました。
1ヶ月ずれた本日投稿させていただきます。申し訳ありませんでした。

3行まとめ

• 赤黒木の代替として 2-3-4木 を使ってみた！
• 動作原理が 単純明快！ねこでもわかる！
• Treapと違って 融合永続 も出来るよ！

イントロ

こんにちは。nari です。競プロでは ID: rickytheta を名乗っています。

まず、この記事の前提として、次の記事を読むことを推奨します:

赤黒木の本質 - Qiita

すなわち、平衡二分探索木である赤黒木は、2-3-4木をシミュレートしたものである、ということが書かれています。
この記事では、その2-3-4木を、競プロ用途(アルゴリズム構成)で使えるように実装します。

先の記事の通り、平衡二分探索木としてよく用いられる赤黒木は、2-3-4木を二分木の形に落とし込んだものです。そのため、赤黒木単体では色変更などの複雑な操作が必要となり、実装もかなり不可解になっています。
パフォーマンス的には二分木であることから赤黒木の方に軍配があがるのかもしれませんが、実装においては 2-3-4木 のほうが比較的明快であることが若干期待できます。

実装の単純さだけで言えばTreapやRandomized Binary Search Treeという有名所がいます。

参考: プログラミングコンテストでのデータ構造 2　～平衡二分探索木編～

これらは平衡二分探索木として十分使える一方で、厳密には融合永続性を持たないという欠点があります。

参考: RBSTはコピー可能は嘘 - よすぽの日記
参考: 永続 RBST を撃墜するケース | mitaki28.info blog

そのため、永続的なmergeが必要となる場面においては、AVL木や赤黒木を用いる必要がありました。
2-3-4木は本質的には赤黒木と等価で、融合永続性を持ちます。よって、より単純明快な実装によって、永続赤黒木などの役割を代替する可能性を秘めています。

ということで、この記事では基本的な操作が行える、出来るだけシンプルな2-3-4木の実装をします。
以下が目的です。

• 2-3-4木を理解する
• 2-3-4木の実装が単純であることを確認する
• 実際に競プロの問題に適用してみる

なお、実装がシンプルだと嬉しい場面としてICPC等のライブラリコピペが不可能な大会が挙げられます。が、ICPCでここまでのものを要求された記憶が無いです……あと赤黒木でいいです……

2-3-4 木の概要

2-3-4 木とは次のような木構造です。

• 各内点は 2,3,4 個の子ノードを持つ。
  • それぞれ 2-ノード、3-ノード、4-ノードと呼ぶ。
• 全ての葉ノードは同じ高さにある。
  • 言い換えると、根ノードから全ての葉ノードまでの最短距離が等しい。

二分木ではないという特徴を持ちますが、代わりに全ての葉までの距離が等しいという制約を持ちます。これにより木の高さが葉の数 $n$ に対して必ず ${\log }_{2}n$ 以下になります。

2-3-4 木で列を管理する場合、葉ノードに値を格納することで列を表現します。内点(のキー)に値を持たせようとすると merge/split の実装に erase が必要になる(と思う)のと、多くの merge/split ベースの赤黒木も同様に葉ノードのみに値を持たせている実装が多いためです。

ちなみに 2-3-4 木について調べると、内点のキーに値を持たせる実装もよく出てきます。insert/erase のみを行う 2-3-4 木の場合はどうしても erase で回転に相当する操作が必要になり、実装難度に差がほとんど無いためだと思われます。

4-ノード の分割

2-3-4 木の基本的な操作として、4-ノード の分割というものがあります。
4-ノード には新しく子を追加できないため、4-ノード を分割して 2-ノード に変換することで子を追加できるようになります。

4-ノード が根である場合と根でない場合の2通りがあり、それぞれ以下の図のようになります。

それぞれ、4-ノード を2つの 2-ノード に分割し、その上の階層の子を増やす、ということで対処しています。
根の場合は高さが1増えて新しい根が出来、根以外の場合は親から新しく子へのリンクを増やします。この時、親は 4-ノード でないという仮定が必要なため、根から再帰的に分割処理を行う必要があります。

2-3-4 木のmerge

マージする 2-3-4 木を、左を L、右を R とします。

L の高さと R の高さが等しい場合、新しく 2-ノード を用意して、その子を L と R にしてあげればよいです。

L の高さが R の高さより大きい場合を考えます(逆も同様です)。
まず、L の根が 4-ノード なら、分割操作を行って 4-ノード を消します。
L の高さが R の高さよりちょうど 1 大きいなら、L の根の一番右の子に R を挿入すればよいです(∵根は 4-ノード ではない)。
そうでないならば、そのような位置まで L の根から最右の子をたどり続けます。この時、途中で出てくる 4-ノード は全て分割して 4-ノード でなくします。そうすることで、最終的に適切に R を挿入できるポイントが見つかります。

計算量は $O(|L\text{の高さ}|-|R\text{の高さ}|)$ です。
この手続きは左端/右端への merge でなくても、ある位置への(高さの低い)木の挿入としても同様に可能なため、merge/split を利用した insert を実装する代わりに、merge を拡張することでも対応ができます。

2-3-4 木のsplit

ここまで来たら簡単で、再帰的に split してあげて merge すればよいです。

図示をすると、まず再帰的に関数呼び出しをすることで以下のように分けます。

これらを順番に merge すれば求まります。

再帰関数で出てきた順番に merge をしてあげると、merge の計算量が $O(|L\text{の高さ}|-|R\text{の高さ}|)$ であることから、全体の計算量は $O(\log n)$ を達成します^[要出典]。

実装

以下の問題を対象に実装しました。

CODE FESTIVAL 2014 エキシビション B - カッコつけ

区間加算と区間minと挿入/削除が要求される問題です。
提出: https://atcoder.jp/contests/code-festival-2014-exhibition/submissions/9651701

2012年 日本情報オリンピック春合宿OJ copypaste - コピー＆ペースト

問題文はこちら: https://www.ioi-jp.org/camp/2012/2012-sp-tasks/2012-sp-day4.pdf
永続merge/splitが要求される問題です。

区間更新(遅延伝播)を削って、オブジェクトプールを用意して、適宜文字列に戻して再構成する、という実装にするとACです。11sec/17sec、454MB/512MB なのでかなりシビア。
提出: https://atcoder.jp/contests/joisc2012/submissions/9654662

これを雑に std::shared_ptr にすると3ケースTLEです。
提出: https://atcoder.jp/contests/joisc2012/submissions/9654701

まとめ

普通に merge/split ベースの赤黒木でいいと思いました。

4-ノードの分割という操作と、子の数が2～4で可変という点が意外と実装時に嵩み、また各ノードが最大4つの子を持つことから各ノードのメモリサイズも大きくなってしまい、実装コストもパフォーマンスも赤黒木とトントンもしくは悪いみたいな感じになりました……

もう少し切り詰めるなら、ポインタ(64bit)の代わりにプール配列の添字(32bit)を持たせてメモリサイズを削減したり、4-ノードの分割を4-ノードが生成された瞬間に行うようにして2-3木にしたり、等の工夫が出来ると思います。

ただ、赤黒木の元ではあるのでこれが赤黒木の理解に繋がる可能性はあるし、実装自体も不可解な点が少なくて分かりやすい……というメリットはあると思います。
一応 4-ノード の分割さえ覚えていれば、何も見ずとも実装できそうなシンプルさなので、無人島で突然融合永続平衡木が必要になったら思い出してあげてください。