C ++ FP-arbre ou arbre Prefix

Question

J'ai quelques séquences que celles-ci

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

il y a une mise en œuvre efficace d'un arbre préfixe ou fp-arbre ou similaire en C + +?

Answer 1

Je ne comprends pas ce que vous dites ... Mais si vous avez besoin de construire un arbre FP est meilleure page ici, je l'ai trouvé

FP Arbre algorithme

Answer 2

Il est pas clair exactement ce que vous avez parce que les données fournies ne semble pas être dans une notation standard.

Si les préfixes ne sont que quelques premiers chiffres décimaux partagés entre les valeurs entières, ils seront sans doute pas faire de différence significative pour le stockage des données. Vous pouvez soustraire 100 avant d'insérer des valeurs dans la structure de données, stocker les valeurs que char, et ajouter 100 retour après la récupération, mais il est sans doute pas la peine.

Probablement vous devez stocker la séquence de séquences en tant que std::deque< std::vector< int > > où les éléments vector sont triés. À moins d'un motif que je ne peux pas voir ou je mal interpréter le problème, le rendement optimal en constatant que les séquences contiennent un nombre donné doit être O (N) du nombre de fois que des séquences O (lg N) dans la longueur de séquence .