The most efficient way to find an index of an element in a SortedDictionary

Question

I use a sorted dictionary to maintain a list of items from which I regularly need to monitor the state of the top x items. Every time I update an item, I would like to quickly find out which index is used for the item I'm referring to. I understand that I can list the entire list and calculate my position, but I'm looking for something with O (log n) or better, after the sorted dictionary is in the RedBlack tree. Each node should be able to track its children, and this should be a quick calculation.

Answer 1

You can simply change your SortedDictionary<TKey, TValue> to SortedList<TKey, TValue> , and then use IndexOfKey(key) :

 var s = new SortedList<string, string> { { "a", "Ay" }, { "b", "Bee" }, { "c", "Cee" } }; // Outputs 1 Console.WriteLine(s.IndexOfKey("b")); 

IndexOfKey internally uses Array.BinarySearch<TKey>() , so it will be O (log n), which is faster than O (n) (which would be if you were looking back first by iterating through it).

Answer 2

A tree structure can be built to access items by index or to represent the index of an existing item in lgN time, requiring very little extra time for insertions and deletions. One way to do this would be to keep track of how many elements are in the left and right branches of each node (when inserting or deleting, change the number of parent nodes of the node when changing the number of children). If the tree structure does not offer such a tool, I know that there an easy way to modify it.