How to find the least element greater than a given value on a C# SortedSet?

Question

I know that a SortedSet in C# is a Red-Black tree. My problem involves adding an element to the SortedSet and getting the lowest element greater than the one just inserted. This should take time O(log n). Yet, I couldn't figure out a way to do it without using the method GetViewBetween, which is linear.

Answer 1

Would be good if you'd have provided your approach with GetViewBetween. Why it didn't work? It should, even if i'm not sure complexity:

SortedSet<int> set = new SortedSet<int>(new[] { 3, 1, 5, 2 });
int newElement = 4;
set.Add(newElement);
int max = set.Max; // SortedSet<T> property, not LINQ method
if(max > newElement)
{
    int nextHigher = set.GetViewBetween(newElement + 1, max).First(); // 5
}

Note that the GetViewBetween returns a SortedSet but without copying all elements. It just uses the original set as reference, stores the min- and max-values and determines the current root element(so the one you search).

Edit: It should be O(log n) now.

Answer 2

To find the least element greater than a given value in a SortedSet, you can use the following LINQ query:

sortedSet.Where(x => x.CompareTo(value) > 0).OrderBy(x => x).FirstOrDefault();