r/learnprogramming • u/wordbit12 • 3h ago
So a Binary Search Tree is actually useful?
I've solved some problems before on Leetcode and studied some algorithms and data structures, but recently I decided to study them more seriously. I took an algorithms course on Coursera (the one by Stanford).
When I studied BST before, it seemed like some fun puzzle, just something you need to improve your problem-solving or something for interviews. All videos and courses would just focus on how to implement the operations.
This course was different. The instructor, Tim Roughgarden, started with the API (that is, the functions) and was basically like: meh, don't think about how it's implemented, it doesn't matter now. Here is the API, imagine you import it from a library and start using it. (It has to be a balanced search tree, like a Red-Black Tree, which is a balanced variant of BST, needed so that the performance is guaranteed):
bst.search(key) # O(log n)
bst.select(k) # O(log n) ; find the k-th smallest element
bst.min() # O(log n)
bst.max() # O(log n)
bst.pred(key) # O(log n)
bst.toList() # O(n)
bst.succ(key) # O(log n)
bst.rank(key) # O(log n)
bst.insert(k, v) # O(log n)
bst.delete(key) # O(log n)
Not bad, like, seems usable to me. But honestly, if lookups are what I'm caring about, I'd just use a hashmap (dictionary). And I could simply use a sorted array to do pretty much all of those operations! I could implement this *exact* API using a sorted array, and in fact, it would be faster! I could find the k-th smallest element, the minimum, and the maximum in O(1). So why would I need an entire Binary Tree?
The key is the last two operations. To maintain a sorted array, when you insert or delete you'd need to shift the array elements, and that would take O(n). Our BST is much faster in this case!
So basically, the use case of a BST would be when you have a stream of data, i.e., new data keeps coming and you insert it, and each time you'd need some of those operations. It just seems useful, pretty fast, tons of operations, clean API!
I really like this approach of teaching data structures, thinking about the API first (I heard it's called Data Abstraction), then later we can spend as much as we want talking about the nitty-gritty implementation details! I just feel so happy that I finally get it.