¿Qué es una implementación de árbol C++ buena y estable?
tree graph-theory (6)
Me pregunto si alguien puede recomendar una buena implementación de árbol C ++, con suerte uno que sea compatible con stl si es posible.
Para el registro, he escrito algoritmos de árbol muchas veces antes, y sé que puede ser divertido, pero quiero ser pragmático y flojo si es posible. Entonces, el objetivo es un enlace real a una solución de trabajo.
Nota: Estoy buscando un árbol genérico, no un árbol equilibrado o un mapa / conjunto, la estructura en sí misma y la conectividad del árbol son importantes en este caso, no solo los datos dentro. Por lo tanto, cada rama debe ser capaz de contener cantidades arbitrarias de datos, y cada rama debe ser iterable por separado.
Ok amigos, encontré otra biblioteca de árbol , pero aún no lo he probado
Si no tiene pares (clave, valor), sino simplemente claves, use std :: set. Utiliza el mismo árbol Rojo-Negro que std :: map.
Voy a sugerir el uso de std :: map en lugar de un árbol.
Las características de complejidad de un árbol son:
Insertar: O (ln (n))
Remoción: O (ln (n))
Buscar: O (ln (n))
Estas son las mismas características que std :: map garantiza.
Por lo tanto, como resultado, la mayoría de las implementaciones de std :: map usan un árbol (árbol rojo-negro) debajo de las cubiertas (aunque técnicamente esto no es necesario).
No conozco sus requisitos, pero ¿no estaría mejor con un gráfico (implementaciones, por ejemplo, en Boost Graph ) si está interesado principalmente en la estructura y no tanto en los beneficios específicos del árbol como la velocidad a través del equilibrio? ? Puedes ''emular'' un árbol a través de un gráfico, y tal vez estará (conceptualmente) más cerca de lo que estás buscando.
Echa un vistazo a esto .
La biblioteca tree.hh para C ++ proporciona una clase de contenedor tipo STL para árboles n-aries, con plantillas sobre los datos almacenados en los nodos. Se proporcionan varios tipos de iteradores (orden posterior, preorden y otros). Donde sea posible, los métodos de acceso son compatibles con el STL o hay algoritmos alternativos disponibles.
HTH
Supongamos que la pregunta es sobre árboles binarios equilibrados (de alguna forma, en su mayoría árboles rojos y negros), incluso si no es el caso.
Los árboles binarios equilibrados, como el vector, permiten administrar algunos pedidos de elementos sin necesidad de clave (como al insertar elementos en cualquier parte del vector), pero:
- Con óptimo O (log (n)) o mejor complejidad para todas las modificaciones de un elemento (agregar / eliminar al comienzo, al final y antes y después de cualquier iterador)
- Con la persistencia de los iteradores a través de cualquier modificación, excepto la destrucción directa del elemento señalado por el iterador.
Opcionalmente, uno puede admitir el acceso por índice como en vector (con un costo de un size_t por elemento), con complejidad O (log (n)). Si se usa, los iteradores serán aleatorios.
Opcionalmente, el orden puede ser impuesto por alguna función de comparación, pero la persistencia de los iteradores permite utilizar un esquema de comparación no repetible (por ejemplo, cambios arbitrarios en carriles de automóviles durante un atasco de tráfico).
En la práctica, el árbol binario equilibrado tiene una interfaz de vector, lista, doble lista vinculada, mapa, multimapa, deque, cola, prioridad_cola ... con la consecución de la complejidad teórica óptima O (log (n)) para todas las operaciones de elemento único.
<sarcástico> esta es probablemente la razón por la cual c ++ stl no lo propone </ sarcastic>
Los individuos no pueden implementar un árbol equilibrado general por sí solos, debido a las dificultades para lograr un manejo correcto del equilibrio, especialmente durante la extracción del elemento.
No hay una implementación ampliamente disponible de árbol binario equilibrado porque el árbol negro rojo de última generación (en este momento el mejor tipo de árbol equilibrado debido a la cantidad fija de costosas reorganizaciones de árbol durante la eliminación) conoce la implementación, copiado servilmente por cada implementador de el código inicial del inventor de la estructura no permite la persistencia del iterador. Probablemente sea la razón de la ausencia de una plantilla de árbol completamente funcional.