Ever felt like AVL trees are too strict and Red-Black trees are way too picky? Enter the Scapegoat Tree—a balanced binary search tree that punishes misbehaving nodes only when necessary.
I decided to implement one in C++26, complete with Python bindings, because sometimes the best learning comes from building things yourself—and because, honestly, they’re underrated and cool.
🚀 Features
- Automatic α-Weight balancing
- Insert, delete, search—all optimized
- Compute sum in range, retrieve values in range, find k-th smallest element
- Forward iterator support (yes,
for(auto x : tree)works!) - Undo/Redo system
- Tree merging with duplicate handling
- Custom data structures: Vector, Queue, Stack
- Terminal UI for interactive exploration
Basically, it’s the Swiss Army knife of BSTs.
💻 How to Use
git clone https://github.com/OmarAhmedTHE25th/ScapeGoatTree
cd ScapeGoatTree/CPP
# Build and run your examples
Python bindings are available for quick prototyping or testing.
🛠 Why It’s Cool
- Minimal STL usage—everything is built from scratch
- Clean API and operator overloading for intuitive syntax
- Extensive testing and interactive documentation available
Check out the full API docs (https://omarahmedthe25th.github.io).
🔗 Get Involved
Open an issue, submit a PR, or just try it out! I’d love to see how others use the Scapegoat Tree in real projects.
https://github.com/OmarAhmedTHE25th/ScapeGoatTree
Tags: C++, data-structures, algorithms, trees, open-source, Python
Top comments (0)