Elastic Binary Trees (2011)

For the problem this was designed for, what this is missing is an argument for why this is better than a heap with a last-resort ordering trivially added. (If you're not using this for a scheduler of course a heap doesn't make sense.)

Note that C padding can be unfortunate here; for some types (but not when `sizeof(key) == sizeof(pointer)`) it may make sense to pack `bit` (in the generic struct; this does not need a whole `int` even) and `key` (in the type-specific struct) into the same word. I think `bit` needs `bitsizeof(key) + bitsizeof(max_dups)` values, so you only need 7 bits (log2(64+64)) at most (hmm, that's almost small enough to try cramming into the low bits of the pointers again ...).

I forget if pointer-bit stuffing is actually defined in C, or if you should be using `uintptr_t`. Debugging is probably saner if you do regardless.

It appears that this is intended to be used intrusively (in which case the value also needs to think about padding), but this completely fails to use the appropriate vocabulary. In fact, I think that might be the only difference between this and a typical bit-oriented radix trie? If so, Wikipedia is completely correct to delete this, since in general any node-based container can be made intrusive quite trivially.

Using absolute indexes (against a known origin) is probably saner than relative-pointers if you have something simple enough, since it lacks the problem of moving/copying.

Despite those considerations, this is definitely worth reading if you're interested in data structures (unlike some articles that get posted occasionally, which can be blogspam or outright incorrect).

HN

Elastic Binary Trees (2011)

Elastic Binary Trees (2011)