Árbol C ++ FP o árbol de prefijo

Question

Tengo algunas secuencias como estas

(100) - (102) - (103) - (104,106) - (108)
(101) - (103)
(102) - (106)

¿Hay alguna implementación eficiente un árbol de prefijo o árbol FP o similar en C + +?

Answer 1

No entiendo lo que estás diciendo ... pero si necesitas construir un árbol FP aquí es la mejor página que he encontrado

Algoritmo de árbol de FP

Answer 2

No está claro exactamente lo que tiene porque los datos dados no parecen estar en ninguna notación estándar.

Si los prefijos son solo algunos dígitos decimales iniciales compartidos entre los valores enteros, probablemente no hagan ninguna diferencia significativa para el almacenamiento de datos. Podrías restar 100 Antes de insertar valores en la estructura de datos, almacene los valores como char, y agregue 100 de regreso después de la recuperación, pero probablemente no valga la pena.

Probablemente deberías almacenar la secuencia de secuencias como un std::deque< std::vector< int > > donde el vector Los elementos están ordenados. A menos que haya un patrón que no pueda ver o estoy malinterpretando el problema, el rendimiento óptimo para encontrar qué secuencias contienen un número dado debe ser o (n) en el número de secuencias tiempos o (lg n) en la longitud de la secuencia .