Built on
search tree
Articles
DS
Data structure
Binary search tree
Smaller to the left, larger to the right: search, order and the k-th element in the tree's height, from log n to n.
O(h): from O(log n) to O(n)
2 problems
DS
Data structure
AVL tree
A search tree where the branch heights at a node differ by at most 1: height up to ~1.44·log₂ n.
O(log n) for search, insertion and deletion
2 problems
DS
Data structure
B-tree
A tree with hundreds of keys in a page-sized node: a search among a billion keys reads five pages.
O(log n) comparisons, O(log_B n) page reads
2 problems
DP
Technique
Interval DP
The state is an interval [i, j], the transition is where to cut it: search trees, matrix chain order, sawing.
O(n³)
2 problems
Problems
Often together
classic 4 tree 3 searching 3 range queries 3 databases 2 interviews 2 selection 1 sliding window 1 operating systems 1 external memory 1 cache-friendly 1 in production 1