平衡二分探索木
プログラミングコンテストでのデータ構造 2 ～平衡二分探索木編～ - SlideShare
Treap
、
スプレー木
が実装しやすいらしい…