Hypothetical Data Structure: Compressed Bit Trie (and possible methods of implementation)

Revision en2, by chromate00, 2022-09-01 03:11:46

This (quite sudden) post is about a hypothetical data structure I have thought of one day in my dreams, and this won't be a 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.

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