My Data Structure: Bit-indexed Trie

Revision en13, by chromate00, 2022-09-01 19:02:49

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. Then, while the undetermined suffix (ex. the $\text{xxx}$ in $1\text{xxx}_2$) is, of course, undetermined, we can assume they are $0$ for the exact node the prefix exists on.

### 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.

#### History

Revisions

Rev. Lang. By When Δ Comment
en30 chromate00 2022-09-02 04:37:46 7 Tiny change: '(1)$, and he is correct. ' -> '(1)$, and they are correct. '
en29 chromate00 2022-09-02 04:37:10 25 Tiny change: '9-02] and told me t' -> '9-02] and [user:Keewrem] told me t' (published)
en28 chromate00 2022-09-02 04:36:38 5 Tiny change: '22-09-02] told me t' -> '22-09-02] and told me t' (saved to drafts)
en27 chromate00 2022-09-02 03:33:02 0 (published)
en26 chromate00 2022-09-02 03:32:43 208 (saved to drafts)
en25 chromate00 2022-09-01 21:14:22 0 (published)
en24 chromate00 2022-09-01 21:13:53 438
en23 chromate00 2022-09-01 21:06:50 24 Tiny change: 'functions.' -> 'functions.\n\n-----\n\n### Summary'
en22 chromate00 2022-09-01 21:05:33 375
en21 chromate00 2022-09-01 20:59:10 2 Tiny change: ' BI-Trie">\n~~~~~\nvoi' -> ' BI-Trie">~~~~~\nvoi'
en20 chromate00 2022-09-01 20:58:45 314
en19 chromate00 2022-09-01 20:48:47 969
en18 chromate00 2022-09-01 20:25:02 75
en17 chromate00 2022-09-01 20:24:25 74
en16 chromate00 2022-09-01 20:08:47 1082 Tiny change: '_2$. This toot node m' -> '_2$. This root node m'
en15 chromate00 2022-09-01 19:07:28 198
en14 chromate00 2022-09-01 19:04:59 69
en13 chromate00 2022-09-01 19:02:49 452
en12 chromate00 2022-09-01 18:53:40 134 Tiny change: '{xx}_2) + n(1001\text{x}_2) + n(10001_2) + n(10000' -> '{xx}_2) + \ldots + n(10000'
en11 chromate00 2022-09-01 18:51:08 1 Tiny change: 'n(10000_2).' -> 'n(10000_2)$.' en10 chromate00 2022-09-01 18:50:59 279 en9 chromate00 2022-09-01 18:45:29 38 Tiny change: '{xxxx}_2$?\n\n' -> '{xxxx}_2$? They use the same node after all.' en8 chromate00 2022-09-01 18:44:59 174 en7 chromate00 2022-09-01 10:26:56 2 Tiny change: 'last$1$(MSB), it me' -> 'last$1$(LSB), it me' en6 chromate00 2022-09-01 10:26:17 120 en5 chromate00 2022-09-01 10:23:13 14 Tiny change: 'se up to$32-l$children' -> 'se up to$l \leq depth\$ children'
en4 chromate00 2022-09-01 10:22:12 533
en3 chromate00 2022-09-01 07:41:44 307
en2 chromate00 2022-09-01 03:11:46 123
en1 chromate00 2022-09-01 01:52:09 427 Initial revision (saved to drafts)