This (quite sudden) post is about a data structure I have came up with in one day in bed, and this won't be a full series(I am yet a student, which means I don't have time to invent data structures all day and all night). Still, Thinking about this, I thought it would be a good idea to cover it on its own post. So here we are.

Concept

The traditional bit trie uses one leaf node for one number, and every leaf node has same depth. but about this, I thought — why? "Do we really have to use $$$32$$$ zeroes, just to represent a single zero? Heck no. There has to be a better way." And this is where I came up with this idea.

Instead of using the same old left-right child, let's use up to $$$l \leq depth$$$ children for one node. $$$l$$$ is the suffix part when each node represents a prefix. and then, we connect all prefixes that have exactly $$$1$$$ set bit after this prefix to this node. for example, under $$$1000_2$$$ comes $$$1100_2$$$, $$$1010_2$$$, $$$1001_2$$$. $$$0$$$ here has two meanings, before the last $$$1$$$ (LSB), it means a definite $$$0$$$ bit, while after it, it means there can be additional children under this node, but in this current node it represents the $$$0$$$ bit itself. This means that the node denoted as $$$1000_2$$$ has extra children ($$$1100_2$$$ and etc), but itself, it represents $$$1000_2$$$.

The Important Detail

At this moment, you should be wondering, how do we distinguish the node for the number $$$10000_2$$$ and the prefix $$$1\text{xxxx}_2$$$? They use the same node after all. My conclusion? You don't need to. To do this, you can just save the size (amount of elements) of the subtree. Now, let us denote the size of the subtree of prefix $$$S$$$ as $$$n(S)$$$. then $$$n(1\text{xxxx}_2) = n(11\text{xxx}_2) + n(101\text{xx}_2) + \ldots + n(10000_2)$$$ applies. So you can just traverse the child nodes one by one, and the rest is the number itself.