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 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.
-
A Different Take on Merge Sort: Binary Search Trees?
-
Deleting Entries From Open-Address 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 In-order 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