Implementación de la Red-Negro Árbol en C #

Question

Estoy buscando una implementación de un Rojo-Negro Árbol en C #, con las siguientes características:

• Buscar, insertar y eliminar en O (log n).
• Tipo de miembros debe ser genérico.
• Soporte en Comparer (T) , para clasificar T por diferente campos en el mismo.
• La búsqueda en el árbol debe estar con el campo específico, por lo que no aceptará T, sino que va a aceptar el tipo de campo de clasificación a él.
• La búsqueda no debe ser sólo un valor exacto. Debe apoyar la búsqueda de la más alta uno inferior /.

Gracias.

Answer 1

SortedDictionary<T, U> , a excepción de la segunda más baja / siguiente valor más alto de búsqueda binaria, que se podría aplicar por su cuenta sin mucha dificultad.

¿Hay razones específicas que SortedDictionary es insuficiente para usted?

Answer 2

rasgar el TreeSet de libs de recogida de C5.

Answer 3

Este es exactamente el OrderedDictionary en PowerCollections. Es más o menos idéntica a SortedDictionary (árbol rojo negro con los genéricos) con la adición de la capacidad de establecer una tecla de inicio / final y escanear todos los valores en ese rango.

SortedDicionary sólo permite expone una función GetEnumerator () que comienza al principio de la colección y sólo permite a una llamada MoveNext (), por lo que incluso si se utiliza LINQ no hay nada sucede la magia: Se inicia en el comienzo y ejecuta su expresión en cada nodo único, en orden, hasta que encuentra los que concuerden con su expresión LINQ.

OrderedDictionary tiene una función que obtiene un empadronador en o antes de una clave particular y que hace las operaciones de búsqueda en O (log n).

Una palabra de precaución sin embargo: el empadronador en el PowerCollections OrderedDictionary se implementa utilizando el "rendimiento" y el uso de la memoria y el rendimiento de enumeración es al menos O (n ^ 2) ... puede cambiar la aplicación a sí mismo para que sea implementar un empadronador tradicional y ambos de estos problemas desaparecen. Voy a presentar ese parche a CodePlex si alguna vez puedo encontrar el tiempo.