AugmentedBinarySearchTree.cs

usingSystem;
usingSystem.Collections.Generic;

namespaceDataStructures.Trees
{
/// <summary>
/// Binary Search Tree node.
/// This node extends the vanilla BSTNode class and adds an extra field to it for augmentation.
/// The BST now augments the subtree-sizes on insert, delete and get-height.
/// </summary>

publicclassBSTRankedNode<T>:BSTNode<T>whereT:IComparable<T>
{
privateint_subtreeSize=0;

publicBSTRankedNode():this(default(T),0,null,null,null){}
publicBSTRankedNode(Tvalue):this(value,0,null,null,null){}
publicBSTRankedNode(Tvalue,intsubtreeSize,BSTRankedNode<T>parent,BSTRankedNode<T>left,BSTRankedNode<T>right)
{
base.Value=value;
SubtreeSize=subtreeSize;
Parent=parent;
LeftChild=left;
RightChild=right;
}

// Size of subtrees
publicvirtualintSubtreeSize
{
get{returnthis._subtreeSize;}
set{this._subtreeSize=value;}
}

publicnewBSTRankedNode<T>Parent
{
get{return(BSTRankedNode<T>)base.Parent;}
set{base.Parent=value;}
}

publicnewBSTRankedNode<T>LeftChild
{
get{return(BSTRankedNode<T>)base.LeftChild;}
set{base.LeftChild=value;}
}

publicnewBSTRankedNode<T>RightChild
{
get{return(BSTRankedNode<T>)base.RightChild;}
set{base.RightChild=value;}
}
}


/******************************************************************************/


/// <summary>
/// Binary Search Tree Data Structure.
/// This is teh augmented version of BST. It is augmented to keep track of the nodes subtrees-sizes.
/// </summary>

publicclassAugmentedBinarySearchTree<T>:BinarySearchTree<T>whereT:IComparable<T>
{
/// <summary>
/// Override the Root node accessors.
/// </summary>
publicnewBSTRankedNode<T>Root
{
get{return(BSTRankedNode<T>)base.Root;}
set{base.Root=value;}
}


/// <summary>
/// CONSTRUCTOR.
/// Allows duplicates by default.
/// </summary>
publicAugmentedBinarySearchTree():base(){}

/// <summary>
/// CONSTRUCTOR.
/// If allowDuplictes is set to false, no duplicate items will be inserted.
/// </summary>
publicAugmentedBinarySearchTree(boolallowDuplicates):base(allowDuplicates){}


/// <summary>
/// Returns the height of the tree.
/// </summary>
/// <returns>Hight</returns>
publicoverrideintHeight
{
get
{
if(IsEmpty)
return0;

varcurrentNode=this.Root;
returnthis._getTreeHeight(currentNode);
}
}

/// <summary>
/// Returns the Subtrees size for a tree node if node exists; otherwise 0 (left and right nodes of leafs).
/// This is used in the recursive function UpdateSubtreeSize.
/// </summary>
/// <returns>The size.</returns>
/// <param name="node">BST Node.</param>
protectedint_subtreeSize(BSTRankedNode<T>node)
{
if(node==null)
return0;
returnnode.SubtreeSize;
}

/// <summary>
/// Updates the Subtree Size of a tree node.
/// Used in recusively calculating the Subtrees Sizes of nodes.
/// </summary>
/// <param name="node">BST Node.</param>
protectedvoid_updateSubtreeSize(BSTRankedNode<T>node)
{
if(node==null)
return;

node.SubtreeSize=_subtreeSize(node.LeftChild)+_subtreeSize(node.RightChild)+1;

_updateSubtreeSize(node.Parent);
}

/// <summary>
/// Remove the specified node.
/// </summary>
/// <param name="node">Node.</param>
/// <returns>>True if removed successfully; false if node wasn't found.</returns>
protectedbool_remove(BSTRankedNode<T>node)
{
if(node==null)
returnfalse;

varparent=node.Parent;

if(node.ChildrenCount==2)// if both children are present
{
varsuccessor=_findNextLarger(node);
node.Value=successor.Value;
return(true&&_remove(successor));
}

if(node.HasLeftChild)// if the node has only a LEFT child
{
base._replaceNodeInParent(node,node.LeftChild);
_updateSubtreeSize(parent);
_count--;

}
elseif(node.HasRightChild)// if the node has only a RIGHT child
{
base._replaceNodeInParent(node,node.RightChild);
_updateSubtreeSize(parent);
_count--;
}
else//this node has no children
{
base._replaceNodeInParent(node,null);
_updateSubtreeSize(parent);
_count--;
}

returntrue;
}

/// <summary>
/// Calculates the tree height from a specific node, recursively.
/// </summary>
/// <param name="node">Node</param>
/// <returns>Height of node's longest subtree</returns>
protectedint_getTreeHeight(BSTRankedNode<T>node)
{
if(node==null||node.HasChildren==false)
return0;

if(node.ChildrenCount==2)// it has both a right child and a left child
{
if(node.LeftChild.SubtreeSize>node.RightChild.SubtreeSize)
return(1+_getTreeHeight(node.LeftChild));
return(1+_getTreeHeight(node.RightChild));
}

if(node.HasLeftChild)
{
return(1+_getTreeHeight(node.LeftChild));
}

if(node.HasRightChild)
{
return(1+_getTreeHeight(node.RightChild));
}

// return-functions-fix
return0;
}

/// <summary>
/// Inserts an element to the tree
/// </summary>
/// <param name="item">Item to insert</param>
publicoverridevoidInsert(Titem)
{
varnewNode=newBSTRankedNode<T>(item);

// Invoke the super BST insert node method.
// This insert node recursively starting from the root and checks for success status (related to allowDuplicates flag).
// The functions increments count on its own.
varsuccess=base._insertNode(newNode);

if(success==false&&_allowDuplicates==false)
thrownewInvalidOperationException("Tree does not allow inserting duplicate elements.");

// Update the subtree-size for the newNode's parent.
_updateSubtreeSize(newNode.Parent);
}

/// <summary>
/// Inserts an array of elements to the tree.
/// </summary>
publicoverridevoidInsert(T[]collection)
{
if(collection==null)
thrownewArgumentNullException();

if(collection.Length>0)
for(inti=0;i<collection.Length;++i)
this.Insert(collection[i]);
}

/// <summary>
/// Inserts a list of elements to the tree.
/// </summary>
publicoverridevoidInsert(List<T>collection)
{
if(collection==null)
thrownewArgumentNullException();

if(collection.Count>0)
for(inti=0;i<collection.Count;++i)
this.Insert(collection[i]);
}

/// <summary>
/// Deletes an element from the tree
/// </summary>
/// <param name="item">item to remove.</param>
publicoverridevoidRemove(Titem)
{
if(IsEmpty)
thrownewException("Tree is empty.");

varnode=(BSTRankedNode<T>)base._findNode(this.Root,item);
boolstatus=_remove(node);
this._updateSubtreeSize(node.Parent);

// If the element was found, remove it.
if(status==false)
thrownewException("Item was not found.");
}

/// <summary>
/// Removes the min value from tree.
/// </summary>
publicoverridevoidRemoveMin()
{
if(IsEmpty)
thrownewException("Tree is empty.");

varnode=(BSTRankedNode<T>)_findMinNode(this.Root);
varparent=node.Parent;
this._remove(node);

// Update the subtrees-sizes
this._updateSubtreeSize(parent);
}

/// <summary>
/// Removes the max value from tree.
/// </summary>
publicoverridevoidRemoveMax()
{
if(IsEmpty)
thrownewException("Tree is empty.");

varnode=(BSTRankedNode<T>)_findMaxNode(this.Root);
varparent=node.Parent;
this._remove(node);

// Update the subtrees-sizes
this._updateSubtreeSize(parent);
}

/// <summary>
/// Returns the rank of the specified element
/// </summary>
/// <param name="item">Tree element</param>
/// <returns>Rank(item) if found; otherwise throws an exception.</returns>
publicvirtualintRank(Titem)
{
varnode=(BSTRankedNode<T>)base._findNode(this.Root,item);

if(node==null)
thrownewException("Item was not found.");
return(this._subtreeSize(node.LeftChild)+1);
}

}

}