Aplicación del Rojo-Negro Árbol en C#

Busco una implementación de un Red-Black Tree en C#, con las siguientes características:Aplicación del Rojo-Negro Árbol en C#

búsqueda, inserción y eliminación en O (log n).
El tipo de miembro debe ser genérico.
Soporte en Comparer(T), para la clasificación T por diferentes campos en el mismo.
La búsqueda en el árbol debe realizarse con el campo específico, por lo que no aceptará T, pero aceptará el tipo de campo clasificándolo.
La búsqueda no debe ser solo del valor exacto. Debería ayudar a buscar el más bajo/más alto.

Gracias.

Fuente

2009-11-09 Alon Gubkin

Respondiendo a su otra pregunta, llamada "Libro o profesor", la * realmente * mejor forma de aprender a programar es * escribir programas *. Escribe esto por tu cuenta y luego aprenderás algo. –

@Pavel: podría escribir esto, pero estoy buscando algo listo, así puedo continuar desarrollando los lados principales de mi programa y acelerar el desarrollo. –

Usted acaba de describir SortedDictionary<T, U>, a excepción de la siguiente búsqueda binaria del siguiente valor más bajo/siguiente, que podría implementar por su cuenta sin mucha dificultad.

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

Fuente

2009-11-09 19:47:04 mquander

* "que puede implementar por su cuenta sin mucha dificultad". * No creo que pueda extender fácilmente SortedDictionary. Al mirar los metadatos y simplemente tratar de ampliarlos, las piezas internas necesarias no parecen accesibles. ¿Me equivoco? – Catskul

¿Quiere decir que SortedDictionary implementa un árbol rojo-negro? Si lo haces, ¿dónde encontraste esto? No veo ninguna mención de ello en las páginas de MSDN. – comecme

Sí; Acabo de verificarlo rozando la clase en Reflector. Internamente, coloca las claves en un 'SortedSet ', que se implementa como un árbol rojo/negro. No estoy seguro de dónde me enteré. Siento que una versión anterior de la documentación de MSDN entró en más detalles sobre la implementación de 'SortedDictionary' en contraste con' SortedList'. Además, umm, no estoy exactamente seguro de por qué pensé que podría extenderlo fácilmente.No está claro si podría. Oh bien. – mquander

Rip the TreeSet de C5 collection libs.

Fuente

2009-11-09 19:46:44

Esto es exactamente el OrderedDictionary en PowerCollections. Es prácticamente idéntico a SortedDictionary (árbol rojo negro con genéricos) con la capacidad de establecer una tecla de inicio/finalización y escanear todos los valores en ese rango.

SortedDicionary solo permite exponer una función GetEnumerator() que comienza al principio de la colección y solo permite una llamada a MoveNext(), por lo que incluso si usa LINQ no ocurre nada mágico: comienza al principio y ejecuta su expresión en cada nodo, en orden, hasta que encuentre aquellos que coincidan con su expresión LINQ.

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

Sin embargo, una palabra de advertencia: el enumerador en PowerCollections OrderedDictionary se implementa utilizando "rendimiento" y el uso de la memoria y el rendimiento de enumeración es al menos O (n^2) ... puede cambiar la implementación usted mismo para hacerlo implementar un enumerador tradicional y ambos problemas desaparecen. Enviaré ese parche a Codeplex si alguna vez puedo encontrar el tiempo.

Fuente

2013-02-11 19:09:00 huntharo

Aplicación del Rojo-Negro Árbol en C#

Respuesta

Cuestiones relacionadas