CODEWITHSUNDEEP
c#avl-tree
bananabreadbob
bananabreadbob

Reputation: 407

AVL tree left and right rotation C#

I am trying to implement an AVL tree however when I come to print the tree out, it does nothing. I am thinking that there is something wrong with my left and right rotate implementation.

I have transferred the rotated values between two variables "old" and "new" to make it easier.

      private void rotateLeft(ref Node<T> tree)
        {
            if (tree.Right.BalanceFactor > 0)
            {
                rotateRight(ref tree.Right);
            }
            Node<T> oldRoot = tree;
            Node<T> newRoot = tree;

            newRoot.Right = oldRoot;
            oldRoot.Left = newRoot;
            newRoot.Right = oldRoot.Left;

        }

        private void rotateRight(ref Node<T> tree)
        {
            if (tree.Left.BalanceFactor < 0)
            {
                rotateLeft(ref tree.Left);
            }
            Node<T> oldRoot = tree;
            Node<T> newRoot = tree;

            newRoot.Left = oldRoot;
            oldRoot.Right = newRoot;
            newRoot.Left = oldRoot.Right;


        }

Heres the Node BalanceFactor 

class Node<T> where T : IComparable
{
    private T data;
    private int balanceFactor = 0; //added for AVLTree
    public Node<T> Left, Right;

    public int BalanceFactor
    {
        set { balanceFactor = value; }
        get { return balanceFactor; }
    }

Insert Item

private void insertItem(T item, ref Node<T> tree)
        {
            if (tree == null)
                tree = new Node<T>(item);
            else if (item.CompareTo(tree.Data) < 0)
                insertItem(item, ref tree.Left);
            else if (item.CompareTo(tree.Data) > 0)
                insertItem(item, ref tree.Right);

            tree.BalanceFactor = Height(tree.Left) - Height(tree.Right);

            if (tree.BalanceFactor <= -2)
                rotateLeft(ref tree);
            if (tree.BalanceFactor >= 2)
                rotateRight(ref tree);
        }

Upvotes: 2

Views: 2906

Answers (2)

Michael_O
Michael_O

Reputation: 31

private void rotateLeft(ref Node<T> tree)
{
    if (tree.Right.BalanceFactor > 0)  //double rotate
        rotateRight(ref tree.Right);

    Node<T> oldRoot = tree;
    Node<T> newRoot = tree.Right;

    oldRoot.Right = newRoot.Left;
    newRoot.Left = oldRoot;

}

private void rotateRight(ref Node<T> tree)
{
    if (tree.Left.BalanceFactor < 0)  //double rotate
        rotateLeft(ref tree.Right);

    Node<T> oldRoot = tree;
    Node<T> newRoot = oldRoot.Left;

    oldRoot.Left = newRoot.Right;
    newRoot.Right = oldRoot;

}

Upvotes: 0

Ondrej Tucny
Ondrej Tucny

Reputation: 27962

Look at this code:

Node<T> oldRoot = tree;
Node<T> newRoot = tree;

newRoot.Right = oldRoot;
oldRoot.Left = newRoot;
newRoot.Right = oldRoot.Left;

and populate tree where ever it's possible. … Here it goes:

tree.Right = tree;
tree.Left = tree;
tree.Right = tree.Left;

I'm quite sure this isn't what you were trying to do. Have a look on the AVL balancing algorithm at wikipedia.

Upvotes: 1

Related Questions