.NET equivalent of Java's TreeSet.floor & TreeSet.ceiling

Question

As an example, there's a Binary Search Tree which holds a range of values. Before adding a new value, I need to check if it already contains it's 'almost duplicate'. I have Java solution which simply performs floor and ceiling and further condition to do the job.

JAVA: Given a TreeSet, floor() returns the greatest element in this set less than or equal to the given element; ceiling() returns the least element in this set greater than or equal to the given element

TreeSet<Long> set = new TreeSet<>();

long l = (long)1;  // anything
Long floor = set.floor(l);
Long ceil = set.ceiling(l);

C#: Closest data structure seems to be SortedSet<>. Could anyone advise the best way to get floor and ceil results for an input value?

SortedSet<long> set = new SortedSet<long>();

Probably `Math.Floor` and `Math.Ceiling`. What is `l` though? — SᴇM, Sep 05 '18 at 08:04
@SeM, I need floor and ceiling methods that operate on BST range — user2376997, Sep 05 '18 at 08:20
This is needed so badly in the .Net. You can't implement a wide range of algorithms without writing your own data structure. — koolaang, Aug 31 '20 at 22:53

score 2 · Answer 1 · answered Feb 06 '19 at 06:46

2

The above, as mentioned, is not the answer since this is a tree we expect logarithmic times. Java's floor and ceiling methods are logarithmic. GetViewBetween is logarigmic and so are Max and Min, so:

floor for SortedSet<long>: sortedSet.GetViewBetween(long.MinValue, num).Max

ceiling for SortedSet<long>: sortedSet.GetViewBetween(num, long.MaxValue).Min

answered Feb 06 '19 at 06:46

Lucio Silveira

23
4

As GetViewBetween() method returns SortedSet, which contains Count property that requires O(N) time to configure, this method does not achieve logarithmic time complexity. – wkwk Apr 20 '20 at 02:16
3

Unfortunately GetViewBetween() is O(N) https://stackoverflow.com/questions/9850975/why-sortedsett-getviewbetween-isnt-olog-n – Ojas Maru Feb 04 '21 at 23:42
Though GetViewBetween() might be O(logN) according to some comments, isn't the code itself wrong? `sortedSet.GetViewBetween(num, long.MaxValue).Min` is `num` itself. – chuang Jul 03 '21 at 12:32
@chuang not if `num` is not in `sortedSet`. The code looks correct to me. And some comments here say that dotnet core's `GetViewBetween` is `O(logN)` (agreeing with you, just didn't see such comments on this question): https://stackoverflow.com/q/9850975/2850543 – Millie Smith Aug 18 '21 at 05:44

score 1 · Accepted Answer · answered Sep 05 '18 at 08:10

1

You can use something like this. In Linq there is LastOrDefault method:

var floor = sortedSet.LastOrDefault(i => i < num);
// num is the number whose floor is to be calculated
if (! (floor < sortedSet.ElementAt(0)))
{
  // we have a floor
}
else
 // nothing is smaller in the set
{
}

answered Sep 05 '18 at 08:10

Gauravsa

6,330
2
21
30

2

This won't have the nice logarithmic time complexity of Java solution, right? It's just a linear search. – Lukáš Lánský Sep 05 '18 at 08:51
Yes agreed. I think search is binary with O(n).. sortedset in c# vs treeset in java will make a good SO question – Gauravsa Sep 05 '18 at 09:20

.NET equivalent of Java's TreeSet.floor & TreeSet.ceiling

2 Answers2