¿Qué es una implementación de árbol de C ++ buena y estable?

Question

Me pregunto si alguien puede recomendar una buena implementación de árbol C ++, espero que sea una 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 perezoso 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í y la conectividad del árbol son importantes en este caso, no solo los datos que contiene. Por lo tanto, cada rama debe ser capaz de contener cantidades arbitrarias de datos, y cada rama debe ser iterable por separado.

Answer 1

No sé cuáles son 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? Puede 'emular' un árbol a través de un gráfico, y tal vez esté (conceptualmente) más cerca de lo que está buscando.

Answer 2

Eche un vistazo a esto .

La biblioteca tree.hh para C ++ proporciona una clase de contenedor similar a STL para árboles n-arios, con plantillas sobre los datos almacenados en los nodos. Se proporcionan varios tipos de iteradores (post-orden, pre-orden y otros). Siempre que sea posible, los métodos de acceso son compatibles con el STL o existen algoritmos alternativos disponibles.

HTH

Answer 3

Voy a sugerir usar std :: map en lugar de un árbol.

Las características de complejidad de un árbol son:

Insertar: & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; O (ln (n))
Eliminación: & Nbsp; & Nbsp; O (ln (n))
Buscar: & Nbsp; & Nbsp; & Nbsp; & Nbsp; & Nbsp; & Nbsp; & Nbsp; & Nbsp; & Nbsp; O (ln (n))

Estas son las mismas características que garantiza std :: map.
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 obligatorio).

Answer 4

Ok amigos, encontré otra biblioteca de árbol; stlplus.ntree . Pero aún no lo he probado.

Answer 5

Si no tiene pares (clave, valor), sino simplemente claves, use std :: set. Utiliza el mismo árbol Rojo-Negro que std :: map.

Answer 6

Supongamos que la pregunta se trata de árboles binarios balanceados (de alguna forma, principalmente árbol negro rojo), incluso si no es el caso.

Los árboles binarios equilibrados, como el vector, permiten gestionar algunos ordenamientos de elementos sin necesidad de clave (como insertar elementos en cualquier parte del vector), pero:

• Con O óptimo (log (n)) o mejor complejidad para todas las modificaciones de un elemento (agregar / eliminar al comienzo, finalizar y antes de & amp; después de cualquier iterador)
• Con persistencia de 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 usan, los iteradores serán aleatorios.

Opcionalmente, el orden puede imponerse mediante alguna función de comparación, pero la persistencia de los iteradores permite utilizar un esquema de comparación no repetible (p. ej., el cambio arbitrario de carriles de automóviles durante un atasco de tráfico).

En la práctica, el árbol binario equilibrado tiene una interfaz de vector, lista, lista de doble enlace, mapa, multimapa, deque, cola, prioridad_queue ... con la obtención de la complejidad O teórica óptima (log (n)) para todas las operaciones de un solo elemento.

< sarcástico > esta es probablemente la razón por la cual c ++ stl no lo propone < / sarcastic >

Los individuos pueden no implementar un árbol equilibrado general por sí mismos, debido a las dificultades para lograr un manejo correcto del equilibrio, especialmente durante la extracción de elementos.

No hay una implementación ampliamente disponible del árbol binario balanceado porque el árbol negro rojo de última generación (en este momento el mejor tipo de árbol balanceado debido a un número fijo de reorganizaciones de árboles costosas durante la eliminación) conoce la implementación, copiada servilmente por cada implementadores & # 8217; desde 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.