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

Question

我正在尝试找到一种方法来在某种意义上对二进制 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 个槽表示，但我只是不明白算法如何在不手动详细可视化每个步骤的情况下弄清楚如何读取这些。一定有方程什么的。

Answer 1

您所描述的是一个 radix 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;
}

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

How to implement a binary trie that has nodes that read 4 bits at a time?

javascript

algorithm

binary-tree

trie

data-structures