|
using System;
using
System.Collections.Generic;
using System.Linq;
using System.Text;
namespace AVL_tree
{
class
Program
{
static void Main(string[] args)
{
AvlTree<int>
tree = new AvlTree<int>();
tree.InsertNode(10);
tree.Print();
tree.InsertNode(15);
tree.Print();
tree.InsertNode(13);
tree.Print();
}
}
class
AvlTree<T> where T : IComparable<T>
{
AvlNode<T> root;
public void
InsertNode(T data)
{
if (root == null)
{
root = new AvlNode<T>
{ Data = data };
Console.WriteLine("Insert
at root: " + data);
}
else
{
AvlNode<T>
node = root;
while (node != null)
{
if (data.CompareTo(node.Data) < 0)
{
AvlNode<T> left = node.Left;
if (left == null)
{
node.Left = new AvlNode<T> { Data = data, Parent = node
};
Console.WriteLine("Insert
after "+ node.Data + " to
Left, value: " + data);
BalanceNode(node, 1);
return;
}
else
{
node = left;
}
}
else if
(data.CompareTo(node.Data) > 0)
{
AvlNode<T> right = node.Right;
if (right == null)
{
node.Right = new AvlNode<T> { Data = data, Parent = node
};
Console.WriteLine("Insert
after " + node.Data + " to
right, value: " + data);
BalanceNode(node, -1);
return;
}
else
{
node = right;
}
}
else
{
node.Data = data;
return;
}
}
}
}
private void
BalanceNode(AvlNode<T> n, int balance)
{
while (n != null)
{
balance =
(n.Balance += balance);
if (balance == 0)
{
return;
}
else if (balance
== 2)
{
if (n.Left.Balance == 1)
{
Console.WriteLine("--------------------------");
Console.WriteLine(" Print before rotation");
Console.WriteLine("--------------------------");
Print();
Console.WriteLine("--------------------------");
Console.WriteLine("Rotate
Right at " + n.Data);
RotateRight(n);
}
else
{
Console.WriteLine("--------------------------");
Console.WriteLine(" Print before rotation");
Console.WriteLine("--------------------------");
Print();
Console.WriteLine("--------------------------");
Console.WriteLine("Rotate
LeftRight at " + n.Data);
RotateLeftRight(n);
}
return;
}
else if (balance
== -2)
{
if (n.Right.Balance == -1)
{
Console.WriteLine("--------------------------");
Console.WriteLine(" Print before rotation");
Console.WriteLine("--------------------------");
Print();
Console.WriteLine("--------------------------");
Console.WriteLine("Rotate
Left at " + n.Data);
RotateLeft(n);
}
else
{
Console.WriteLine("--------------------------");
Console.WriteLine(" Print before rotation");
Console.WriteLine("--------------------------");
Print();
Console.WriteLine("--------------------------");
Console.WriteLine("Rotate
RightLeft at " + n.Data);
RotateRightLeft(n);
}
return;
}
AvlNode<T> parent = n.Parent;
if (parent != null)
{
if (parent.Left == n)
{
balance = 1;
}
else
{
balance = -1;
}
}
n = parent;
}
}
#region rotation left, right, leftright og
rightleft
#region left
/*
ROTATION
VENSTRE
(5) (4)
/ \ / \
(4) S / \
/ \ --> (3)
(5)
(3) R / \ / \
/ \ / \
/ \
P Q P Q R
S
*/
//Den Grå markerede kode er ikke del af Pensum.
private AvlNode<T>
RotateLeft(AvlNode<T> node)
{
AvlNode<T> right = node.Right;
AvlNode<T> rightLeft = right.Left;
AvlNode<T> parent = node.Parent;
right.Parent = parent;
right.Left = node;
node.Right = rightLeft;
node.Parent = right;
if (rightLeft != null)
{
rightLeft.Parent = node;
}
if (node == root)
{
root = right;
}
else if
(parent.Right == node)
{
parent.Right = right;
}
else
{
parent.Left = right;
}
right.Balance++;
node.Balance = -right.Balance;
return right;
}
#endregion
#region right
/*
ROTATION HØJRE
(3) (4)
/ \ / \
P (4) / \
/
\ --> (3)
(5)
Q (5) / \ / \
/ \ / \
/ \
R S P Q R
S
*/
private AvlNode<T>
RotateRight(AvlNode<T> node)
{
AvlNode<T> left = node.Left;
AvlNode<T> leftRight = left.Right;
AvlNode<T> parent = node.Parent;
left.Parent = parent;
left.Right = node;
node.Left = leftRight;
node.Parent = left;
if (leftRight != null)
{
leftRight.Parent = node;
}
if (node == root)
{
root = left;
}
else if (parent.Left
== node)
{
parent.Left = left;
}
else
{
parent.Right = left;
}
left.Balance--;
node.Balance = -left.Balance;
return left;
}
#endregion
#region left>right
/*
ROTATION VENSTRE OG SÅ
HØJRE
(5) (5) (4)
/ \ / \ / \
(3) S (4) S / \
/ \
--> / \
--> (3) (5)
P (4) (3) R / \ / \
/ \ / \ / \
/ \
Q R P Q P Q R
S
*/
private AvlNode<T>
RotateLeftRight(AvlNode<T> node)
{
AvlNode<T> left = node.Left;
AvlNode<T> leftRight = left.Right;
AvlNode<T> parent = node.Parent;
AvlNode<T> leftRightRight =
leftRight.Right;
AvlNode<T> leftRightLeft =
leftRight.Left;
leftRight.Parent = parent;
node.Left = leftRightRight;
left.Right = leftRightLeft;
leftRight.Left = left;
leftRight.Right = node;
left.Parent = leftRight;
node.Parent = leftRight;
if (leftRightRight != null)
{
leftRightRight.Parent = node;
}
if (leftRightLeft != null)
{
leftRightLeft.Parent = left;
}
if (node == root)
{
root = leftRight;
}
else if
(parent.Left == node)
{
parent.Left = leftRight;
}
else
{
parent.Right = leftRight;
}
if (leftRight.Balance == -1)
{
node.Balance = 0;
left.Balance = 1;
}
else if
(leftRight.Balance == 0)
{
node.Balance = 0;
left.Balance = 0;
}
else
{
node.Balance = -1;
left.Balance = 0;
}
leftRight.Balance = 0;
return leftRight;
}
#endregion
#region right>left
/*
ROTATION HØJRE OG SÅ
VENSTRE
(3) (3) (4)
/ \ / \ / \
P (5) P (4) / \
/ \
--> / \
--> (3) (5)
(4) D
Q (5) / \ / \
/ \ / \ / \
/ \
B C R S P Q R
S
*/
private AvlNode<T>
RotateRightLeft(AvlNode<T> node)
{
AvlNode<T> right = node.Right;
AvlNode<T> rightLeft = right.Left;
AvlNode<T> parent = node.Parent;
AvlNode<T> rightLeftLeft =
rightLeft.Left;
AvlNode<T> rightLeftRight = rightLeft.Right;
rightLeft.Parent = parent;
node.Right = rightLeftLeft;
right.Left = rightLeftRight;
rightLeft.Right = right;
rightLeft.Left = node;
right.Parent = rightLeft;
node.Parent = rightLeft;
if (rightLeftLeft != null)
{
rightLeftLeft.Parent = node;
}
if (rightLeftRight != null)
{
rightLeftRight.Parent = right;
}
if
(node == root)
{
root = rightLeft;
}
else if
(parent.Right == node)
{
parent.Right = rightLeft;
}
else
{
parent.Left = rightLeft;
}
if (rightLeft.Balance == 1)
{
node.Balance = 0;
right.Balance = -1;
}
else if
(rightLeft.Balance == 0)
{
node.Balance = 0;
right.Balance = 0;
}
else
{
node.Balance = 1;
right.Balance = 0;
}
rightLeft.Balance = 0;
return rightLeft;
}
#endregion
#endregion
public void
Print()
{
Console.WriteLine("--------Print
AVL Træ-----------");
String t = "";
if (root != null)
root.Print(root, t);
Console.WriteLine("--------------------------------");
Console.WriteLine();
}
}
class
AvlNode<T>
{
private T data;
private int
balance;
private AvlNode<T>
left;
private AvlNode<T>
right;
private AvlNode<T> parent;
#region Properties
public AvlNode<T>
Left
{
get { return
left; }
set { left = value;
}
}
public AvlNode<T>
Right
{
get { return
right; }
set
{ right = value; }
}
public AvlNode<T>
Parent
{
get { return
parent; }
set { parent = value;
}
}
public T Data
{
get { return
data; }
set { data = value;
}
}
public int
Balance
{
get { return
balance; }
set { balance = value;
}
}
#endregion
public void
Print(AvlNode<T> n, string t)
{
AvlNode<T>parentData;
if
(n.parent != null)
{
parentData =
parent;
}
else
{
parentData = new AvlNode<T>();
}
t += "-";
if (right != null)
right.Print(n.right, t);
Console.WriteLine(t + "
node: " + n.data + " parent:
" + parentData.data + "
Balance: " + n.Balance);
if (left != null)
left.Print(n.left, t);
}
}
}
|
