平衡二分木を使う問題 - よすぽの日記平衡二分木は、定数倍は遅いしコード長がアホみたいに長くなりますがとても強力なデータ構造です。 そんな平衡二分木を使う事が最近多いので、使った問題を紹介します。 木の種類 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よりも簡単だと思
プログラミングコンテストでのデータ構造 2 ～平衡二分探索木編～
Spend Bill Gates' Money
