none
About AVL tree rotation logic

    Question

  • I am trying to create an AVL tree, the most importation is rotation. I used my sample data but the result is wrong in the first rotation.

    I think the error is that I didn't return the correct object after rotation. Please help me to look at it.

    namespace AVLTree
    {
        public class AVLTree
        {
            private AvlTreeNode root;
            // AvlTreeNode has three fields, data, left and right.
            public AVLTree()
            {
                root = null;
            }
    
            public void Insert(int value)
            {
                Insert(value, ref root);
                if (!IsBanlance(root))
                    ReBanlance(root);
            }
    
            private void Insert(int element, ref AvlTreeNode node)
            {
               // blah blah
            }
    
            public void ReBanlance(AvlTreeNode node)
            {
                int heightDiff = GetHeight(node.left) - GetHeight(node.right);
                if (heightDiff > 1)//left case
                {
                    if (GetHeight(node.left.left) > GetHeight(node.left.right))//left left case
                    {
                        RightRotation(node);
                    }
                    else// left right case
                    {
                        LeftRotation(node);
                        RightRotation(node);
                    }
                }
                else if (heightDiff < -1)//right case
                {
                    if (GetHeight(node.right.left) > GetHeight(node.right.right))//right left case
                    {
                        RightRotation(node);
                        LeftRotation(node);
                    }
                    else//right right case
                    {
                        LeftRotation(node);
                        RightRotation(node);
                    }
                }
                return true;
            }
    
            // http://en.wikipedia.org/wiki/Tree_rotation
            // Left Rotation of node P:
            // Let Q be P's right child.
            // Set Q to be the new root.
            // Set P's right child to be Q's left child.
            // Set Q's left child to be P.
    
            public bool LeftRotation(AvlTreeNode P)
            {
                // Define new instances
                AvlTreeNode Q = new AvlTreeNode();
                AvlTreeNode A = new AvlTreeNode();
                AvlTreeNode B = new AvlTreeNode();
                AvlTreeNode C = new AvlTreeNode();
                // Original tree expression
                Q = P.right;
                A = P.left;
                B = Q.left;
                C = Q.right;
                //  Begin rotation
                P.left = A;
                P.right = B;
                Q.left = P;
                Q.right = C;
                return true;
            }
    
            //    Right Rotation of node Q:
            //    Let P be Q's left child.
            //    Set P to be the new root.
            //    Set Q's left child to be P's right child.
            //    Set P's right child to be Q.
    
            public bool RightRotation(AvlTreeNode Q)
            {
                // Define new instances
                AvlTreeNode P = new AvlTreeNode();
                AvlTreeNode A = new AvlTreeNode();
                AvlTreeNode B = new AvlTreeNode();
                AvlTreeNode C = new AvlTreeNode();
                // Original tree expression
                P = Q.left;
                A = P.left;
                B = P.right;
                C = Q.right;
                //  Begin rotation
                P.left = A;
                Q.right = C;
                Q.left = B;
                P.right = Q;
                return true;
            }


    • Edited by ardmore Friday, January 24, 2014 3:54 PM
    Friday, January 24, 2014 3:52 PM

Answers

  • And I rewrote my code, ignore 'ref'. Now it works perfectly.

      public void ReBanlance(AvlTreeNode node)
            {
                int heightDiff = GetHeight(node.left) - GetHeight(node.right);
                if (heightDiff > 1)//left case
                {
                    if (GetHeight(node.left.left) > GetHeight(node.left.right))//left left case
                    {
                        root = RightRotation(node);
                    }
                    else// left right case
                    {
                        root = LeftRotation(node);
                        root = RightRotation(root);
                    }
                }
                else if (heightDiff < -1)//right case
                {
                    if (GetHeight(node.right.left) > GetHeight(node.right.right))//right left case
                    {
                        root = RightRotation(node);
                        root = LeftRotation(root);
                    }
                    else//right right case
                    {
                        root = LeftRotation(node);
                    }
                }
            }
    
            // http://en.wikipedia.org/wiki/Tree_rotation
            // Left Rotation of node P:
            // Let Q be P's right child.
            // Set Q to be the new root.
            // Set P's right child to be Q's left child.
            // Set Q's left child to be P.
    
            public AvlTreeNode LeftRotation(AvlTreeNode P)
            {
                // Define new instances
                AvlTreeNode Q = new AvlTreeNode();
                AvlTreeNode A = new AvlTreeNode();
                AvlTreeNode B = new AvlTreeNode();
                AvlTreeNode C = new AvlTreeNode();
                // Original tree expression
                Q = P.right;
                A = P.left;
                B = Q.left;
                C = Q.right;
                //  Begin rotation
                P.left = A;
                P.right = B;
                Q.left = P;
                Q.right = C;
                return Q;
            }

    • Marked as answer by ardmore Tuesday, January 28, 2014 1:14 PM
    Tuesday, January 28, 2014 2:24 AM

All replies

  • This code seems to suffer from the same problem as the code in a previous question of yours, you're not updating the links from the parent to child.

    For example in RightRotation, OK, you're changing all this links between child nodes but a right rotation also requires that P takes the place of Q as root of the rotated subtree. I don't see anywhere in your code that the root is changed, the argument of RightRotation should be 'ref' and so does the argument of LeftRotation and ReBalance.

    An alternative solution is to move the values between the nodes such that Q effectively becomes P. Actually this would be preferable in C# if the node value is a small value type like int. In this case it's slightly faster to move the values than to update the node links.

    Friday, January 24, 2014 9:22 PM
    Moderator
  • It still failed after I added 'ref' everywhere as you pointed out. The exception is
    Object reference not set to an instance of an object
    Which occurred at  A = P.left during the first right rotation. Before this there was a left rotation, I guess some information was lost there.
    Sunday, January 26, 2014 3:37 PM
  • That exception means that P is null so Q.left is null since you say this was a right rotation.

    The big question here is how did you end up doing a right rotation if Q doesn't have a left child. The purpose of a right rotation is to decrease the size of the left subtree of Q but it seems that Q doesn't have a left subtree so the right rotation wasn't needed.

    One problem seems to be in ReBalance, the right right case does both a left rotation and a right rotation, it's supposed to do only a left rotation.

    Sunday, January 26, 2014 5:11 PM
    Moderator
  • Okay. It is my fault, now I removed that piece of code. ReBalance becomes,

     public void ReBanlance(ref AvlTreeNode node)
            {
                int heightDiff = GetHeight(node.left) - GetHeight(node.right);
                if (heightDiff > 1)//left case
                {
                    if (GetHeight(node.left.left) > GetHeight(node.left.right))//left left case
                    {
                        RightRotation(ref node);
                    }
                    else// left right case
                    {
                        LeftRotation(ref node);
                        RightRotation(ref node);
                    }
                }
                else if (heightDiff < -1)//right case
                {
                    if (GetHeight(node.right.left) > GetHeight(node.right.right))//right left case
                    {
                        RightRotation(ref node);
                        LeftRotation(ref node);
                    }
                    else//right right case
                    {
                        LeftRotation(ref node);
                    }
                }
            }

    The exception is gone but when I traversal the tree finally only a few node there. Why?

    I guess that the code is wrong when I always use 'root' to pass in.

     public void Insert(int value)
     {
         Insert(value, ref root);
         if (!IsBanlance(root))
              ReBanlance(ref root);
     }
    Thanks for help.

    Sunday, January 26, 2014 9:11 PM
  • "The exception is gone but when I traversal the tree finally only a few node there. Why?"

    I suppose Insert doesn't work properly. Test insert separately, it's supposed to work correctly even if you don't balance the tree.

    "I guess that the code is wrong when I always use 'root' to pass in."

    Hmm, the particular code seems dubious when it comes to balancing but it shouldn't cause nodes to disappear from the tree. The problem is more likely inside Insert(int, AvlTreeNode) method.

    Monday, January 27, 2014 5:34 AM
    Moderator
  • Well, I don't think so. I comment the balancing code. The tree is correct.
    Tuesday, January 28, 2014 12:09 AM
  • And I rewrote my code, ignore 'ref'. Now it works perfectly.

      public void ReBanlance(AvlTreeNode node)
            {
                int heightDiff = GetHeight(node.left) - GetHeight(node.right);
                if (heightDiff > 1)//left case
                {
                    if (GetHeight(node.left.left) > GetHeight(node.left.right))//left left case
                    {
                        root = RightRotation(node);
                    }
                    else// left right case
                    {
                        root = LeftRotation(node);
                        root = RightRotation(root);
                    }
                }
                else if (heightDiff < -1)//right case
                {
                    if (GetHeight(node.right.left) > GetHeight(node.right.right))//right left case
                    {
                        root = RightRotation(node);
                        root = LeftRotation(root);
                    }
                    else//right right case
                    {
                        root = LeftRotation(node);
                    }
                }
            }
    
            // http://en.wikipedia.org/wiki/Tree_rotation
            // Left Rotation of node P:
            // Let Q be P's right child.
            // Set Q to be the new root.
            // Set P's right child to be Q's left child.
            // Set Q's left child to be P.
    
            public AvlTreeNode LeftRotation(AvlTreeNode P)
            {
                // Define new instances
                AvlTreeNode Q = new AvlTreeNode();
                AvlTreeNode A = new AvlTreeNode();
                AvlTreeNode B = new AvlTreeNode();
                AvlTreeNode C = new AvlTreeNode();
                // Original tree expression
                Q = P.right;
                A = P.left;
                B = Q.left;
                C = Q.right;
                //  Begin rotation
                P.left = A;
                P.right = B;
                Q.left = P;
                Q.right = C;
                return Q;
            }

    • Marked as answer by ardmore Tuesday, January 28, 2014 1:14 PM
    Tuesday, January 28, 2014 2:24 AM
  • You mean it works in the sense that nodes don't go missing from the tree? What about balancing, does it really balance the tree as it should? I doubt that.

    As a side note, the "// Define new instances" part in the rotation functions is useless. You're supposed to define variables, not new instances. That is, the following is enough:

    AvlTreeNode Q, A, B, C;

    Tuesday, January 28, 2014 7:16 AM
    Moderator