La biblioteca de clases base en .NET tiene algunas estructuras de datos excelentes para colecciones (Lista, Cola, Pila, Diccionario), pero curiosamente no contiene ninguna estructura de datos para árboles binarios. Esta es una estructura tremendamente útil para ciertos algoritmos, como los que aprovechan diferentes rutas transversales. Estoy buscando una implementación gratuita y correctamente escrita.
¿Estoy simplemente ciego y no lo encuentro ... está enterrado en algún lugar del BCL? Si no es así, ¿alguien puede recomendar una biblioteca C # / .NET gratuita o de código abierto para árboles binarios? Preferiblemente uno que emplee genéricos.
EDITAR: Para aclarar lo que estoy buscando. No me interesan las colecciones de diccionarios ordenadas que utilizan internamente un árbol. De hecho, estoy interesado en un árbol binario, uno que exponga su estructura para que pueda hacer cosas como extraer subárboles o realizar un recorrido posterior a la corrección en los nodos. Idealmente, dicha clase podría extenderse para proporcionar los comportamientos de árboles especializados (es decir, rojo / negro, AVL, equilibrado, etc.).
fuente
Respuestas:
Tienes razón, no hay nada en la BCL. Sospecho que esto se debe a que la elección de utilizar un árbol suele ser un detalle de implementación y, por lo demás, es una forma poco convencional de acceder a los datos. Es decir, no dice, "binary-search-for element # 37"; en su lugar, dice, "consígame el elemento n. ° 37".
Pero, ¿ha echado un vistazo al C5 ? Es muy útil y tienen varias implementaciones de árbol ( 1 , 2 , 3 ).
fuente
Podrías definir el tuyo propio:
public class MyTree<K, V> : Dictionary<K, MyTree<K, V>> { public V Value { get; set; } }O sin llave:
public class MyTree<V> : HashSet<MyTree<V>> { public V Value { get; set; } }fuente
¿Qué le gustaría de tal implementación?
¿Árbol binario? ¿Negro rojo? ¿Árbol de radix? Árbol B? R-tree? R * -árbol?
Un árbol es más un patrón que una estructura de datos, y tienden a usarse donde el rendimiento importa (por lo que los detalles de implementación probablemente también importen). Si el BCL incluye algún tipo de clase de árbol, de todos modos solo tendrías que tirar el tuyo
fuente
Creo que
SortedDictionarycomo la inserción de log (n), las características de recuperación que esperaría de una estructura de datos de árbol.http://msdn.microsoft.com/en-us/library/f7fta44c(VS.80).aspx
fuente
SortedSet<T>se implementa como un árbol de búsqueda binario ref .SortedDictionary<TKey, TValue>utiliza internamente, porSortedSet<T>lo que también es un árbol de búsqueda binario ref .fuente
No, no hay ningún tipo "
Tree<T>similar" en el BCL (algo que siempre me ha desconcertado también) pero aquí hay un buen artículo que lo guiará a través de la implementación del suyo en C #.Supongo que podría argumentar que las estructuras de datos basadas en árboles se usan con menos frecuencia en el tipo de aplicaciones para las que se usa generalmente .NET (aplicaciones comerciales, aplicaciones de movimiento de datos, etc.). Aún así, estoy de acuerdo con usted, es extraño que el BCL no tenga implementación alguna.
fuente
Esta serie de artículos fue útil para mí cuando tuve que escribir los míos, especialmente las partes 3 y 4.
Un examen exhaustivo de las estructuras de datos
fuente
Hay un TreeNode que puedes usar. No es genérico y está oculto en formularios de Windows y se usa con el control de vista de árbol, pero también puede usarlo en otros lugares.
fuente