>>260
二分木である必要は必ずしもないが、規格で決まった計算量の
要求を満たすデータ構造が事実上なんらかのバランス木しかないので、
実際の実装はほとんど全て二分木。B木とかを使う実装もあるかもしれん（知らんけど）

> 登録コストはlog nですか？
> mapエントリ削除、編集のコストはどうですか？
http://www.sgi.com/tech/stl/Map.html