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

我正在尝试找到一种方法inline某种意义上的二进制字典树。基本上，二进制 trie 为二进制数中的每个槽都有一个节点，在 0 上向左分支，在 1 上向右分支。您将如何构造它以便一次读取 4 位而不是 1？似乎每个 trie 节点中有 16 个槽就可以实现这一点，但我很难想象这实际上是什么样子；你将如何读取二进制输入10101010使用这种方法一次 4 位。它会是什么样子？

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

或者我不知道。可以根据数组中的 16 个槽检查 4 位的算法是什么？

似乎 4 位可以用 16 个槽表示，但我只是不明白算法如何在不手动详细可视化每个步骤的情况下找出如何读取这些值。一定有一些方程式或其他东西。

你所描述的是一个基数特里树 https://en.wikipedia.org/wiki/Radix_tree以 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;
}