The latest articles on Forem by Omar Ahmed Abdel Hameed (@omarahmedthe25th). https://forem.com/omarahmedthe25th https://media2.dev.to/dynamic/image/width=90,height=90,fit=cover,gravity=auto,format=auto/https:%2F%2Fdev-to-uploads.s3.amazonaws.com%2Fuploads%2Fuser%2Fprofile_image%2F3709849%2Fd426a465-90fb-4b7d-ba15-d0c9e9a6d4d0.jpg https://forem.com/omarahmedthe25th en Omar Ahmed Abdel Hameed Tue, 13 Jan 2026 21:22:36 +0000 https://forem.com/omarahmedthe25th/why-scapegoat-trees-are-underrated-and-my-c-implementation-5b7b https://forem.com/omarahmedthe25th/why-scapegoat-trees-are-underrated-and-my-c-implementation-5b7b <p>Ever felt like <strong>AVL trees are too strict</strong> and <strong>Red-Black trees are way too picky</strong>? Enter the <strong>Scapegoat Tree</strong>—a balanced binary search tree that punishes misbehaving nodes only when necessary.</p> <p>I decided to implement one in <strong>C++26</strong>, complete with <strong>Python bindings</strong>, because sometimes the best learning comes from building things yourself—and because, honestly, they’re underrated and cool.</p> <h2> 🚀 Features </h2> <ul> <li><strong>Automatic α-Weight balancing</strong></li> <li>Insert, delete, search—all optimized</li> <li>Compute <strong>sum in range</strong>, retrieve <strong>values in range</strong>, find <strong>k-th smallest element</strong> </li> <li>Forward iterator support (yes, <code>for(auto x : tree)</code> works!)</li> <li>Undo/Redo system</li> <li>Tree merging with duplicate handling</li> <li>Custom data structures: Vector, Queue, Stack</li> <li>Terminal UI for interactive exploration</li> </ul> <p>Basically, it’s the <strong>Swiss Army knife of BSTs</strong>.</p> <h2> 💻 How to Use </h2> <div class="highlight js-code-highlight"> <pre class="highlight shell"><code>git clone https://github.com/OmarAhmedTHE25th/ScapeGoatTree <span class="nb">cd </span>ScapeGoatTree/CPP <span class="c"># Build and run your examples</span> </code></pre> </div> <p>Python bindings are available for quick prototyping or testing.</p> <h2> 🛠 Why It’s Cool </h2> <ul> <li>Minimal STL usage—everything is built from scratch</li> <li>Clean API and operator overloading for intuitive syntax</li> <li>Extensive testing and interactive documentation available</li> </ul> <p>Check out the full API docs (<a href="https://omarahmedthe25th.github.io" rel="noopener noreferrer">https://omarahmedthe25th.github.io</a>).</p> <h2> 🔗 Get Involved </h2> <p>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.<br> <a href="https://github.com/OmarAhmedTHE25th/ScapeGoatTree" rel="noopener noreferrer">https://github.com/OmarAhmedTHE25th/ScapeGoatTree</a></p> <p><strong>Tags:</strong> <code>C++</code>, <code>data-structures</code>, <code>algorithms</code>, <code>trees</code>, <code>open-source</code>, <code>Python</code></p> datastructures cpp programming algorithms