The Problem
Why a Red-Black Tree
In a lot of RPGs, players collect potions that boost their stats — managing that inventory efficiently (sorting it, finding the strongest item) ends up being a real-world case for picking the right data structure. A plain list means re-sorting on every single change; an unbalanced BST can degrade to O(n) on the wrong input. A Red-Black Tree avoids both problems.
- O(log n) Guaranteed — Self-balancing via rotations and recoloring on every insert/delete, so performance never degrades as the inventory grows.
- Always Sorted — An in-order traversal returns potions already sorted by whichever stat is active — no separate sort step.
- Swappable Sort Key — Sort key is a
std::function, so switching between Total / Strength / Speed / Health rebuilds the ordering without duplicating logic.
How It Works
Under the hood
- Potion — Struct holding name, strength, speed, health, plus a
totalStats()helper. - Node — Tree node storing a Potion, its red/black color, and parent/left/right pointers.
- RedBlackTree —
insert,remove,search,inorder, andclear, with move semantics (copying is disabled on purpose — only one tree should own a given set of nodes). - Input Validation — Menu choices are numeric-only, potion names can't be empty, and stats are capped 0–100,000, all enforced before anything touches the tree.
- 6-Option Menu — Add, Display, Search, Delete, Clear, Change Sort, Quit — each with its own success/failure message.
Screenshots
A look inside
A console app doesn't screenshot well, so here's an actual run, straight from the README:
Welcome to The Potion Creation Station! Please select your choice!: 1 Potion name: Elixir of Vitality Strength: 4 Speed: 3 Health: 5 Potion added! --- Menu --- 1. Add Potion 2. Display All Potions 3. Search Potion by Name 4. Delete Potion by Name 5. Clear All Potions 6. Change Sorting Method 7. Quit Please select your choice!: 2 === Potion List === Potion of Giants - STR: 7, SPD: 5, HP: 6 (Total: 18) Elixir of Vitality - STR: 4, SPD: 3, HP: 5 (Total: 12) Please select your choice!: 4 Enter potion name: Elixir of Vitality This Potion has been sent into the depths of the archive, never to be found again!
Reflection
Challenges & what I learned
This was a solo project too, so here's what I personally ran into building a Red-Black Tree from scratch:
- Rotation & Recoloring — Getting insertion fix-ups right is the classic hard part of building a Red-Black Tree from scratch; one missed case and the whole balance guarantee breaks.
- Defensive Input Handling — Every single menu path had to survive non-numeric input, empty names, and out-of-range stats without crashing.
- Move Semantics in C++ — I added an explicit move constructor/assignment and deleted the copy constructor outright, just to keep tree ownership unambiguous.