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.
19
58
224
Conversation
Replying to
I don't care if someone can implement a red-black tree, at all. But ordered O(log N) structures solve a lot of problems and candidates should understand their use.
1
3
Replying to
Sure. But they should also know that an unsorted vector is going to outperform for many input sizes, and *why*.
3
15
Pointer chasing to new allocations for “structural data” is one reason why set, map and list are bad. sorted vector is a good middle ground for larger set sizes and low insert frequency, (std::vector with std::lower_bound). Memory order is reduced to the “actual data”.
1
1
1
It should be noted that std::map and std::set are not representative of self-balancing search trees overall. They force an inefficient implementation for modern hardware due to the iterator invalidation guarantees. B-trees are a great data structure but the API doesn't allow it.
1
1
2
A good reason to use a red-black tree is for intrusive data structures where the nodes are going to be threaded through existing objects, often as a way of designing around avoiding dynamic allocation. It's a useful approach in memory allocators, kernels and robust libraries.
B-trees are ordered data structures providing O(log n) find, insert and delete while also having great data locality at the same time. The node size can be increased or decreased to tune performance. Great data locality is why they're so broadly used by databases / filesystems.
3
1
2
For storage, node size is tuned to match the storage block size. You could use those relatively massive nodes in-memory if you wanted, but you would usually want a significantly smaller node size. It's Rust's only standard ordered map/set for good reason: doc.rust-lang.org/std/collection.
1
1
2
Show replies