c++ - 在 C++ 中创建 trie/suffix 树时减少内存使用

Question

我正尝试在 C++ 中创建一个 trie，现在我的基本数据结构看起来像..

struct node{
    int count; no of times this node has been visited.
    struct node* child[ALPHABET_SIZE]; // Let ALPHABET_SIZE be 26
}

当字符串变大时，会浪费大量分配的内存。就像我们插入 "he"我们的树将是

root---->h--->e
    |--->e

我们看到在根目录下，只有 2/26th 分配的内存被使用。 如何改进？？。

Answer 1

一些非常基本的建议:

1. 如果预计您的分支因子较低，请考虑为子项使用数组以外的其他内容。例如，您可以有一个字母到节点* 对的数组，并对它们进行线性或二进制搜索(如果它们是有序的)。您也可以使用某种 map 。
2. 如果您不希望计数达到数百万/数十亿，您也可以使用更小的整数。
3. 您可以从基于竞技场的分配器(即对象池)获取节点，而不是动态分配节点，从而避免通常添加到堆上分配的对象的堆分配开销。