Here’s a quick sketch I did yesterday about a randomized data structure: the treap. It’s basically a really cool way to implement a balanced binary search tree. Kamal told me about it!
The main reason I know for sure this is useful is in case someone asks you to implement a balanced binary search tree in an interview. More seriously though – if you want to implement an ordered map (like C++’s std::map), then you probably want a balanced BST!
C++’s std::map is usually a red-black tree, but a treap performs just as well (in expected value) and the algorithms for insert/delete are way simpler.
Read the full article here by Julia Evans
No comments:
Post a Comment