Microsoft .Net has an AVL tree class SortetSet<T> but it is always nice to understand the origins of the logic behind.
What is an AVL tree
And AVL tree is much like a Balanced Binary Search Tree. A Binary Search Tree (BST) has the following properties:
- Each node has a value;
- Each node has a left node which stores only values of lesser value than the node's value.
- Each node has a right node which stores only values of greater value than the node's value
An AVL tree is a self-balancing BST with the following properties:
- The heights of the two children sub-trees of any node differ at most one.
- Search, Insert and Delete methods all take O(log n) time in both the average and worse cases
- Insert and Delete may require the tree to be re-balanced by one or more rotations.
Without further ado: the code
You will find comments in the code detailing the steps needed to balance and rotate nodes.
//define the binary Node class BinaryNode {
public int data { get; set; }
//This node will store nodes with lesser value than the data field
public BinaryNode left;
//this node will store nodes with greater values than the data field
public BinaryNode right;
//Initialize the Node
public BinaryNode(int data)
{
this.data = data;
left = null;
right = null;
visited = false;
}
}
//this class manages the AVL tree, as you can see is based on as BST class BinaryTree
{
public BinaryNode head; //the tree
//to keep track of how many nodes we have in the tree
public int counter;
public bool isBalanced()
{
int left = height(head.left);
int right = height(head.right);
//in a balanced tree the difference in height between
// the left sub-tree height and the right sub-tree it is at most one
return Math.Abs(left - right) <= 1 ? true : false;
}
public int height(BinaryNode n)
{
if (n == null)
{
//if the value is null, return -1 and the node will be subtracted from the total
return -1;
}
int theleft = height(n.left)+1;
int theright = height(n.right)+1;
//the height of a node is the MAX value of the sub-trees
return Math.Max(theleft , theright );
}
//Class Constructor
public BinaryTree(BinaryNode n)
{
head = n;
}
public BinaryNode Delete( BinaryNode root, BinaryNode n)
{
if (n == null | root == null)
{
return null;
}
if (n.data < root.data)
{
root.left = Delete(root.left, n);
}
if (n.data > root.data)
{
root.right = Delete(root.right, n);
}
// when deleting a node, then you need to shift Nodes around
if (root.data == n.data)f
{
if (root.left == null && root.right == null)
{
root = null;
return root;
}
else
{
// Rotate nodes
if (root.left == null)
{
BinaryNode temp = root;
root = root.right;
temp = null;
return root;
}
else if (root.right == null)
{
BinaryNode temp = root;
root = root.left;
temp = null;
}
else
{
//rotate to right?... but we may need to go check the depth..
BinaryNode min = GetMin(root.right);
root.data = min.data;
root.right = Delete(root.right,min);
}
}
}
return root;
}
//This function will return the lowest node in a sub-tree
private BinaryNode GetMin(BinaryNode root)
{
if (root.left == null)
{
return root;
}
return GetMin(root.left);
}
private int HeightDifference(BinaryNode Node)
{
return height(Node.left) - height(Node.right);
}
//Balancing a node
private BinaryNode Balance(BinaryNode Node)
{
// AVL Steps:
// 1.- Find the height difference between sub-trees
// 2.- If -1 <= difference <= 1 then you are good, otherwise, you need to rotate
// 3.- Nodes at the top have higher values than the bottom, so the root should store the highest
// height, while leaf nodes at bottom would store a height of 1
int heightDifference= HeightDifference(Node);
//if the balance factor is > 1 it means the left is deeper than the right
if (heightDifference> 1)
{
//if the node to the left is deeper, then rotate to the left twice
if (HeightDifference(Node.left) > 0 )
{
//rotate left left
Node = RotateLL(Node);
}
else //there is nothing under it
{
//rotate left - right
Node = RotateLR(Node);
}
}
else if (heightDifference< -1) // a negative value means the right is deeper than the left
{
//now let's check the depth of the right node
if (HeightDifference(Node.right) > 0) // the right is deeper lets rotate right then left
{
//rotate right - left
Node = RotateRL(Node);
}
else //there is nothing under
{
//rotate right - right
Node = RotateRR(Node);
}
}
return Node;
}
//Rotating Nodes, there are 4 cases: right-right, right-left, left-left and left-right
// right-right: all nodes are to the right of the parent, the pivot becomes the new parent and
// the original parent becomes the child of the pivot
// left-left: all nodes are to the left of the parent
// right-left: pivot is the right child of the parent
// left-right: pivot is the left child of the parent
private BinaryNode RotateRR(BinaryNode Node)
{
BinaryNode Pivot = Node.right;
Node.right = Pivot.left;
Pivot.left = Node;
return Pivot;
}
private BinaryNode RotateLL(BinaryNode Node)
{
BinaryNode Pivot = Node.left;
Node.left = (Pivot == null ? null : Pivot.right);
Pivot.right = Node;
return Pivot;
}
private BinaryNode RotateLR(BinaryNode Node)
{
BinaryNode Pivot = Node.left;
Node.left = RotateRR(Pivot);
return RotateLL(Node);
}
private BinaryNode RotateRL(BinaryNode Node)
{
BinaryNode Pivot = Node.right;
Node.right = RotateLL(Pivot);
return RotateRR(Node);
}
// Insert with balance
public void Insert(BinaryNode root, BinaryNode n)
{
if (root == null)
{
root = n;
counter++;
}
else
{
if (root.data > n.data)
{
if (root.left == null)
{
root.left = n;
counter++;
}
else
{
Insert(root.left, n);
//After inserting, then balance the tree
Balance(root.left);
}
}
else
{
if (root.right == null)
{
root.right = n;
counter++;
}
else
{
Insert(root.right, n);
//After inserting, then balance the tree
Balance(root.right);
}
}
}
}
// This method searches for the value in the tree
public BinaryNode Find(BinaryNode root, BinaryNode n)
{
BinaryNode found;
if (n == null | root == null)
{
return null;
}
if (root.data == n.data)
{
return root;
}
if (root.data > n.data)
{
found = Find(root.left, n);
}
else
{
found = Find(root.right, n);
}
return found;
}
//use this method to display the data in order
public void InOrderTransversal()
{
BinaryNode temp = head;
DisplayInOrder(temp);
}
//use this method to display the data in order
public void DisplayInOrder(BinaryNode n)
{
if (n == null)
{
return;
}
DisplayInOrder(n.left);
Console.WriteLine("{0}", n.data);
DisplayInOrder(n.right);
}
}
No comments:
Post a Comment