Árbol C ++ FP o árbol de prefijo
-
27-10-2019 - |
Pregunta
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 + +?
Solución
No entiendo lo que estás diciendo ... pero si necesitas construir un árbol FP aquí es la mejor página que he encontrado
Otros consejos
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 .