Sunday 10 September 2017

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.

Read the full article here by Julia Evans

No comments: