How to retrieve elements from sorted TreeSet using Binary Search?

Question

I am trying to merge multiple sorted lists into one TreeSet.. And then I am thinking to apply Binary Search algorithm on that TreeSet to retrieve the element in O(log n) time complexity..

Below is my code in which I am passing List of Lists in in one of my method and combining them into TreeSet to avoid duplicacy... All the lists inside inputs are sorted -

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)
}

• First of all, is this right way to merge multiple sorted lists into TreeSet? Is there any direct way to merge multiple sorted lists in TreeSet efficiently?
• Secondly, how would I extract an element from that TreeSet in O(log n) time complexity? I would like to find an element x in that TreeSet, if it is there, then return it, if it is not there then return the next largest value from the TreeSet.

Or may be I am better off to another data structure as compared to which I am using currently?

UPDATED CODE:-

private TreeSet tree = new 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
    }
}

Latchet

You can use TreeSet.addAll() instead of adding each element individually. It'll save a few LOC but I don't know if it's any more perfomant. – Deemphasize

@MikeB: Thanks for tip for addAll.. I totally forgot that.. And now regarding my second question.. Any thoughts? – Latchet

Looks like the discussion here is relevant: #3390949 – Arnaud

What do you mean by "extract an element"? Do you want to get the xth largest element? Do you want to test if x is in the TreeSet? Do you want to get the element that is equal to x (in which case...you'd just return x?) – Incorporate

I would like to find an element x in that TreeSet, if it is there, then return it, if it is not there then return the next largest value from the TreeSet. – Latchet

Answer 1

TreeSet is backed by a NavigableMap, a TreeMap specifically. Calling contains() on a TreeSet delegates to TreeMap.containsKey(), which is a binary search implementation.

You can check if an object is contained in the set by using TreeSet.contains(), but you have to have the object first. If you want to be able to look up and retrieve an object, then a Map implementation will be better.

Deemphasize

Thanks Mike.. I updated the question with the latest code.. Earlier I misunderstood but after your suggestion, few things got cleared up.. But I have one doubt in my else statement.. Take a look at my code.. – Latchet

Maybe the higher() method in TreeSet? I've never used it but it looks like what you want. For future reference, you can look at the javadocs first to see if your answer is there: docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html – Deemphasize

U sure it uses a binarysearch imp? have a look at Entry<K,V> getEntry in TreeMap, to me it looks like a positional 'linked' based search. – Stinkwood

It might have changed since I posted my answer. It was definitely a binary search implementation at the time, though. – Deemphasize

Answer 2

You could use TreeSet.floor(), which according to the docs

Returns the greatest element in this set less than or equal to the given element, or null if there is no such element.

Connivance

Answer 3

TreeSet, by it's nature is a sorted set and uses a red-tree-black-tree via TreeMap as it's backing

Basically: TreeSet.add(E) -> TreeMap.put(E,NULL);

As it is already a binary, sorted tree structure any 'get' or 'contains' will result in an O(log n) operation.

Your code and your question though don't line up.

You're flattening a List<List<Integer>> and just putting them all in to get all unique elements (or, at least, that's what this code will do).

But then your following method says "given this integer, give me a List<Integer>" which isn't achievable in the above code

So, let me answer your questions in order:

1. Sure/Yes Y
2. No. You misunderstand Sets (you can't extract by design) If you can do Set.contains(e) then you HAVE the element and need not extract anything

If you need to do something like a "Set extraction" then use a TreeMap or turn your set back into a list and do myList.get(Collections.binarySearch(myElement));

Spiritism