Y-fast Trie

[AndreasMadsen]

This is also called the labeled successor problem which you have solved with something similar to the X-Fast Trie algorithm. You should know there is a better version called Y-Fast Trie which runs in O(log(log(bitfieldLength))) time and also uses O(n) space.

Y-Fast Trie is a fairly complex data structure which combines the X-Fast Trie with balanced binary search trees, so it is understandable if you don't want to implement it. I wouldn't :p

[mafintosh]

Thanks!

After reading up on Y-Fast I realized we can easily convert the current log(n) algorithm to a log(log(n)) by using the same technique that Y-Fast tries uses (I already have multiple binary trees internally).

[AndreasMadsen]

I already have multiple binary trees internally

Interesting, then it is definitely an alternative to X-Fast Trie. But yes any X-Fast Trie-like algorithm (like this) will work as the top-half of the Y-Fast Trie algorithm. Personally, I think balanced-binary-search-trees are rather annoying to implement, but if you already have those then it is "quite" easy.

PS: Splay-trees are my personal favorite, they are so strange :)

[max-mapper]

TFW danes speak english but its harder to understand than when they speak danish

[AndreasMadsen]

@mafintosh That's just because you haven't heard an algorithm discussion in danish, it involves some really funny translations :D (my first algorithm course was in danish).

edit: but nothing beats an abstract algebra discussion in danish, that gets really awkward (sexually) to the point where you have to switch to English (once, a professor of mine had to switch).

[AndreasMadsen]

By the way, if you really have found a non-hashing alternative to X-Fast Trie that supports updating then It might be paper-worth. As far as I know nobody has done it in log(·) worst-case time, just log(·) expected time.