java - 带 TreeMultimap 的吊顶（）

Question

• 是否有可能从谷歌的番石榴扩展 TreeMultimap 以获得一些奇怪的ceiling功能？ceiling(key)将返回大于给定键的最小键。（我知道我可以得到一个有序的集合视图并只看，但我更喜欢时间复杂度更高的东西，比如平衡的二叉搜索树提供）
• 是否有任何其他库可以实现平衡的二叉搜索树并允许这样做？
• TreeMultimap常用操作的复杂度是多少？

Answer 1

multimap.keySet().ceiling(key)

它非常直接，但是您需要 Java 6 和最新的 Guava 版本 14.0，即TreeMultimap.keySet() 开始返回NavigableSet. 复杂度为 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都返回基础数据的视图，而不是自己构建新集合。