There are functions named
floor in Java’s TreeSet. However I didn’t find something like them in Scala’s TreeSet.
I use code like
set.from(123).min to do such thing. However in this way a new set is created, thus the complexity is
O(n) right? But actually I only need that value, the complexity should be
Is there any function functioning like
You can use the
I know that. But I want to get the max value below an arbitrary value
x. Use plain
max will only get the max value in the whole tree. So I have to use
to method and then
Does it hurt performance? It is mentioned in here few years ago. Is it sill the same?
maxBy method is used for
finding the first element which yields the largest value measured by function f.
f you gave is
_ < x, which yields
Boolean. Seems like Scala considers
True is larger than
TreeSet(1, 3, 5).maxBy(_ < 5) returns 1, due to 1 and 3 both yield
maxBy is not the one I want in this case.
TreeSet(1, 3, 5).maxBy(x => if (x < 5) x else Int.MinValue) this will return the desired result 3. However, I think the complexity of it is
Strange that TreeSet has slice(Int, Int), but no method to get a single
element at a given position.
Of course, you can do
def get[A](set: SortedSet[A], pos: Int): A = set.slice(pos, pos + 1).head
Now you can do a binary search for elements.
slice looks like the combination of
to, which means it’s still the same thing.
slice returns a new TreeSet, which means a new red-black tree will be created, thus the complexity of
O(n) is inevitable.
The point is, in a BST the complexity should be
O(logn) if you want to find a specific value. In Java,
floor are provided to do this.
A reasonable implementation of TreeSet.slice should only go with
Yeah, I agree with u. I said
O(n) because I guess it was similar to heap.
But the point is you can go with
O(log n_total) if you only want that specific value.