2020年1月21日 | ブログ記事

2-3-4木を実装する

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


3行まとめ

イントロ

こんにちは。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木の実装をします。
以下が目的です。

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

2-3-4 木の概要

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

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

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通りがあり、それぞれ以下の図のようになります。

IMG_0017

それぞれ、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 を挿入できるポイントが見つかります。

IMG_0018

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

2-3-4 木のsplit

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

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

IMG_0019

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

再帰関数で出てきた順番に merge をしてあげると、merge の計算量が であることから、全体の計算量は を達成します[要出典]

実装

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

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-ノード の分割さえ覚えていれば、何も見ずとも実装できそうなシンプルさなので、無人島で突然融合永続平衡木が必要になったら思い出してあげてください。

この記事を書いた人
nari

競プロ(C++) / CTF(Crypto/PPC) / ゲーム作成(C++/Java/JavaScript) 参加プロジェクト: Traps of Typing(プログラマ) / Polar Snow Fantasy(プログラマ)

この記事をシェア

このエントリーをはてなブックマークに追加
共有

関連する記事

2018年12月12日
多重スリーブの世界と,各種進捗報告。
Silviase
2018年12月16日
ICPCアジア地区横浜大会参加記【アドベントカレンダー2018 52日目】
eiya
2018年12月3日
ハル研究所プログラミングコンテスト 2018に参加しました[アドベントカレンダー2018 40日目]
ninja
2019年3月16日
競技プログラミングを始めよう【新歓ブログリレー2019 8日目】
eiya
2018年10月30日
競プロだけでは習得しづらいJava Stream API 【アドベントカレンダー 6日目】
mikit
2018年3月6日
ICPC World Finals 2018にninjaribatonが出場します!
nari
記事一覧 タグ一覧 Google アナリティクスについて