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) в длине последовательности.,