Как реализовать Trie с уменьшенным использованием памяти в C ++?

Question

Мне нужно реализовать структуру trie, чтобы хранить приблизительно 30 тыс. Строк.Прямо сейчас структура дерева выглядит так:

struct TrieNode {
        bool isWord=false;
        struct TrieNode* children[256];
};

Для каждого узла я выделяю слишком много места из-за массива фиксированного размера, поэтому моя программа падает из-за огромного использования памяти.Для этой проблемы я не могу использовать карты, которые были единственным решением, которое я нашел до сих пор.У кого-нибудь есть еще советы?

спасибо.

Answer 1

Используйте std::unordered_map<char, TrieNode> вместо TrieNode * массива.

Если вам нужно отсортировать детей, используйте std::map<char, TrieNode>.

Если вам не разрешено использовать STL, самостоятельно реализуйте хэш-карту или сбалансированный класс двоичного дерева.