4 ms·
> anything better than a red-black tree Is there an equivalent data structure that has better worst-case time complexity than red-black tree?
by RossBencina 7y ago
> anything better than a red-black tree
Is there an equivalent data structure that has better worst-case time complexity than red-black tree?
- Dylan16807 7y agoThere are plenty of algorithms that are also O(logn) that are much faster in practice, because of how caches work.
- RossBencina 7y agoCould you name some please? I'm genuinely interested in learning of data structures with this property.
- Dylan16807 7y agoThe simplest one is a B tree. It's like a self-balancing binary tree, except that you put more than two children in each node. Same big-O, but faster by a big linear multiplier.
- vardump 7y agoIf the data is small enough (up to about n=100 magnitude), linear scan O(n) often beats asymptotically faster algorithms.