AVLTree.cs

usingSystem;
usingSystem.Collections.Generic;

namespaceDataStructures.AVLTree;

/// <summary>
/// A simple self-balancing binary tree.
/// </summary>
/// <remarks>
/// An AVL tree is a self-balancing binary search tree (BST) named after
/// its inventors: Adelson, Velsky, and Landis. It is the first self-
/// balancing BST invented. The primary property of an AVL tree is that
/// the height of both child subtrees for any node only differ by one.
/// Due to the balanced nature of the tree, its time complexities for
/// insertion, deletion, and search all have a worst-case time
/// complexity of O(log n). Which is an improvement over the worst-case
/// O(n) for a regular BST.
/// See https://en.wikipedia.org/wiki/AVL_tree for more information.
/// Visualizer: https://visualgo.net/en/bst.
/// </remarks>
/// <typeparam name="TKey">Type of key for the tree.</typeparam>
publicclassAvlTree<TKey>
{
/// <summary>
/// Gets the number of nodes in the tree.
/// </summary>
publicintCount{get;privateset;}

/// <summary>
/// Comparer to use when comparing key values.
/// </summary>
privatereadonlyComparer<TKey>comparer;

/// <summary>
/// Reference to the root node.
/// </summary>
privateAvlTreeNode<TKey>?root;

/// <summary>
/// Initializes a new instance of the <see cref="AvlTree{TKey}"/>
/// class.
/// </summary>
publicAvlTree()
{
comparer=Comparer<TKey>.Default;
}

/// <summary>
/// Initializes a new instance of the <see cref="AvlTree{TKey}"/>
/// class using the specified comparer.
/// </summary>
/// <param name="customComparer">
/// Comparer to use when comparing keys.
/// </param>
publicAvlTree(Comparer<TKey>customComparer)
{
comparer=customComparer;
}

/// <summary>
/// Add a single node to the tree.
/// </summary>
/// <param name="key">Key value to add.</param>
publicvoidAdd(TKeykey)
{
if(rootisnull)
{
root=newAvlTreeNode<TKey>(key);
}
else
{
root=Add(root,key);
}

Count++;
}

/// <summary>
/// Add multiple nodes to the tree.
/// </summary>
/// <param name="keys">Key values to add.</param>
publicvoidAddRange(IEnumerable<TKey>keys)
{
foreach(varkeyinkeys)
{
Add(key);
}
}

/// <summary>
/// Remove a node from the tree.
/// </summary>
/// <param name="key">Key value to remove.</param>
publicvoidRemove(TKeykey)
{
root=Remove(root,key);
Count--;
}

/// <summary>
/// Check if given node is in the tree.
/// </summary>
/// <param name="key">Key value to search for.</param>
/// <returns>Whether or not the node is in the tree.</returns>
publicboolContains(TKeykey)
{
varnode=root;
while(nodeis not null)
{
varcompareResult=comparer.Compare(key,node.Key);
if(compareResult<0)
{
node=node.Left;
}
elseif(compareResult>0)
{
node=node.Right;
}
else
{
returntrue;
}
}

returnfalse;
}

/// <summary>
/// Get the minimum value in the tree.
/// </summary>
/// <returns>Minimum value in tree.</returns>
publicTKeyGetMin()
{
if(rootisnull)
{
thrownewInvalidOperationException("AVL tree is empty.");
}

returnGetMin(root).Key;
}

/// <summary>
/// Get the maximum value in the tree.
/// </summary>
/// <returns>Maximum value in tree.</returns>
publicTKeyGetMax()
{
if(rootisnull)
{
thrownewInvalidOperationException("AVL tree is empty.");
}

returnGetMax(root).Key;
}

/// <summary>
/// Get keys in order from smallest to largest as defined by the
/// comparer.
/// </summary>
/// <returns>Keys in tree in order from smallest to largest.</returns>
publicIEnumerable<TKey>GetKeysInOrder()
{
List<TKey>result=new();
InOrderWalk(root);
returnresult;

voidInOrderWalk(AvlTreeNode<TKey>?node)
{
if(nodeisnull)
{
return;
}

InOrderWalk(node.Left);
result.Add(node.Key);
InOrderWalk(node.Right);
}
}

/// <summary>
/// Get keys in the pre-order order.
/// </summary>
/// <returns>Keys in pre-order order.</returns>
publicIEnumerable<TKey>GetKeysPreOrder()
{
varresult=newList<TKey>();
PreOrderWalk(root);
returnresult;

voidPreOrderWalk(AvlTreeNode<TKey>?node)
{
if(nodeisnull)
{
return;
}

result.Add(node.Key);
PreOrderWalk(node.Left);
PreOrderWalk(node.Right);
}
}

/// <summary>
/// Get keys in the post-order order.
/// </summary>
/// <returns>Keys in the post-order order.</returns>
publicIEnumerable<TKey>GetKeysPostOrder()
{
varresult=newList<TKey>();
PostOrderWalk(root);
returnresult;

voidPostOrderWalk(AvlTreeNode<TKey>?node)
{
if(nodeisnull)
{
return;
}

PostOrderWalk(node.Left);
PostOrderWalk(node.Right);
result.Add(node.Key);
}
}

/// <summary>
/// Helper function to rebalance the tree so that all nodes have a
/// balance factor in the range [-1, 1].
/// </summary>
/// <param name="node">Node to rebalance.</param>
/// <returns>New node that has been rebalanced.</returns>
privatestaticAvlTreeNode<TKey>Rebalance(AvlTreeNode<TKey>node)
{
if(node.BalanceFactor>1)
{
if(node.Right!.BalanceFactor==-1)
{
node.Right=RotateRight(node.Right);
}

returnRotateLeft(node);
}

if(node.BalanceFactor<-1)
{
if(node.Left!.BalanceFactor==1)
{
node.Left=RotateLeft(node.Left);
}

returnRotateRight(node);
}

returnnode;
}

/// <summary>
/// Perform a left (counter-clockwise) rotation.
/// </summary>
/// <param name="node">Node to rotate about.</param>
/// <returns>New node with rotation applied.</returns>
privatestaticAvlTreeNode<TKey>RotateLeft(AvlTreeNode<TKey>node)
{
vartemp1=node;
vartemp2=node.Right!.Left;
node=node.Right;
node.Left=temp1;
node.Left.Right=temp2;

node.Left.UpdateBalanceFactor();
node.UpdateBalanceFactor();

returnnode;
}

/// <summary>
/// Perform a right (clockwise) rotation.
/// </summary>
/// <param name="node">Node to rotate about.</param>
/// <returns>New node with rotation applied.</returns>
privatestaticAvlTreeNode<TKey>RotateRight(AvlTreeNode<TKey>node)
{
vartemp1=node;
vartemp2=node.Left!.Right;
node=node.Left;
node.Right=temp1;
node.Right.Left=temp2;

node.Right.UpdateBalanceFactor();
node.UpdateBalanceFactor();

returnnode;
}

/// <summary>
/// Helper function to get node instance with minimum key value
/// in the specified subtree.
/// </summary>
/// <param name="node">Node specifying root of subtree.</param>
/// <returns>Minimum value in node's subtree.</returns>
privatestaticAvlTreeNode<TKey>GetMin(AvlTreeNode<TKey>node)
{
while(node.Leftis not null)
{
node=node.Left;
}

returnnode;
}

/// <summary>
/// Helper function to get node instance with maximum key value
/// in the specified subtree.
/// </summary>
/// <param name="node">Node specifying root of subtree.</param>
/// <returns>Maximum value in node's subtree.</returns>
privatestaticAvlTreeNode<TKey>GetMax(AvlTreeNode<TKey>node)
{
while(node.Rightis not null)
{
node=node.Right;
}

returnnode;
}

/// <summary>
/// Recursively function to add a node to the tree.
/// </summary>
/// <param name="node">Node to check for null leaf.</param>
/// <param name="key">Key value to add.</param>
/// <returns>New node with key inserted.</returns>
privateAvlTreeNode<TKey>Add(AvlTreeNode<TKey>node,TKeykey)
{
// Regular binary search tree insertion
varcompareResult=comparer.Compare(key,node.Key);
if(compareResult<0)
{
if(node.Leftisnull)
{
varnewNode=newAvlTreeNode<TKey>(key);
node.Left=newNode;
}
else
{
node.Left=Add(node.Left,key);
}
}
elseif(compareResult>0)
{
if(node.Rightisnull)
{
varnewNode=newAvlTreeNode<TKey>(key);
node.Right=newNode;
}
else
{
node.Right=Add(node.Right,key);
}
}
else
{
thrownewArgumentException(
$"Key \"{key}\" already exists in AVL tree.");
}

// Check all of the new node's ancestors for inbalance and perform
// necessary rotations
node.UpdateBalanceFactor();

returnRebalance(node);
}

/// <summary>
/// Recursive function to remove node from tree.
/// </summary>
/// <param name="node">Node to check for key.</param>
/// <param name="key">Key value to remove.</param>
/// <returns>New node with key removed.</returns>
privateAvlTreeNode<TKey>?Remove(AvlTreeNode<TKey>?node,TKeykey)
{
if(node==null)
{
thrownewKeyNotFoundException(
$"Key \"{key}\" is not in the AVL tree.");
}

// Normal binary search tree removal
varcompareResult=comparer.Compare(key,node.Key);
if(compareResult<0)
{
node.Left=Remove(node.Left,key);
}
elseif(compareResult>0)
{
node.Right=Remove(node.Right,key);
}
else
{
if(node.Leftisnull&&node.Rightisnull)
{
returnnull;
}

if(node.Leftisnull)
{
varsuccessor=GetMin(node.Right!);
node.Right=Remove(node.Right!,successor.Key);
node.Key=successor.Key;
}
else
{
varpredecessor=GetMax(node.Left!);
node.Left=Remove(node.Left!,predecessor.Key);
node.Key=predecessor.Key;
}
}

// Check all of the removed node's ancestors for rebalance and
// perform necessary rotations.
node.UpdateBalanceFactor();

returnRebalance(node);
}
}