This page is due for review. Re-read the key points and answer the self-check questions before recording your video.
Algorithms · Hub
Trees
Six tree structures, from the basic vocabulary to the trees inside databases. Binary search trees keep values ordered for $O(h)$ search; AVL and B-trees keep $h$ small; heaps keep only the minimum or maximum on top.
Why it matters: the height of a tree is the cost of almost every operation on it. Every structure here is a different trick for keeping that height near $\log n$.
5 random questions mixed from all six tree pages.
Mixed review
Answer each one out loud before opening the sample answer.
flowchart TD
A{"What do you need?"} -->|"only the smallest or largest, fast"| H{"Smallest or largest?"}
H -->|smallest| MIN["Min-heap"]
H -->|largest| MAX["Max-heap"]
A -->|"ordered keys: search, ranges, sorted output"| B{"Data on disk, millions of keys?"}
B -->|yes| BT["B-tree"]
B -->|"no, in memory"| C{"Need a worst-case guarantee?"}
C -->|yes| AVL["AVL tree"]
C -->|"no, input is random"| BST["Binary search tree"]
A -->|"just a hierarchy, no ordering"| BIN["Binary tree basics"]
Key points
Operations cost $O(h)$ on search trees because they follow one root-to-leaf path.
A plain BST can become a chain because nothing stops sorted input from always going the same way.
AVL trees guarantee $O(\log n)$ because rotations keep sibling heights within one of each other.
Heaps make the min or max $O(1)$ because they only order parents against children, which is cheaper to maintain than full order.
B-trees suit disks because many keys per node make the tree just a few levels deep.