CODEWITHSUNDEEP
c#treebinary-treesortedsetsorteddictionary
ILIA BROUDNO
ILIA BROUDNO

Reputation: 1893

C# BinaryTree implementation

I need a binary tree or another structure in which I can store objects with a time stamp and then QUICKLY look them up not just by the timestamp I know is there but also by a range

    (timestamp > min && timestamp < max).

I found SortedDictionary and SortedSet that both implement a binary tree. What I am missing is the ability to look up by range > && < without forcing it (SortedDictionary or SortedSet) internally to iterate over more elements than they need to.

What I mean is when I call

 SortedDictionary.TryGetValue(DateTime.Now, ...

it should take logarithmic time.

I want to be able to get all items between Min and Max in logarithmic time as well. Missing 

SortedDictionary.TryGetValueBetween(DateTime.Now-SomeInterval, DateTime.Now+SomeInterval,...

If I was implementing the binary tree myself it would not be a problem. But I do not see a mechanism for doing it with SortedDictionary or SortedSet. And I don't want to resort to linear time.

Am I just not finding the right methods or do I really need to implement the binary tree myself to get the benefits I am looking for?

Other options are also welcome. Is there a different structure that would give me insert, delete and "range lookup" in log time or better.

Upvotes: 1

Views: 232

Answers (1)

ILIA BROUDNO
ILIA BROUDNO

Reputation: 1893

Found 2 solutions:

  1. On closer inspection SortedSet does have the method I need: GetViewBetween

  2. In a free third party library called Wintellect.PowerCollections there is OrderedMultiDictionary class (see here) that does what I need plus allows duplicates into the collection (unlike SortedSet). The method for getting a range between 2 values is called Range().

Both as far as I can tell do inserts, deletes and lookups in log(n) time.

Upvotes: 2

Related Questions