My Data Structure: Bit-indexed Trie

Revision en7, by chromate00, 2022-09-01 10:26:56

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

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