如何使用二进制搜索从排序树集检索元素？

Question

我正在尝试将多个已排序的列表合并到一个树集中。。然后我考虑在树集上应用二进制搜索算法，以O（logn）的时间复杂度检索元素。。

下面是我的代码，我在其中一个方法中传递列表列表，并将它们组合成TreeSet以避免重复...所有列表中的输入排序-

private TreeSet<Integer> tree = new TreeSet<Integer>();

public void mergeMultipleLists(final List<List<Integer>> inputs) {
    tree = new TreeSet<Integer>();
    for (List<Integer> input : inputs) {
        for(Integer ii : input) {
            tree.add(ii);
        }
    }
}

public List<Integer> getItem(final Integer x) {
    // extract elements from TreeSet in O(log n)
}

• 首先，这是将多个排序列表合并到树集的正确方法吗？有没有直接的方法可以有效地合并TreeSet中的多个排序列表

或者，与我目前使用的数据结构相比，我更适合使用另一种数据结构？

更新代码：-

私有树集树=新树集（）；

public SearchItem(final List<List<Integer>> inputs) {
    tree = new TreeSet<Integer>();
    for (List<Integer> input : inputs) {
        tree.addAll(input);
    }
}

public Integer getItem(final Integer x) {
    if(tree.contains(x)) {
        return x;
    } else {
        // now how do I extract next largest 
         // element from it if x is not present
    }
}

Answer 1

TreeSet本质上是一个排序集，通过TreeMap使用红树黑树作为后盾

基本上是：树集。加（E）-

因为它已经是一个二进制的排序树结构，任何“获取”或“包含”都将导致O（log n）操作。

你的代码和你的问题不一致。

您正在压平一个列表

但是接下来的方法是“给定这个整数，给我一个列表

所以，让我按顺序回答你的问题：

1. 当然/是Y
2. 没有。你误解了集合（你不能通过设计提取）如果你能做Set.contains（e），那么你就有了元素，不需要提取任何东西

如果您需要执行设置提取之类的操作，请使用TreeMap或将您的设置转换回列表，并执行myList.get（Collections.binarySearch（myElement））；

Answer 2

您可以使用TreeSet.floor（），根据文档

返回此集合中小于或等于给定元素的最大元素，如果没有此类元素，则返回null。

Answer 3

TreeSet由一个NavigableMap、一个TreeMap支持。在TreeSet上调用contains（）将委托给TreeMap。containsKey（），这是一个二进制搜索实现。

您可以使用TreeSet检查集合中是否包含对象。contains（），但必须先拥有对象。如果您希望能够查找和检索对象，那么Map实现会更好。