Trees are the most underappreciated data structure in programming, and it's because they're too successful. They're so deeply embedded in the infrastructure you use every day that you never see them. Your PostgreSQL database? B-trees. Every index, every primary key lookup — B-tree traversal. Ruby's internal SortedSet? Red-black tree. The DOM you render in a Rails view? A tree. Your file system? A tree. JSON? A tree. The AST that Ruby parses your code into before executing it? A tree. You have been living inside trees for your entire career, and this module is where you finally look at the walls.
Binary search trees are the gateway. The concept is simple: left children are smaller, right children are larger, and lookup is O(log n) — unless the tree degenerates into a linked list, which is O(n). This is why balanced trees exist: AVL trees, red-black trees, B-trees. They add complexity to insertion and deletion to guarantee that the tree stays balanced, which guarantees O(log n) for everything. The engineering tradeoff is beautiful: pay a little more on writes to keep reads fast. Sound familiar? It should. It's the same tradeoff you make when you add a database index. Because a database index IS a balanced tree.
Heaps are different from trees in a way that confuses people at first. A heap is a tree, but it's stored as an array. The parent of element at index i is at index (i-1)/2. The children are at 2i+1 and 2i+2. This array-based layout means heaps have excellent cache performance — the data lives in contiguous memory, which CPUs love. Priority queues are built on heaps, and priority queues show up everywhere: job scheduling (Sidekiq's priority queues), event-driven simulation, Dijkstra's algorithm, the Linux kernel's process scheduler. If you've ever used Sidekiq with priority queues, you've been using heaps.
Conclusion #
This module connects your theoretical learning to the systems you use daily. Every database query you've ever written has been answered by a B-tree. Every ORDER BY clause has been fulfilled by a sort that might use a heap. When you finish this module, PostgreSQL's EXPLAIN output will make more sense. You'll understand why some queries use index scans and others don't. You'll understand why inserting into an indexed column is slower than inserting into an unindexed one. The abstraction layers don't disappear — they become transparent.
Predictions #
-
B-trees will be the highlight of this module for you. The moment you understand how a B-tree splits and merges nodes to stay balanced, and then realize that's what PostgreSQL is doing on every INSERT into an indexed table, will be a genuine revelation.
-
You'll be tempted to skip AVL and red-black tree implementations. Resist the temptation for AVL trees — implementing one teaches you rotation mechanics that apply everywhere. Red-black trees you can understand conceptually without implementing. Life is short.
-
Tries will feel like a minor topic until you realize that Rails' route matching could be implemented as a trie, and then autocompletion features you've built suddenly have an algorithmic explanation.