1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Trying to construct an AVLTree

  1. Mar 17, 2013 #1

    Zondrina

    User Avatar
    Homework Helper

    So I'm trying to construct an AVLTree and something crazy seems to be happening in my code.

    AVL Tree Class. This includes only the insert and delete methods, soon to be a find method as well :

    Code (Text):
    package comp2402TreeEditor;

    public class AVLTree extends BSTree {  
       
        public AVLTree() {}
       
        public void insert(String dataString){
            Data data = new Data(dataString);
           
            AVLTreeNode newChildNode = new AVLTreeNode(data);

            if(isEmpty()) {
                setRoot(newChildNode);
                newChildNode.setLocation(getOwner().getDefaultRootLocation());
            }
           
            else
                getRoot().insertNode(newChildNode);
        }
       
        public void remove(String aKeyString){
            if(isEmpty()) return;
           
            if(size()==1){
                Data temp = new Data(aKeyString);
                if(root().getData().compare(temp) == 0)
                    setRoot(null);
                return;
            }
         
            getRoot().remove(aKeyString);  
        }
       
    }
     
    Now as for the real problem, here's my AVLTreeNode Class. I'm focusing mainly on the insertion portion right now :

    Code (Text):
    package comp2402TreeEditor;

    import java.awt.Point;

    public class AVLTreeNode extends BSTreeNode{

        int balance;
       
        public AVLTreeNode() {}

        public AVLTreeNode(Point aPoint) {
            super(aPoint);
            balance = 0;
        }
       
        public AVLTreeNode(Data data) {
            super(data);
            balance = 0;
        }
       
        public void insertNode(TreeNode aNode) {
            if(!(aNode instanceof AVLTreeNode)) return;
           
            System.out.println(this);
            System.out.println(aNode);
            System.out.println(leftChild);
            System.out.println(rightChild);
           
            if(aNode.getData().compare(getData()) < 0) {
                if(leftChild == null) {
                    leftChild = (AVLTreeNode) aNode;
                    aNode.setParent(this);
                    recursiveBalance(this);
                    aNode.setLocation(this.getLocation()); //starting location for animation
                }
                else{
                    leftChild.insertNode(aNode);
                }
            }
           
            else{
                if(rightChild == null) {
                    rightChild = (AVLTreeNode) aNode;
                    aNode.setParent(this);
                    recursiveBalance(this);
                    aNode.setLocation(this.getLocation()); //starting location for animation
                }
                else {
                    rightChild.insertNode(aNode);
                }
            }
        }
       
        public void remove(String aDataString){        
            Data temp = new Data(aDataString);

            int comparision = temp.compare(this.getData());
                   
            if(comparision < 0 && leftChild != null) {
                leftChild.remove(aDataString);
            }
                   
            else if(comparision > 0 && rightChild != null) {
                rightChild.remove(aDataString);
            }
           
            else if(comparision == 0){
                //found a node to remove so remove this node
                if(isLeaf())
                    getParent().removeChildNode(this);
               
                else if(isRoot() && rightChild == null) {
                    //hijack the leftChild as the new root of the tree
                    setData(leftChild.getData());
                    leftChild.setParent(null);
                   
                    rightChild = (AVLTreeNode) leftChild.rightChild();
                    if(rightChild != null)
                        rightChild.setParent(this);
                   
                    leftChild = (AVLTreeNode) leftChild.leftChild();
                    if(leftChild != null)
                        leftChild.setParent(this);
                }
               
                else if(isRoot() && leftChild == null) {
                    //hijack the right as the new root of the tree
                    setData(rightChild.getData());
                    rightChild.setParent(null);
                    leftChild = (AVLTreeNode) rightChild.leftChild();
                    if(leftChild != null)
                        leftChild.setParent(this);
                   
                    rightChild = (AVLTreeNode) rightChild.rightChild();
                    if(rightChild != null)
                        rightChild.setParent(this);
                }
               
                else if(leftChild == null && rightChild != null) {
                    //promote rightchild as new child of parent
                    ((AVLTreeNode) getParent()).replaceChildNode(this, rightChild);
                }
                else if(rightChild == null && leftChild != null) {
                    //promote left child as new child of parent
                    ((AVLTreeNode) getParent()).replaceChildNode(this, leftChild);
                }
                else{
                    //we need to remove an internal node with two current children
                    //find the smallest next node via the right subtree and use it as a
                    //replacement for this node
                   
                    TreeNode smallest = ((AVLTreeNode) rightChild).findSmallestNode();
                    this.setData(smallest.getData()); //steel the data object of the smallest node
                    smallest.remove(smallest.key());
                    //System.out.println("BSTreeNode::remove: smallest to remove= " + smallest.key());
                }      
            }
        }
       
        public void recursiveBalance(AVLTreeNode current) {
             setBalance(current);
             int tBalance = current.balance;

             System.out.println(current + " " + this);
             System.out.println(tBalance);

             if(tBalance == -2) {
                 if(height((AVLTreeNode)current.leftChild.leftChild) >= height((AVLTreeNode)current.leftChild.rightChild))
                     current = rotateRight(current);
                 else
                     current = doubleRotateLeftRight(current);
             }  
             if(tBalance == 2) {
                 if(height((AVLTreeNode)current.rightChild.rightChild) >= height((AVLTreeNode)current.rightChild.leftChild))
                     current = rotateLeft(current);
                 else
                     current = doubleRotateRightLeft(current);
             }

             if(current.getParent() != null) {
                 recursiveBalance((AVLTreeNode)current.getParent());
             }
             
             else {
                 //Need to somehow set the root to be current RIGHT HERE!!!!!!!!!
                 System.out.println("Balancing Complete!");
             }
         }
         
         public AVLTreeNode rotateLeft(AVLTreeNode n) {
             AVLTreeNode v = (AVLTreeNode)n.rightChild;
             v.setParent(n.getParent());
             n.rightChild = v.leftChild;
             
             if(n.rightChild != null)
                 n.rightChild.setParent(n);
         
              v.leftChild = n;
              n.setParent(v);
         
              if(v.getParent() != null) {
                  if(((AVLTreeNode)v.getParent()).rightChild == n)
                      ((AVLTreeNode)v.getParent()).rightChild = v;
                  else if( ((AVLTreeNode)v.getParent()).leftChild == n)
                      ((AVLTreeNode)v.getParent()).leftChild = v;
              }
         
              setBalance(n);
              setBalance(v);
              return v;
         }
         
         public AVLTreeNode rotateRight(AVLTreeNode n) {
             AVLTreeNode v = (AVLTreeNode)n.leftChild; //(3)
             v.setParent(n.getParent()); //(null)
             n.leftChild = v.rightChild; //(null)
             
             if(n.leftChild!=null)
                 n.leftChild.setParent(n);
         
              v.rightChild = n;
              n.setParent(v);

              if(v.getParent() != null) {
                  if(((AVLTreeNode)v.getParent()).rightChild == n)
                      ((AVLTreeNode)v.getParent()).rightChild = v;
                  else if( ((AVLTreeNode)v.getParent()).leftChild == n)
                      ((AVLTreeNode)v.getParent()).leftChild = v;
              }
              setBalance(n);
              setBalance(v);
              return v;
         }

         public AVLTreeNode doubleRotateLeftRight(AVLTreeNode u) {
             u.leftChild = rotateLeft((AVLTreeNode)u.leftChild);
             return rotateRight(u);
         }

         public AVLTreeNode doubleRotateRightLeft(AVLTreeNode u) {
             u.rightChild = rotateRight((AVLTreeNode)u.rightChild);
             return rotateLeft(u);
         }

         public AVLTreeNode successor(AVLTreeNode q) {
             if(q.rightChild != null) {
                 AVLTreeNode r = (AVLTreeNode)q.rightChild;
                 while(r.leftChild != null)
                     r = (AVLTreeNode)r.leftChild;
                 return r;
             }
             
             else {
                 AVLTreeNode p = (AVLTreeNode)q.getParent();
                 while(p != null && q == p.rightChild) {
                     q = p;
                     p = (AVLTreeNode)q.getParent();
                 }
                 return p;
             }
         }

         private int height(AVLTreeNode current) {
             if(current == null)
                 return -1;
             if(current.leftChild == null && current.rightChild == null)
                 return 0;
             else if(current.leftChild == null)
                 return 1+height((AVLTreeNode)current.rightChild);
             else if(current.rightChild == null)
                 return 1+height((AVLTreeNode)current.leftChild);
             else
                 return 1+maximum(height((AVLTreeNode)current.leftChild),height((AVLTreeNode)current.rightChild));
         }

         private int maximum(int a, int b) {
             return (a>=b) ? a : b;
         }
         
         private void setBalance(AVLTreeNode current) {
             current.balance = height((AVLTreeNode)current.rightChild) - height((AVLTreeNode)current.leftChild);
         }
         
        private void replaceChildNode(TreeNode currentChild, TreeNode newChild){
            //replace the currentChild of this node with the newChild node
            if(leftChild == currentChild){
                removeChildNode(currentChild);
                leftChild = (AVLTreeNode) newChild;
                newChild.setParent(this);
            }
            else if(rightChild == currentChild){
                removeChildNode(currentChild);
                rightChild = (AVLTreeNode) newChild;
                newChild.setParent(this);
            }
        }
       
        private TreeNode findSmallestNode(){
            //find the smallest node searching from this node along the left subtrees
            //in a binary search tree the node with the smallest key will be found by
            //going left as far as possible.
           
            if(leftChild == null) return this;
            else return ((AVLTreeNode) leftChild).findSmallestNode();
           
        }
    }
       
     
    Crazy things seem to happen when i try to create a tree by inserting 5, 3 and then 1. The 3 and 1 nodes disapear into nowhere and only the 5 node is left surviving ( which is absolutely incorrect ).

    What should happen is that since 5 is my root, 3 is a left child and 1 is a left left child; I should see a re-arrangement of my tree to 3 1 5 where 3 is now the root, 1 is the left child and 5 is the right child.

    For some reason this does not seem to be happening? If anyone can spot the kink please let me know as I've been at this for 3 days now and it's getting quite tiresome.

    EDIT : Here's a picture of my gui and what's going on.

    Picture of inserting 5 and then 3 : http://gyazo.com/6cf46d74404d5e49650a096b721f8b2a
    Picture of inserting 1 right after : http://gyazo.com/2b04ee63e66991fbc93cc201fa981159
     
  2. jcsd
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted



Similar Discussions: Trying to construct an AVLTree
  1. Construct a launcher (Replies: 4)

  2. ROtate construction (Replies: 0)

  3. Construction drawing (Replies: 2)

Loading...