c - 节省空间的特里

Question

我正尝试在 C 中实现一个节省空间的 trie。这是我的结构:

struct node {
char val; //character stored in node
int key; //key value if this character is an end of word
struct node* children[256];
};

当我添加一个节点时，它的索引是字符的无符号字符转换。比如我要加“c”，那么

children[(unsigned char)'c']

是指向新添加节点的指针。但是，此实现要求我声明一个包含 256 个元素的 node* 数组。我想做的是:

struct node** children;

然后在添加节点时，只需为节点分配空间并拥有

children[(unsigned char)'c']

指向新节点。问题是，如果我不首先为 child 分配空间，那么我显然不能引用任何索引，否则这是一个很大的错误。

所以我的问题是:如何实现一个 trie，使其只存储指向其子节点的非空指针？

Answer 1

您可以尝试使用 de la Briandais trie ，其中每个节点只有一个子指针，每个节点也有一个指向“ sibling ”的指针，因此所有 sibling 都有效地存储为一个链表，而不是直接由父节点指向。