1

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.

Seno
  • 157
  • 8
  • 4
    What do you base the assertion on that `GetViewBetween` is linear? It should be `O(log N)`, meaning that creating a view from `value + 1` to `int.MaxValue` and getting the first element (which is `O(1)`) should do what you want. – Jeroen Mostert Aug 15 '22 at 13:13
  • @RyanWilson: interesting, so it *used* to be linear. I wouldn't have expected that -- and neither did most other people, judging from the comments. – Jeroen Mostert Aug 15 '22 at 13:41
  • @RyanWilson this answer Jeroen's question, but not mine – Seno Aug 15 '22 at 13:42
  • @JeroenMostert why *used*? – Seno Aug 15 '22 at 13:43
  • 1
    @Seno it does too. Look at the final answer, you can use `GetViewBetween` and `First()` as Jeroen mentioned. – Ryan Wilson Aug 15 '22 at 13:43
  • 1
    @Seno: it answers both questions. I only looked at the most recent source, so I wasn't even aware of the perf issue in older versions. Should you actually be stuck with an implementation where it exists with no path for upgrades I'd say this justifies getting an independent implementation; `SortedSet` is not special other than being part of the BCL. – Jeroen Mostert Aug 15 '22 at 13:45
  • 1
    A truly boneheaded decision/oversight, and it's present in all versions .NET Framework up to and including 4.8, so you would need to move up to Core/.NET 6+ to fix it. Big ouch for people who have to stick with Framework to stay compatible with other code. – Jeroen Mostert Aug 15 '22 at 13:55
  • Thank you @RyanWilson and JorenMostert, it indeed works :) – Seno Aug 15 '22 at 14:06

2 Answers2

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.

Tim Schmelter
  • 450,073
  • 74
  • 686
  • 939
0

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();
Olivier Jacot-Descombes
  • 104,806
  • 13
  • 138
  • 188
Ron Adin
  • 49
  • 8