If you were stuck on a desert island with just one data structure, which would it be and why?
This is a silly but fun question, and after giving it some thought, my answer most likely shouldn’t surprise most readers: A balanced binary search tree. Taking a look at my article index, it’s clear that Red/Black tree’s are an a subject I’ve spent a lot of time reviewing. But why would i choose it as my go-to structure on a desert island?
Simple: adaptivity. A binary search tree can be repurposed to serve A LOT of different functions, and a self balancing binary search tree will allow those functions to be completed in a reasonable amount of time. What kind of repurposing can be done?
Here’s a short list of tasks that one could repurpose a Red/Black Tree in to serving:
- A map – It’s no secret that the STL and the Java standard Library use Red/Black Tree’s to implement std::map and TreeMap respectively. Indeed this is among what is probably the most common use for a red/black tree.
- A set – See above.
- A priority queue – by using the key field as priority and the value field for storing the item a red/black could efficiently implement a priority queue with all operations taking O(logN) performance through findMin/findMax, insert, and erase taking the place of peek(), push(), and pop().
- A regular queue – another example of manipulating the key field to manage oldest and newest additions to the tree.
- A stack – same as above, but in reverse. Essentially any data structure that requires ordered property can be emulated in a self balanced tree by manipulating the key.
- An O(n log n) sorting algorithm – Tree Sort! an in-order traversal of a binary search tree yields the items in sorted order.
And this is just scratching the surface, there are many, many more possible use cases where a red/black tree could come in handy.
