Является ли tr ie эквивалентом std :: map в С ++?

Question

Является ли обычная реализация tr ie эквивалентной

std::map<std::string, int>

в C ++?

Под эквивалентностью я имею в виду : имеют ли они одинаковую сложность пространства, и имеют ли их соответствующие операции одинаковую сложность времени?

Answer 1

Нет, я не верю в это. std :: map и std :: set обычно реализуются как сбалансированные красно-черные двоичные деревья

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

Сложность времени для поиска, вставки, удаления все еще средний O (log n). Однако постоянный фактор часто важен. Префиксные деревья обычно обмениваются на меньшую высоту, но большую ширину. Специфическое c приложение важно для выбора, какое.