平衡二分木を使う問題 - よすぽの日記

平衡二分木は、定数倍は遅いしコード長がアホみたいに長くなりますがとても強力なデータ構造です。
そんな平衡二分木を使う事が最近多いので、使った問題を紹介します。

RBST
軽実装かつコピー可能な(追記:不可能です。)プロコンなら最強感のある木
とりあえずコレを書いておけば困る事はあんまり無さそう
実装、解説はiwiwi大先生のスライドが良かった
プログラミングコンテストでのデータ構造 2 ～平衡二分探索木編～

AA Tree or LLRB Tree(Left Leaning Red Black Tree)
insert/eraseだけの実装なら簡単
merge/splitの実装は面倒
reverseの実装は闇
insert/eraseの定数倍はRBSTより速い、僕の実装では

Red Black Tree
実装は面倒だけど、reverseに関してだけはAA Treeよりも簡単だと思う。書いたことはないしこれからもなさそう

Splay Tree
実装は軽い　再アクセスが高速　Link-Cut Treeに使用　コピーは厳しい
これも強い木
永続化とコピーは出来るのかなぁ
実装はqnighyさんのスライドとコードが非常に良かった
スライド
http://www.ioi-jp.org/camp/2013/2013-sp-tasks/2013-sp-day4-spaceships-review.pdf
コード
http://www.ioi-jp.org/camp/2013/2013-sp-tasks/2013-sp-day4-spaceships-sample2.cpp

基本的にSplay操作さえ実装してしまえば色んな事(merge,split,insert,delete)が出来るため強い。

Link-Cut Tree
上のqnighyさんのスライドとiwiwi大先生のスライドが大変素晴らしい
プログラミングコンテストでのデータ構造 2 ～動的木編～