scapegoat_tree.hpp File Reference

Scapegoat Tree implementation. More...

#include <string>
#include <cmath>
#include "vector.hpp"
#include "stack.hpp"
#include "Node.hpp"
#include "scapegoat_tree.tpp"

Go to the source code of this file.

Classes
struct	Command< T >
class	ScapeGoatTree< T >
class	ScapeGoatTree< T >::iterator

Enumerations
enum class	OpType { Insert , Delete , BatchStart , BatchEnd }

Detailed Description

Scapegoat Tree implementation.

... DoxyFile

Enumeration Type Documentation

OpType

enum class OpType

strong

ScapeGoat Tree Implementation

A self-balancing BST that maintains balance through periodic rebuilding.

Key Properties:

• α-weight-balanced: No node's subtree is heavier than α × parent's subtree
• α = 2/3 for this implementation
• Height bound: h ≤ log₁.₅(n) where n = number of nodes

Time Complexity:

• Insert: O(log n) amortized, O(n) worst case during rebuild
• Delete: O(log n) amortized, O(n) worst case during rebuild
• Search: O(log n) worst case (tree stays balanced)

Space Complexity: O(n) for tree + O(n) temporary array during rebuild Represents the type of operation performed on the tree for undo/redo purposes.

Enumerator
Insert
Delete
BatchStart
BatchEnd