如何在 C++ 中实现减少内存使用量的 Trie？

Question

我需要实现一个 trie 结构，以存储大约 30k 个字符串。 现在，trie 结构看起来像这样

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

由于固定大小的数组，我为每个节点分配了太多space，所以我的程序因大量内存使用而崩溃。 对于这个问题，我不能使用地图，这是迄今为止我找到的唯一解决方案。有人有其他建议吗？

谢谢。

Answer 1

使用 std::unordered_map<char, TrieNode> 代替 TrieNode * 数组。

如果需要 children 排序，请使用 std::map<char, TrieNode>。

如果您不允许使用 STL，请自己实现哈希图或平衡二叉树class。