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

Question

I am trying to find a way to sort of inline a binary trie in some sense. Basically, a binary trie has a node for every slot in a binary number, branching left on 0 and right on 1. How would you structure this so you could read 4 bits at a time rather than 1? It seems this would be possible by having 16 slots in each trie node, but I'm having a hard time visualizing how this would actually look; how you would read the binary input like 10101010 4-bits at a time using this sort of approach. What would it look like?

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

Or I don't know. What is an algorithm that would check the 4 bits against 16 slots in an array?

It seems that 4 bits can be represented in 16 slots, but I just don't see how an algorithm can figure out how to read these without manually visualizing every step in detail. There must be some equation or something.

question from:https://stackoverflow.com/questions/65645992/how-to-implement-a-binary-trie-that-has-nodes-that-read-4-bits-at-a-time

Answer 1

What you describe is a radix trie base 16. By extracting 4 bits from your key, you get a number between 0 and 15 (inclusive). You can use that number to index into your node:

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;
}