C ++ FP-дерево или префиксное дерево

Question

У меня есть несколько последовательностей, так как эти

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

есть некоторая эффективная реализация префиксного дерева или fp-дерева или аналогичного в C + +?

Answer 1

Я не понимаю, что вы говорите ... Но если вам нужно построить дерево FP, вот лучшая страница, которую я нашел

Алгоритм дерева FP

Answer 2

Непонятно, что именно у вас, потому что данные не отображаются ни в одной стандартной записи.

Если префиксы - это всего лишь несколько общих начальных десятичных цифр между целыми значениями, они, вероятно, выигралине имеет большого значения для хранения данных.Вы можете вычесть 100 перед вставкой значений в структуру данных, сохранить значения как char и добавить 100 обратно после извлечения, но это, вероятно, не стоит усилий.

Возможно, вам следует сохранить последовательностьпоследовательности как std::deque< std::vector< int > >, где отсортированы элементы vector.Если не существует шаблона, который я не вижу, или я неправильно истолковываю проблему, оптимальная производительность для нахождения последовательностей, содержащих данное число, должна быть O (N) в количестве последовательностей, умноженном на O (lg N) в длине последовательности.