Node.cs

usingSystem;

namespaceDataStructures.ScapegoatTree;

/// <summary>
/// Scapegoat tree node class.
/// </summary>
/// <typeparam name="TKey">Scapegoat tree node key type.</typeparam>
publicclassNode<TKey>whereTKey:IComparable
{
privateNode<TKey>?right;
privateNode<TKey>?left;

publicTKeyKey{get;}

publicNode<TKey>?Right
{
get=>right;
set
{
if(value!=null&&!value.IsGreaterThanOrSameAs(Key))
{
thrownewArgumentException("The value's key is smaller than or equal to node's right child's key.",nameof(value));
}

right=value;
}
}

publicNode<TKey>?Left
{
get=>left;
set
{
if(value!=null&&value.IsGreaterThanOrSameAs(Key))
{
thrownewArgumentException("The value's key is greater than or equal to node's left child's key.",nameof(value));
}

left=value;
}
}

publicNode(TKeykey)=>Key=key;

publicNode(TKeykey,Node<TKey>?right,Node<TKey>?left)
:this(key)
{
Right=right;
Left=left;
}

/// <summary>
/// Returns number of elements in the tree.
/// </summary>
/// <returns>Number of elements in the tree.</returns>
publicintGetSize()=>(Left?.GetSize()??0)+1+(Right?.GetSize()??0);

/// <summary>
/// Gets alpha height of the current node.
/// </summary>
/// <param name="alpha">Alpha value.</param>
/// <returns>Alpha height value.</returns>
publicdoubleGetAlphaHeight(doublealpha)=>Math.Floor(Math.Log(GetSize(),1.0/alpha));

publicNode<TKey>GetSmallestKeyNode()=>Left?.GetSmallestKeyNode()??this;

publicNode<TKey>GetLargestKeyNode()=>Right?.GetLargestKeyNode()??this;

/// <summary>
/// Checks if the current node is alpha weight balanced.
/// </summary>
/// <param name="a">Alpha value.</param>
/// <returns>True - if node is alpha weight balanced. If not - false.</returns>
publicboolIsAlphaWeightBalanced(doublea)
{
varisLeftBalanced=(Left?.GetSize()??0)<=a*GetSize();
varisRightBalanced=(Right?.GetSize()??0)<=a*GetSize();

returnisLeftBalanced&&isRightBalanced;
}

privateboolIsGreaterThanOrSameAs(TKeykey)
{
returnKey.CompareTo(key)>=0;
}
}