java - TreeMultimapを使用したceiling（）

Question

• GoogleのグアバからTreeMultimapを拡張して、キングオッドceiling関数を取得することは可能ですか？ceiling(key)指定されたキーよりも大きい最小のキーを返します。（順序集合ビューを取得して見ているだけでよいことはわかっていますが、バランスの取れた二分探索木が提供するような、時間計算量がより複雑なものを好みます）
• 平衡二分探索木を実装してそれを可能にする他のライブラリはありますか？
• TreeMultimapの一般的な操作の複雑さは何ですか？

Answer 1

multimap.keySet().ceiling(key)

TreeMultimap.keySet() それはかなり直接的なことですが、 Java6NavigableSetと最新のGuavaリリースである14.0が必要です。複雑さは、予想どおり、O（log #keys）です。

Answer 2

K ceiling(K key, TreeMultimap<K,V> map) {
  SortedSet<K> keyset = map.keySet();
  SortedSet<K> head = keyset.headSet(key);
  return headSet.isEmpty() ? null : head.last();    
}

ドキュメントには操作の時間保証については記載されていませんが、両方とも新しいコレクションを構築するのではなく、基になるデータのビューを返すように見えるkeySetため、対数時間で実行されると思います。headSet