La forma más eficiente de encontrar el índice de un artículo en SortedDictionary

Question

Estoy usando un diccionario ordenado para mantener una lista de elementos, de los cuales regularmente debo monitorear el estado de los principales x elementos. Cada vez que actualizo un artículo, me gustaría encontrar una forma rápida de determinar a qué índice está usando el ítem al que me refiero. Entiendo que puedo enumerar la lista completa y contar mi posición, pero estoy buscando algo con O (log n) time o mejor, después de que todo el diccionario ordenado esté en un árbol RedBlack. Cada nodo debe ser capaz de realizar un seguimiento de sus hijos, y esto debería ser un cálculo rápido.

Answer 1

Usted puede simplemente cambiar su SortedDictionary<TKey, TValue> en un SortedList<TKey, TValue> y luego usar IndexOfKey(key):

var s = new SortedList<string, string> 
    { { "a", "Ay" }, { "b", "Bee" }, { "c", "Cee" } }; 

// Outputs 1 
Console.WriteLine(s.IndexOfKey("b")); 

utiliza internamente Array.BinarySearch<TKey>(), por lo que será O (log n), que es más rápido que O (n) (que sería si usted buscara de adelante hacia atrás iterando a través de él).

Answer 2

Se podría construir una estructura de árbol para acceder a los elementos por índice o informar el índice de un elemento existente en tiempo de lgN, lo que requiere un tiempo extra muy ligero para las inserciones y eliminaciones. Una forma de hacerlo sería realizar un seguimiento de cuántos elementos se encuentran en las ramas izquierda y derecha de cada nodo (en una inserción o eliminación, cambie el recuento de nodos de los nodos principales al cambiar el recuento de los hijos). Sin embargo, si una estructura basada en árboles no ofrece tal facilidad, no conozco ninguna manera fácil de actualizarla.