ScapegoatTree.cs

usingSystem;
usingSystem.Collections.Generic;

namespaceDataStructures.ScapegoatTree;

/// <summary>
/// A scapegoat implementation class.
/// See https://en.wikipedia.org/wiki/Scapegoat_tree for more information about scapegoat tree.
/// </summary>
/// <typeparam name="TKey">The scapegoat tree key type.</typeparam>
publicclassScapegoatTree<TKey>whereTKey:IComparable
{
/// <summary>
/// Gets the α (alpha) value of the tree.
/// </summary>
publicdoubleAlpha{get;privateset;}

/// <summary>
/// Gets the root node of the tree.
/// </summary>
publicNode<TKey>?Root{get;privateset;}

/// <summary>
/// Gets the number of nodes in the tree.
/// </summary>
publicintSize{get;privateset;}

/// <summary>
/// Gets the maximal value of the tree Size since the last time the tree was completely rebuilt.
/// </summary>
publicintMaxSize{get;privateset;}

/// <summary>
/// Gets an event handler which will fire when tree is being balanced.
/// </summary>
publiceventEventHandler?TreeIsUnbalanced;

publicScapegoatTree()
:this(alpha:0.5,size:0)
{
}

publicScapegoatTree(doublealpha)
:this(alpha,size:0)
{
}

publicScapegoatTree(Node<TKey>node,doublealpha)
:this(alpha,size:node.GetSize())
{
Root=node;
}

publicScapegoatTree(TKeykey,doublealpha=0.5)
:this(alpha,size:1)
{
Root=newNode<TKey>(key);
}

privateScapegoatTree(doublealpha,intsize)
{
CheckAlpha(alpha);

Alpha=alpha;

Size=size;
MaxSize=size;
}

/// <summary>
/// Checks if current instance of the scapegoat tree is alpha weight balanced.
/// </summary>
/// <returns>True - if tree is alpha weight balanced. Otherwise, false.</returns>
publicboolIsAlphaWeightBalanced()
{
returnRoot?.IsAlphaWeightBalanced(Alpha)??true;
}

/// <summary>
/// Check if any node in the tree has specified key value.
/// </summary>
/// <param name="key">Key value.</param>
/// <returns>Returns true if node exists, false if not.</returns>
publicboolContains(TKeykey)
{
returnSearch(key)!=null;
}

/// <summary>
/// Searches current instance of the scapegoat tree for specified key.
/// </summary>
/// <param name="key">Key value.</param>
/// <returns>Node with the specified key or null.</returns>
publicNode<TKey>?Search(TKeykey)
{
if(Root==null)
{
returnnull;
}

varcurrent=Root;

while(true)
{
varresult=current.Key.CompareTo(key);

switch(result)
{
case0:
returncurrent;
case>0whencurrent.Left!=null:
current=current.Left;
break;
case<0whencurrent.Right!=null:
current=current.Right;
break;
default:
returnnull;
}
}
}

/// <summary>
/// Inserts a new key into current instance of the scapegoat tree. Rebuilds tree if it's unbalanced.
/// </summary>
/// <param name="key">Key value.</param>
/// <returns>True - if insertion is successful, false - if the key is already present in the tree.</returns>
publicboolInsert(TKeykey)
{
varnode=newNode<TKey>(key);

if(Root==null)
{
Root=node;

UpdateSizes();

returntrue;
}

varpath=newStack<Node<TKey>>();

varcurrent=Root;

varfound=false;

while(!found)
{
path.Push(current);

varresult=current.Key.CompareTo(node.Key);

switch(result)
{
case<0whencurrent.Right!=null:
current=current.Right;
continue;
case<0:
current.Right=node;
found=true;
break;
case>0whencurrent.Left!=null:
current=current.Left;
continue;
case>0:
current.Left=node;
found=true;
break;
default:
returnfalse;
}
}

UpdateSizes();

if(path.Count>Root.GetAlphaHeight(Alpha))
{
TreeIsUnbalanced?.Invoke(this,EventArgs.Empty);

BalanceFromPath(path);

MaxSize=Math.Max(MaxSize,Size);
}

returntrue;
}

/// <summary>
/// Removes the specified key from the current instance of the scapegoat tree. Rebuilds tree if it's unbalanced.
/// </summary>
/// <param name="key">Key value.</param>
/// <returns>True - if key was successfully removed, false - if the key wasn't found in the tree.</returns>
publicboolDelete(TKeykey)
{
if(Root==null)
{
returnfalse;
}

if(Remove(Root,Root,key))
{
Size--;

if(Root!=null&&Size<Alpha*MaxSize)
{
TreeIsUnbalanced?.Invoke(this,EventArgs.Empty);

varlist=newList<Node<TKey>>();

Extensions.FlattenTree(Root,list);

Root=Extensions.RebuildFromList(list,0,list.Count-1);

MaxSize=Size;
}

returntrue;
}

returnfalse;
}

/// <summary>
/// Clears the tree.
/// </summary>
publicvoidClear()
{
Size=0;
MaxSize=0;
Root=null;
}

/// <summary>
/// Changes <see cref="Alpha"/> value to adjust balancing.
/// </summary>
/// <param name="value">New alpha value.</param>
publicvoidTune(doublevalue)
{
CheckAlpha(value);
Alpha=value;
}

/// <summary>
/// Searches for a scapegoat node in provided stack.
/// </summary>
/// <param name="path">Stack instance with nodes, starting with root node.</param>
/// <returns>Scapegoat node with its parent node. Parent can be null if scapegoat node is root node.</returns>
/// <exception cref="ArgumentException">Thrown if path stack is empty.</exception>
/// <exception cref="InvalidOperationException">Thrown if scapegoat wasn't found.</exception>
public(Node<TKey>?Parent,Node<TKey>Scapegoat)FindScapegoatInPath(Stack<Node<TKey>>path)
{
if(path.Count==0)
{
thrownewArgumentException("The path collection should not be empty.",nameof(path));
}

vardepth=1;

while(path.TryPop(outvarnext))
{
if(depth>next.GetAlphaHeight(Alpha))
{
returnpath.TryPop(outvarparent)?(parent,next):(null,next);
}

depth++;
}

thrownewInvalidOperationException("Scapegoat node wasn't found. The tree should be unbalanced.");
}

privatestaticvoidCheckAlpha(doublealpha)
{
if(alphais<0.5 or >1.0)
{
thrownewArgumentException("The alpha parameter's value should be in 0.5..1.0 range.",nameof(alpha));
}
}

privateboolRemove(Node<TKey>?parent,Node<TKey>?node,TKeykey)
{
if(nodeisnull||parentisnull)
{
returnfalse;
}

varcompareResult=node.Key.CompareTo(key);

if(compareResult>0)
{
returnRemove(node,node.Left,key);
}

if(compareResult<0)
{
returnRemove(node,node.Right,key);
}

Node<TKey>?replacementNode;

// Case 0: Node has no children.
// Case 1: Node has one child.
if(node.Leftisnull||node.Rightisnull)
{
replacementNode=node.Left??node.Right;
}

// Case 2: Node has two children. (This implementation uses the in-order predecessor to replace node.)
else
{
varpredecessorNode=node.Left.GetLargestKeyNode();
Remove(Root,Root,predecessorNode.Key);
replacementNode=newNode<TKey>(predecessorNode.Key)
{
Left=node.Left,
Right=node.Right,
};
}

// Replace the relevant node with a replacement found in the previous stages.
// Special case for replacing the root node.
if(node==Root)
{
Root=replacementNode;
}
elseif(parent.Left==node)
{
parent.Left=replacementNode;
}
else
{
parent.Right=replacementNode;
}

returntrue;
}

privatevoidBalanceFromPath(Stack<Node<TKey>>path)
{
var(parent,scapegoat)=FindScapegoatInPath(path);

varlist=newList<Node<TKey>>();

Extensions.FlattenTree(scapegoat,list);

vartree=Extensions.RebuildFromList(list,0,list.Count-1);

if(parent==null)
{
Root=tree;
}
else
{
varresult=parent.Key.CompareTo(tree.Key);

if(result<0)
{
parent.Right=tree;
}
else
{
parent.Left=tree;
}
}
}

privatevoidUpdateSizes()
{
Size+=1;
MaxSize=Math.Max(Size,MaxSize);
}
}