#include <scapegoat_tree.hpp>

Classes
class	iterator

Public Member Functions
	ScapeGoatTree ()

	ScapeGoatTree (double alpha)

void	insert (T value)

void	insertBatch (const Vector< T > &values)

bool	deleteValue (T value)

void	deleteBatch (const Vector< T > &values)

bool	search (const T &key) const

TreeNode *	find_node (T &key) const

void	clear ()

void	undo ()

void	redo ()

T	sumInRange (T min, T max)

T	getMin ()

T	getMax ()

Vector< T >	valuesInRange (T min, T max)

T	getSuccessor (T value) const

T	kthSmallest (int k) const

std::pair< ScapeGoatTree, ScapeGoatTree >	split (T value)

int	updateSize (TreeNode *&node)

void	changeAlpha (const double alpha)

std::string	isBalanced () const

const TreeNode *	getRoot ()

iterator	begin ()

	ScapeGoatTree (const ScapeGoatTree &Otree)

	ScapeGoatTree (ScapeGoatTree &&other) noexcept

	~ScapeGoatTree ()

std::string	displayPreOrder ()

std::string	displayInOrder ()

std::string	displayPostOrder ()

std::string	displayLevels ()

bool	operator[] (T value) const

ScapeGoatTree	operator+ (const ScapeGoatTree &other) const

ScapeGoatTree &	operator= (const ScapeGoatTree &other)

ScapeGoatTree &	operator= (ScapeGoatTree &&other) noexcept

ScapeGoatTree &	operator= (int value)

bool	operator== (const ScapeGoatTree &tree) const

bool	operator!= (const ScapeGoatTree &tree) const

bool	operator! () const

void	operator+ (const T &value)

bool	operator- (const T &value)

bool	operator-= (const T &value)

void	operator+= (const T &value)

Static Public Member Functions
static iterator	end ()

Private Types
using	TreeNode = Node< T >

Private Member Functions
TreeNode *	findTraitor (TreeNode *node)

TreeNode *	rebuildTree (int start, int end, TreeNode parent_node, T array)

void	inorderTraversal (const TreeNode node, int &i, T &array) const

void	preorderTraversal (const TreeNode *node)

void	displayPreOrder (const TreeNode *node, std::ostream &os)

void	displayInOrder (const TreeNode *node, std::ostream &os)

void	displayPostOrder (const TreeNode *node, std::ostream &os)

int	getThreshold () const

void	DeletionRebuild ()

bool	areTreesEqual (const TreeNode n1, const TreeNode n2) const

void	restructure_subtree (TreeNode *newNode)

T	sumHelper (TreeNode *node, T min, T max)

void	rangeHelper (TreeNode *node, T min, T max, Vector< T > &range)

T	kthSmallestHelper (TreeNode *node, int k) const

Static Private Member Functions
static int	findH (const TreeNode *node)

static unsigned int	countN (const TreeNode *node)

static void	postorderTraversal (const TreeNode *node)

static TreeNode *	findSuccessor (TreeNode *node)

Private Attributes
TreeNode *	root {}

int	nNodes {}

int	rebuildCount = 0

Stack< Command< T > >	undoStack

Stack< Command< T > >	redoStack

bool	isUndoing = false

int	max_nodes = 0

double	ALPHA = 2.0/3.0

Member Typedef Documentation

◆ TreeNode

template<typename T >

using ScapeGoatTree< T >::TreeNode = Node<T>

private

Constructor & Destructor Documentation

◆ ScapeGoatTree() [1/4]

template<typename T >

ScapeGoatTree< T >::ScapeGoatTree ( )

default

Default constructor for an empty Scapegoat Tree.

◆ ScapeGoatTree() [2/4]

template<typename T >

ScapeGoatTree< T >::ScapeGoatTree ( double alpha )

◆ ScapeGoatTree() [3/4]

template<typename T >

ScapeGoatTree< T >::ScapeGoatTree ( const ScapeGoatTree< T > & Otree )

Copy constructor for deep copying another ScapeGoatTree.

◆ ScapeGoatTree() [4/4]

template<typename T >

ScapeGoatTree< T >::ScapeGoatTree ( ScapeGoatTree< T > && other )

noexcept

Move constructor for transferring ownership from another ScapeGoatTree.

◆ ~ScapeGoatTree()

template<typename T >

ScapeGoatTree< T >::~ScapeGoatTree ( )

Destructor that cleans up all nodes in the tree.

Member Function Documentation

◆ areTreesEqual()

template<typename T >

bool ScapeGoatTree< T >::areTreesEqual	(	const TreeNode *	n1,
		const TreeNode *	n2
	)		const

private

Compares two subtrees for structural and value equality.

◆ begin()

template<typename T >

ScapeGoatTree< T >::iterator ScapeGoatTree< T >::begin ( )

◆ changeAlpha()

template<typename T >

void ScapeGoatTree< T >::changeAlpha ( const double alpha )

inline

◆ clear()

template<typename T >

void ScapeGoatTree< T >::clear ( )

Removes all nodes from the tree and resets its state.

◆ countN()

template<typename T >

unsigned int ScapeGoatTree< T >::countN ( const TreeNode * node )

staticprivate

Counts the total number of nodes in the subtree rooted at the given node.

◆ deleteBatch()

template<typename T >

void ScapeGoatTree< T >::deleteBatch ( const Vector< T > & values )

Removes multiple values from a Vector from the tree.

◆ deleteValue()

template<typename T >

bool ScapeGoatTree< T >::deleteValue ( T value )

Removes a value from the tree and maintains balance if needed.

◆ DeletionRebuild()

template<typename T >

void ScapeGoatTree< T >::DeletionRebuild ( )

private

Checks if a rebuild is needed after a deletion and performs it if necessary.

◆ displayInOrder() [1/2]

template<typename T >

std::string ScapeGoatTree< T >::displayInOrder ( )

Returns a string representing the tree in in-order traversal.

◆ displayInOrder() [2/2]

template<typename T >

void ScapeGoatTree< T >::displayInOrder	(	const TreeNode *	node,
		std::ostream &	os
	)

private

Formats the tree in in-order.

◆ displayLevels()

template<typename T >

std::string ScapeGoatTree< T >::displayLevels ( )

Returns a string representing the tree in level-order traversal.

◆ displayPostOrder() [1/2]

template<typename T >

std::string ScapeGoatTree< T >::displayPostOrder ( )

Returns a string representing the tree in post-order traversal.

◆ displayPostOrder() [2/2]

template<typename T >

void ScapeGoatTree< T >::displayPostOrder	(	const TreeNode *	node,
		std::ostream &	os
	)

private

Formats the tree in post-order.

◆ displayPreOrder() [1/2]

template<typename T >

std::string ScapeGoatTree< T >::displayPreOrder ( )

Returns a string representing the tree in pre-order traversal.

◆ displayPreOrder() [2/2]

template<typename T >

void ScapeGoatTree< T >::displayPreOrder	(	const TreeNode *	node,
		std::ostream &	os
	)

private

Formats the tree in pre-order.

◆ end()

template<typename T >

ScapeGoatTree< T >::iterator ScapeGoatTree< T >::end ( )

static

◆ find_node()

template<typename T >

ScapeGoatTree< T >::TreeNode * ScapeGoatTree< T >::find_node ( T & key ) const

◆ findH()

template<typename T >

int ScapeGoatTree< T >::findH ( const TreeNode * node )

staticprivate

Calculates the height of a given node in the tree.

◆ findSuccessor()

template<typename T >

ScapeGoatTree< T >::TreeNode * ScapeGoatTree< T >::findSuccessor ( TreeNode * node )

staticprivate

◆ findTraitor()

template<typename T >

ScapeGoatTree< T >::TreeNode * ScapeGoatTree< T >::findTraitor ( TreeNode * node )

private

Finds the highest node that violates the alpha-weight-balance property.

◆ getMax()

template<typename T >

T ScapeGoatTree< T >::getMax ( )

◆ getMin()

template<typename T >

T ScapeGoatTree< T >::getMin ( )

◆ getRoot()

template<typename T >

const ScapeGoatTree< T >::TreeNode * ScapeGoatTree< T >::getRoot ( )

Returns a pointer to the root node of the tree.

◆ getSuccessor()

template<typename T >

T ScapeGoatTree< T >::getSuccessor ( T value ) const

◆ getThreshold()

template<typename T >

int ScapeGoatTree< T >::getThreshold ( ) const

inlineprivate

Calculates the maximum allowed height before a rebuild is triggered.

◆ inorderTraversal()

template<typename T >

void ScapeGoatTree< T >::inorderTraversal	(	const TreeNode *	node,
		int &	i,
		T *&	array
	)		const

private

Performs an in-order traversal to populate a sorted array with node values.

◆ insert()

template<typename T >

void ScapeGoatTree< T >::insert ( T value )

Inserts a new value into the tree and maintains balance if needed.

◆ insertBatch()

template<typename T >

void ScapeGoatTree< T >::insertBatch ( const Vector< T > & values )

Inserts multiple values from a Vector into the tree.

◆ isBalanced()

template<typename T >

std::string ScapeGoatTree< T >::isBalanced ( ) const

Returns a string report indicating if the tree is currently balanced.

◆ kthSmallest()

template<typename T >

T ScapeGoatTree< T >::kthSmallest ( int k ) const

◆ kthSmallestHelper()

template<typename T >

T ScapeGoatTree< T >::kthSmallestHelper	(	TreeNode *	node,
		int	k
	)		const

private

◆ operator!()

template<typename T >

bool ScapeGoatTree< T >::operator! ( ) const

Checks if the tree is empty.

◆ operator!=()

template<typename T >

bool ScapeGoatTree< T >::operator!= ( const ScapeGoatTree< T > & tree ) const

Checks if two trees are not equal.

◆ operator+() [1/2]

template<typename T >

ScapeGoatTree< T > ScapeGoatTree< T >::operator+ ( const ScapeGoatTree< T > & other ) const

Creates a new tree containing elements from both trees.

Creates a new tree containing elements from both trees using linear merge.

if first is smaller then take it and increment the indicies for the merged list and the current array else if second is smaller then take it and increment the indicies for the merged list and the current array else (duplicates) take one of them and skip the duplicate in the other array

◆ operator+() [2/2]

template<typename T >

void ScapeGoatTree< T >::operator+ ( const T & value )

Overloaded plus operator for inserting a value.

◆ operator+=()

template<typename T >

void ScapeGoatTree< T >::operator+= ( const T & value )

Overloaded addition assignment operator for inserting a value.

◆ operator-()

template<typename T >

bool ScapeGoatTree< T >::operator- ( const T & value )

Overloaded minus operator for deleting a value.

◆ operator-=()

template<typename T >

bool ScapeGoatTree< T >::operator-= ( const T & value )

Overloaded subtraction assignment operator for deleting a value.

◆ operator=() [1/3]

template<typename T >

ScapeGoatTree< T > & ScapeGoatTree< T >::operator= ( const ScapeGoatTree< T > & other )

Assignment operator for deep copying.

Assignment operator for deep copying another tree.

◆ operator=() [2/3]

template<typename T >

ScapeGoatTree< T > & ScapeGoatTree< T >::operator= ( int value )

Clears the current tree and initializes it with a single value.

Clears the current tree if the assigned value is 0.

◆ operator=() [3/3]

template<typename T >

ScapeGoatTree< T > & ScapeGoatTree< T >::operator= ( ScapeGoatTree< T > && other )

noexcept

Move assignment operator.

Move assignment operator for transferring ownership.

◆ operator==()

template<typename T >

bool ScapeGoatTree< T >::operator== ( const ScapeGoatTree< T > & tree ) const

Checks if two trees are equal.

Checks if two trees are equal by comparing their structures and values.

◆ operator[]()

template<typename T >

bool ScapeGoatTree< T >::operator[] ( T value ) const

Overloaded subscript operator to search for a value in the tree.

◆ postorderTraversal()

template<typename T >

void ScapeGoatTree< T >::postorderTraversal ( const TreeNode * node )

staticprivate

Recursively deletes all nodes in the subtree using post-order traversal.

◆ preorderTraversal()

template<typename T >

void ScapeGoatTree< T >::preorderTraversal ( const TreeNode * node )

private

Performs a pre-order traversal for internal processing.

◆ rangeHelper()

template<typename T >

void ScapeGoatTree< T >::rangeHelper	(	TreeNode *	node,
		T	min,
		T	max,
		Vector< T > &	range
	)

private

◆ rebuildTree()

template<typename T >

ScapeGoatTree< T >::TreeNode * ScapeGoatTree< T >::rebuildTree	(	int	start,
		int	end,
		TreeNode *	parent_node,
		T *	array
	)

private

Recursively rebuilds a balanced BST from a sorted array of values.

◆ redo()

template<typename T >

void ScapeGoatTree< T >::redo ( )

Redo the last undone operation. If the last undone operation was a batch, it redoes the entire batch.

◆ restructure_subtree()

template<typename T >

void ScapeGoatTree< T >::restructure_subtree ( TreeNode * newNode )

private

Initiates a subtree rebuild starting from the scapegoat node.

◆ search()

template<typename T >

bool ScapeGoatTree< T >::search ( const T & key ) const

Searches for a specific value in the tree.

◆ split()

template<typename T >

std::pair< ScapeGoatTree< T >, ScapeGoatTree< T > > ScapeGoatTree< T >::split ( T value )

◆ sumHelper()

template<typename T >

T ScapeGoatTree< T >::sumHelper	(	TreeNode *	node,
		T	min,
		T	max
	)

private

◆ sumInRange()

template<typename T >

T ScapeGoatTree< T >::sumInRange	(	T	min,
		T	max
	)

◆ undo()

template<typename T >

void ScapeGoatTree< T >::undo ( )

Undo the last operation (insert or delete). If the last operation was a batch, it undoes the entire batch.

◆ updateSize()

template<typename T >

int ScapeGoatTree< T >::updateSize ( TreeNode *& node )

◆ valuesInRange()

template<typename T >

Vector< T > ScapeGoatTree< T >::valuesInRange	(	T	min,
		T	max
	)

Member Data Documentation

◆ ALPHA

template<typename T >

double ScapeGoatTree< T >::ALPHA = 2.0/3.0

private

◆ isUndoing

template<typename T >

bool ScapeGoatTree< T >::isUndoing = false

private

Flag to prevent operations triggered by undo/redo from being recorded. This avoids infinite recursion and keeps the undo history clean.

◆ max_nodes

template<typename T >

int ScapeGoatTree< T >::max_nodes = 0

private

◆ nNodes

template<typename T >

int ScapeGoatTree< T >::nNodes {}

private

◆ rebuildCount

template<typename T >

int ScapeGoatTree< T >::rebuildCount = 0

private

◆ redoStack

template<typename T >

Stack<Command<T> > ScapeGoatTree< T >::redoStack

private

Stack to store commands that have been undone and can be redone.

◆ root

template<typename T >

TreeNode* ScapeGoatTree< T >::root {}

private

◆ undoStack

template<typename T >

Stack<Command<T> > ScapeGoatTree< T >::undoStack

private

Stack to store commands that can be undone.

The documentation for this class was generated from the following files:

CPP/scapegoat_tree.hpp
CPP/scapegoat_tree.tpp

Classes

Public Member Functions

Static Public Member Functions

Private Types

Private Member Functions

Static Private Member Functions

Private Attributes

Member Typedef Documentation

◆ TreeNode

Constructor & Destructor Documentation

◆ ScapeGoatTree() [1/4]

◆ ScapeGoatTree() [2/4]

◆ ScapeGoatTree() [3/4]

◆ ScapeGoatTree() [4/4]

◆ ~ScapeGoatTree()

Member Function Documentation

◆ areTreesEqual()

◆ begin()

◆ changeAlpha()

◆ clear()

◆ countN()

◆ deleteBatch()

◆ deleteValue()

◆ DeletionRebuild()

◆ displayInOrder() [1/2]

◆ displayInOrder() [2/2]

◆ displayLevels()

◆ displayPostOrder() [1/2]

◆ displayPostOrder() [2/2]

◆ displayPreOrder() [1/2]

◆ displayPreOrder() [2/2]

◆ end()

◆ find_node()

◆ findH()

◆ findSuccessor()

◆ findTraitor()

◆ getMax()

◆ getMin()

◆ getRoot()

◆ getSuccessor()

◆ getThreshold()

◆ inorderTraversal()

◆ insert()

◆ insertBatch()

◆ isBalanced()

◆ kthSmallest()

◆ kthSmallestHelper()

◆ operator!()

◆ operator!=()

◆ operator+() [1/2]

◆ operator+() [2/2]

◆ operator+=()

◆ operator-()

◆ operator-=()

◆ operator=() [1/3]

◆ operator=() [2/3]

◆ operator=() [3/3]

◆ operator==()

◆ operator[]()

◆ postorderTraversal()

◆ preorderTraversal()

◆ rangeHelper()

◆ rebuildTree()

◆ redo()

◆ restructure_subtree()

◆ search()

◆ split()

◆ sumHelper()

◆ sumInRange()

◆ undo()

◆ updateSize()

◆ valuesInRange()

Member Data Documentation

◆ ALPHA

◆ isUndoing

◆ max_nodes

◆ nNodes

◆ rebuildCount

◆ redoStack

◆ root