A gentle introduction to Data Structure Trees
summary
Covers fundamentals and concrete tradeoffs: arrays and linked lists give constant-time access for small datasets but scale poorly, while binary search trees deliver average O(log n) search/insert/delete and degrade to O(n) when unbalanced. Includes runnable Ruby code for node insert/search using recursion and ternary operators, demonstrates why self‑balancing trees matter, and explains AVL rotations, splay trees (move accessed node to root for caches) and B‑trees for database indexing and disk‑resident data.
AI-written summary · about
chapters (5)
- 0:00Start
- 9:29Big O notation is the language we use for talking about how long an algorithm takes to run.
- 13:19Binary Tree?
- 22:44Binary Search Trees only work best when the tree is balanced..
- 23:31Self-Balancing Trees?
related talks
20mAlternative Data Structures in Ruby
38mAlgorithms: CLRS in Ruby
35mChanging the Unchangeable: The Hows and Whys of Immutable Data Structures
27mReimplementing Ruby's Hash
34mBeyond the language. An introduction to algorithms.
32mStupid Ruby Tricks
37mExploring Graphs with Ruby
42mRopes: An Alternative to Ruby's Strings