Rubyによる赤黒木ベースのMap実装です

基本操作

• []=(key, value) - キーに対応する値を設定（キーが存在する場合は上書き）
• [](key) - キーに対応する値を取得（存在しない場合はnil）
• delete(key) - キーに対応する要素を削除し、値を返す（存在しない場合はnil）
• to_h - Hashオブジェクトに変換

要素の一括操作

• merge!(other) - 他のマップの要素を追加（破壊的）
• merge(other) - 他のマップの要素を追加した新しいマップを返す
• clear - すべての要素を削除

状態確認

• size - マップ内の要素数を返す
• empty? - マップが空かどうかを返す
• include?(key) - 指定したキーが存在するかどうかを返す

イテレーション

• each - キーと値のペアを順にイテレート
• keys - すべてのキーを配列で返す
• values - すべての値を配列で返す

境界値検索

• lower_bound(key) - key以上の最小のキーを持つノードを返す
• upper_bound(key) - keyより大きい最小のキーを持つノードを返す
• lower_bound_pair(key) - key以上の最小のキーを持つ[key, value]のペアを返す
• upper_bound_pair(key) - keyより大きい最小のキーを持つ[key, value]のペアを返す

最小値/最大値

• min_key - 最小のキーを返す（空の場合はnil）
• max_key - 最大のキーを返す（空の場合はnil）
• shift - 最小の要素を削除して[key, value]のペアを返す
• pop - 最大の要素を削除して[key, value]のペアを返す

だいたいの操作はO(log n)の時間計算量で動作します（nはマップ内の要素数）。