如何实现一个具有一次读取4位的节点的二进制trie？

Question

我试图找到一种方法，在某种意义上内联一个二进制trie。基本上，二进制trie为二进制数字中的每个插槽都有一个节点，在0上向左分支，在1上向右分支。你将如何构造这样你可以一次读取4位而不是1位？在每个trie节点中有16个插槽似乎是可能的，但我很难想象这将是什么样子；如何使用这种方法一次读取二进制输入，比如101010104位。会是什么样子？

[  left    , right   ,    left,  right  ,  left,   right   ...]
  (goto2)    (goto5)   (goto7)  (goto8)   (goto9), (goto10)

或者我不知道。什么是一个算法，将检查4位与16个插槽在一个数组？

似乎4位可以在16个槽中表示，但我只是不明白一个算法如何在没有手动详细可视化每一步的情况下找出如何读取这些数据。一定有什么方程式什么的。

Answer 1

你描述的是一个基数trie基数16。通过从密钥中提取4位，您将得到一个0到15（含）之间的数字。您可以使用该数字索引到节点：

struct Node {
    Node *children[16];
    Value value;
};

Value *find(const char *key, int nkey, Node *node) {
    int i = 0;
    while(i < 2*nkey && node) {
        int digit = (key[i/2] >> (i%2==0 ? 0 : 4)) & 0xf;
        node = node->children[digit];
        ++i;
    }
    return node ? &node->value : 0;
}