The Desert Island Data Structure
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 goto 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 inorder 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.

A Different Take on Merge Sort: Binary Search Trees?

Deleting Entries From OpenAddress Hash tables

Transform any Binary Search Tree in to a Sorted Linked List

From Regular Expressions To NFA by way of Abstract Syntax Trees: Thompsons Construction

Extending Sedgewick's explicit Digraph NFA

Iterative Inorder B Tree Traversal

Simple DB Migration with JDBC

Welcome to CodeBlahger, A Blahging Platform for Programmers.

The Façade Pattern

The Interpreter Pattern: Implementing Interpreters the OOP way
Leave A Comment