Conversation

Modern computers do not quite work in the way most people think.

Quote Tweet

Jul 3, 2019

Attention CSEd Twitter: While Big-O matters, the constant-factors involved in things like cache-hit rate are at least as important. If you're teaching balanced-binary-trees for any reason other than tradition, I'd love to chat.

Daniel Micay

@DanielMicay

Replying to

@halvarflake

I strongly disagree with the implication that teaching self-balancing binary search trees isn't useful though. B-trees are one of the most cache friendly data structures to the point that they're broadly used on storage and it's natural to learn as a follow-up to red-black trees.

1:00 AM · Jul 5, 2019Twitter Web Client

Replying to

and

The time complexity of these data structures does matter a lot and it only takes a few dozen elements to start beating a vector. Constant factors matter a lot too, but it doesn't make the time complexity unimportant. Ordered data is a big part of providing good data locality too.

Replying to

and

Red-black trees are a bad choice in the general case rather than using a B-tree or the special case of generating the map / set once rather than using a sorted vector. However, they do have a crucial use case for intrusive data structures for avoiding dynamic allocation/failure.

Show replies