The Desert Island Data Structure

mgcadmin 09-04-2022

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:

1. 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.
2. A set - See above.
3. 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().
4. A regular queue - another example of manipulating the key field to manage oldest and newest additions to the tree.
5. 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.
6. 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. 

---