An AVL Tree in C# is a specialized Binary Search Tree that improves the worst-case running time by self-balancing. Since an AVL Tree is a specialized Binary Tree, the AVL Tree class is built upon the C# Binary Tree class.
//====================================================
//| Downloaded From |
//| Visual C# Kicks - http://www.vcskicks.com/ |
//| License - http://www.vcskicks.com/license.html |
//====================================================
using System;
using System.Collections.Generic;
using System.Text;
namespace CSKicksCollection.Trees
{
class AVLTreeNode<T> : BinaryTreeNode<T>
where T : IComparable
{
public AVLTreeNode(T value)
: base(value)
{
}
public new AVLTreeNode<T> LeftChild
{
get
{
return (AVLTreeNode<T>)base.LeftChild;
}
set
{
base.LeftChild = value;
}
}
public new AVLTreeNode<T> RightChild
{
get
{
return (AVLTreeNode<T>)base.RightChild;
}
set
{
base.RightChild = value;
}
}
public new AVLTreeNode<T> Parent
{
get
{
return (AVLTreeNode<T>)base.Parent;
}
set
{
base.Parent = value;
}
}
}
/// <summary>
/// AVL Tree data structure
/// </summary>
class AVLTree<T> : BinaryTree<T>
where T : IComparable
{
/// <summary>
/// Returns the AVL Node of the tree
/// </summary>
public new AVLTreeNode<T> Root
{
get
{
return (AVLTreeNode<T>)base.Root;
}
set
{
base.Root = value;
}
}
/// <summary>
/// Returns the AVL Node corresponding to the given value
/// </summary>
public new AVLTreeNode<T> Find(T value)
{
return (AVLTreeNode<T>)base.Find(value);
}
/// <summary>
/// Insert a value in the tree and rebalance the tree if necessary.
/// </summary>
public override void Add(T value)
{
AVLTreeNode<T> node = new AVLTreeNode<T>(value);
base.Add(node); //add normally
//Balance every node going up, starting with the parent
AVLTreeNode<T> parentNode = node.Parent;
while (parentNode != null)
{
int balance = this.getBalance(parentNode);
if (Math.Abs(balance) == 2) //-2 or 2 is unbalanced
{
//Rebalance tree
this.balanceAt(parentNode, balance);
}
parentNode = parentNode.Parent; //keep going up
}
}
/// <summary>
/// Removes a given value from the tree and rebalances the tree if necessary.
/// </summary>
public override bool Remove(T value)
{
AVLTreeNode<T> valueNode = this.Find(value);
return this.Remove(valueNode);
}
/// <summary>
/// Wrapper method for removing a node within the tree
/// </summary>
protected new bool Remove(BinaryTreeNode<T> removeNode)
{
return this.Remove((AVLTreeNode<T>)removeNode);
}
/// <summary>
/// Removes a given node from the tree and rebalances the tree if necessary.
/// </summary>
public bool Remove(AVLTreeNode<T> valueNode)
{
//Save reference to the parent node to be removed
AVLTreeNode<T> parentNode = valueNode.Parent;
//Remove the node as usual
bool removed = base.Remove(valueNode);
if (!removed)
{
return false; //removing failed, no need to rebalance
}
else
{
//Balance going up the tree
while (parentNode != null)
{
int balance = this.getBalance(parentNode);
if (Math.Abs(balance) == 1) //1, -1
{
break; //height hasn't changed, can stop
}
else if (Math.Abs(balance) == 2) //2, -2
{
//Rebalance tree
this.balanceAt(parentNode, balance);
}
parentNode = parentNode.Parent;
}
return true;
}
}
/// <summary>
/// Balances an AVL Tree node
/// </summary>
protected virtual void balanceAt(AVLTreeNode<T> node, int balance)
{
if (balance == 2) //right outweighs
{
int rightBalance = getBalance(node.RightChild);
if (rightBalance == 1 || rightBalance == 0)
{
//Left rotation needed
rotateLeft(node);
}
else if (rightBalance == -1)
{
//Right rotation needed
rotateRight(node.RightChild);
//Left rotation needed
rotateLeft(node);
}
}
else if (balance == -2) //left outweighs
{
int leftBalance = getBalance(node.LeftChild);
if (leftBalance == 1)
{
//Left rotation needed
rotateLeft(node.LeftChild);
//Right rotation needed
rotateRight(node);
}
else if (leftBalance == -1 || leftBalance == 0)
{
//Right rotation needed
rotateRight(node);
}
}
}
/// <summary>
/// Determines the balance of a given node
/// </summary>
protected virtual int getBalance(AVLTreeNode<T> root)
{
//Balance = right child's height - left child's height
return this.GetHeight(root.RightChild) - this.GetHeight(root.LeftChild);
}
/// <summary>
/// Rotates a node to the left within an AVL Tree
/// </summary>
protected virtual void rotateLeft(AVLTreeNode<T> root)
{
if (root == null)
{
return;
}
AVLTreeNode<T> pivot = root.RightChild;
if (pivot == null)
{
return;
}
else
{
AVLTreeNode<T> rootParent = root.Parent; //original parent of root node
bool isLeftChild = (rootParent != null) && rootParent.LeftChild == root; //whether the root was the parent's left node
bool makeTreeRoot = root.Tree.Root == root; //whether the root was the root of the entire tree
//Rotate
root.RightChild = pivot.LeftChild;
pivot.LeftChild = root;
//Update parents
root.Parent = pivot;
pivot.Parent = rootParent;
if (root.RightChild != null)
{
root.RightChild.Parent = root;
}
//Update the entire tree's Root if necessary
if (makeTreeRoot)
{
pivot.Tree.Root = pivot;
}
//Update the original parent's child node
if (isLeftChild)
{
rootParent.LeftChild = pivot;
}
else if (rootParent != null)
{
rootParent.RightChild = pivot;
}
}
}
/// <summary>
/// Rotates a node to the right within an AVL Tree
/// </summary>
protected virtual void rotateRight(AVLTreeNode<T> root)
{
if (root == null)
{
return;
}
AVLTreeNode<T> pivot = root.LeftChild;
if (pivot == null)
{
return;
}
else
{
AVLTreeNode<T> rootParent = root.Parent; //original parent of root node
bool isLeftChild = (rootParent != null) && rootParent.LeftChild == root; //whether the root was the parent's left node
bool makeTreeRoot = root.Tree.Root == root; //whether the root was the root of the entire tree
//Rotate
root.LeftChild = pivot.RightChild;
pivot.RightChild = root;
//Update parents
root.Parent = pivot;
pivot.Parent = rootParent;
if (root.LeftChild != null)
{
root.LeftChild.Parent = root;
}
//Update the entire tree's Root if necessary
if (makeTreeRoot)
{
pivot.Tree.Root = pivot;
}
//Update the original parent's child node
if (isLeftChild)
{
rootParent.LeftChild = pivot;
}
else if (rootParent != null)
{
rootParent.RightChild = pivot;
}
}
}
}
}