5
Data structure: the treap!
source link: https://jvns.ca/blog/2017/09/09/data-structure--the-treap-/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Data structure: the treap!
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.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK