Data Structures -> Balanced BSTs For Contests

Compare note for AVL, Red-Black, Scapegoat, Size Balanced Tree, and sibling textbook balancing families, explaining when PBDS or treap is still the cleaner contest retrieval route.

• Topic slug: data-structures/balanced-bsts
• Tutorial page: Open tutorial
• Ladder page: Open ladder
• Repo problems currently tagged here: 0
• Repo companion pages: 6
• Curated external problems: 3

Microtopics

• avl-balance-invariant
• red-black-invariants
• scapegoat-rebuilds
• size-balanced-tree-invariants
• ll-rr-lr-rl-rotations
• deterministic-balanced-bst
• library-style-ordered-container
• rebuild-based-balancing
• size-driven-balancing
• ordered-set-compare
• pbds-vs-treap-vs-avl
• duplicates-via-count

Learning Sources

Source	Type
OI Wiki AVL	Reference
OI Wiki Red-Black Tree	Reference
OI Wiki Scapegoat Tree	Reference
OI Wiki Size Balanced Tree	Reference
cppreference std::set	Primary
GCC PBDS manual	Primary

Practice Sources

Source	Type
Luogu P3369 - 普通平衡树	Practice
SPOJ ORDERSET	Practice
CSES Salary Queries	Practice

Repo Companion Material

Material	Type
Balanced BST hot sheet	quick reference
PBDS / Order Statistics Tree tutorial	compare point
Treap / Implicit Treap tutorial	compare point
Splay Tree tutorial	compare point
Balanced BSTs ladder	compare track
Heaps And Ordered Sets tutorial	adjacent tutorial

Curated External Problems

Compare

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
ORDERSET - Order Statistic Set	SPOJ	Medium	Balanced Bst Compare, Order Statistics	Data-Structure-Heavy; Classic	Ordered Set Invariant; Rank Queries; K-Th Queries	Rank-Query; Kth-Smallest; Compare-Route	Good compare practice after the AVL note because the same interface is often better served by PBDS than by hand-coding deterministic balancing.
Salary Queries	CSES	Medium	Balanced Bst Compare, Treap Compare	Data-Structure-Heavy; Query-Heavy	Duplicate Counts; Order Statistics; Pair-Key Wrapper	Duplicate-Safe-Wrapper; Range-Count; Compare-Route	A strong compare exercise showing that once split/merge by key or duplicate-safe wrappers matter, treap or PBDS is usually the cleaner in-repo route than AVL.

Implementation Challenge

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Luogu P3369 - 普通平衡树	Luogu	Hard	Avl, Red-Black, Scapegoat, Size-Balanced-Tree, Balanced Bst	Data-Structure-Heavy; Implementation-Heavy	Avl Balance Invariant; Rotations; Duplicate Counts	Rotations; Order-Statistics; Predecessor-Successor	A canonical implementation challenge if you want to hand-code AVL-style, Red-Black-style, Scapegoat-style, or SBT-style balancing and support the textbook ordered-set operation bundle end to end.

Repo Problems

No repo problem note is attached yet. Use the repo companion material above for this theory/process-heavy topic.

Regeneration

python3 scripts/generate_problem_catalog.py