1. Not finding help here? Sign up for a free 30min 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!

AVLTree program and Binary Tree program help

  1. Mar 22, 2012 #1
    1. The problem statement, all variables and given/known data
    Write a java program to construct an AVL tree and then generate 100 random numbers to insert to this tree and then delete randomly 50 of these random numbers from this AVL tree.

    (use the AVL tree animation of your book to understand the bahavior of the this tree in the case of insertion and deletion, www.cs.armstrong.edu/liang/animation/AVLTreeAnimation.html).



    2. Relevant equations



    3. The attempt at a solution
    The program BinaryTree errors deal with the inorder method I am not sure what the heck is wrong with it becuase it came straight from the book I would just like it so that I can create a test class for it but I cant resolve this error. There is also an error with my AVLTree program its updateheigth method is not quite right.

    Code (Text):

    public class BinaryTree<E extends Comparable<E>> extends Abstracttree<E> {
       
        protected TreeNode<E> root;
        protected int size = 0;
       
        public BinaryTree(){
       
    }
        public BinaryTree(E[] objects){
            for(int i = 0;i < objects.length; i++)
                insert(objects[i]);
        }
        public boolean search(E e){
           TreeNode<E> current = root;
            while ( current != null){
                if(e.compareTo(current.element)< 0){
                    current = current.left;
                }
                else if (e.compareTo(current.element) > 0){
                    current = current.right;
                }
                else
                    return true;
            }
            return false;
        }
        public boolean insert(E e){
            if(root == null)
                root = createNewNode(e);
            else{
                TreeNode<E> parent = null;
                TreeNode<E> current = root;
                while(current != null)
                    if (e.compareTo(current.element) < 0){
                        parent = current;
                        current = current.left;
                    }
                    else if (e.compareTo(current.element) > 0){
                        parent = current;
                        current = current.right;
                    }
                else
                        return false;
               
                if(e.compareTo(parent.element)< 0)
                    parent.left = createNewNode(e);
                else
                    parent.right = createNewNode(e);
            }
            size++;
            return true;
        }
        protected TreeNode<E> createNewNode(E e){
            return new TreeNode<E>(e);
    }
        public void inorder(){
            inorder(root);
        }
        protected void inorder(TreeNode<E> root){
            if(root== null) return;
            inorder(root.left);
            System.out.print(root.element + " ");
            inorder(root.right);
        }
        public void postorder(){
            postorder(root);
        }
        protected void postorder(TreeNode<E> root){
            if(root== null) return;
            postorder(root.left);
            postorder(root.right);
            System.out.print(root.element + " ");
        }
        public void preorder() {
            preorder(root);
        }
        protected void preorder(TreeNode<E> root){
            if(root == null) return;
            System.out.print(root.element + " ");
            preorder(root.left);
            preorder(root.right);
        }

        @Override
        public void inOrder() {
            throw new UnsupportedOperationException("Not supported yet.");
        }
        public static class TreeNode<E extends Comparable<E>>{
            E element;
            TreeNode<E> left;
            TreeNode<E> right;
           
            public TreeNode(E e){
                element = e;
            }
        }
        public int getSize(){
            return size;
        }
        public TreeNode getRoot(){
            return root;
        }
        public java.util.ArrayList<TreeNode<E>> path(E e) {
            java.util.ArrayList<TreeNode<E>> list = new java.util.ArrayList<TreeNode<E>>();
            TreeNode<E> current = root;
           
            while(current != null){
                list.add(current);
                if(e.compareTo(current.element) < 0){
                    current = current.left;
                }
                else if (e.compareTo(current.element) > 0){
                    current = current.right;
                }
                else break;
            }
            return list;
        }
        public boolean delete(E e){
            TreeNode<E> parent = null;
            TreeNode<E> current = root;
            while(current != null){
                if(e.compareTo(current.element) < 0){
                    parent = current;
                    current = current.left;
                }
                else if (e.compareTo(current.element) > 0){
                    parent = current;
                    current = current.right;
                }
                else
                    break;
            }
            if(current == null)
                return false;
            if(current.left == null){
                if(parent == null){
                    root = current.right;
                }
                else{
                    if(e.compareTo(parent.element) < 0)
                        parent.left = current.right;
                    else
                        parent.right = current.right;
                }
            }
            else{
                TreeNode<E> parentOfRightMost = current;
                TreeNode<E> rightMost = current.left;
               
                while(rightMost.right != null){
                    parentOfRightMost = rightMost;
                    rightMost  = rightMost.right;
                }
                current.element = rightMost.element;
               
                if(parentOfRightMost.right == rightMost)
                    parentOfRightMost.right = rightMost.left;
                else
                    parentOfRightMost.left = rightMost.left;
            }
            size--;
            return true;
        }
        public java.util.Iterator iterator(){
            return inorderIterator();
        }
        public java.util.Iterator inorderIterator(){
            return new InorderIterator();
        }
        class InorderIterator implements java.util.Iterator {
            private java.util.ArrayList<E> list = new java.util.ArrayList<E>();
            private int current = 0;
           
            public InorderIterator(){
            inorder();
        }
            public void inorder(TreeNode<E> root){
                if(root == null) return;
                inorder(root.left);
                list.add(root.element);
                inorder(root.right);
            }
            public boolean hasNext(){
                if(current < list.size())
                    return true;
               
                return false;
            }
            public Object next(){
                return list.get(current++);
            }
            public void remove(){
                delete(list.get(current));
                list.clear();
                inorder();
            }

            private void inorder() {
                throw new UnsupportedOperationException("Not yet implemented");
            }
        }
        public void clear(){
            root = null;
            size = 0;
                   
        }
    }


    Code (Text):
    public abstract class Abstracttree<E extends Comparable<E>>implements Tree<E> {
       
        public void inorder() {
           
        }
        public void postorder() {
           
        }
        public void preorder() {
           
        }
        public boolean isEmpty() {
            return getSize() == 0;
        }
        public java.util.Iterator iterator() {
            return null;
        }
    }

    Code (Text):
    public interface Tree<E extends Comparable<E>> {
       
        public boolean search(E e);
        public boolean insert(E e);
        public boolean delete(E e);
        public void inOrder();
        public void postorder();
        public void preorder();
        public int getSize();
        public boolean isEmpty();
        public java.util.Iterator iterator();
    }
    Code (Text):
    public class AVLTree<E extends Comparable<E>> extends BinaryTree<E> {
       
        public AVLTree(){
           
        }
        public AVLTree(E[] objects){
            super(objects);
        }
        @Override
        protected AVLTreeNode<E> createNewNode(E o){
            return new AVLTreeNode<E>(o);
        }
        public boolean insert(E o){
           boolean successful = super.insert(o);
            if (!successful)
            return false; // o is already in the tree
                else {
                   balancePath(o); // Balance from o to the root if necessary
                    }

     return true; //
        }    
       
    private int balanceFactor(AVLTreeNode<E> node) {
        if (node.right == null) // node has no right subtree
     return -node.height;
     else if (node.left == null) // node has no left subtree
     return +node.height;
     else
     return ((AVLTreeNode<E>)node.right).height -
     ((AVLTreeNode<E>)node.left).height;
           
        }
    public void updateHeigth(AVLTreeNode<E> node){
            if (node.left == null && node.right == null)
                node.height = 0;
     else if (node.left == null) // node has no left subtree
     node.height = 1 + ((AVLTreeNode<E>)(node.right)).height;
     else if (node.right == null) // node has no right subtree
     node.height = 1 + ((AVLTreeNode<E>)(node.left)).height;
     else
     node.height = 1 +
     Math.max(((AVLTreeNode<E>)(node.right)).height,
     ((AVLTreeNode<E>)(node.left)).height);
     }
       
     private void balanceLL(TreeNode<E> A, TreeNode<E> parentOfA) {
            TreeNode<E> B = A.left; // A is left-heavy and B is left-heavy

     if (A == root) {
     root = B;
     }
    else {
     if (parentOfA.left == A) {
     parentOfA.left = B;
     }
     else {
     parentOfA.right = B;
     }
     }

     A.left = B.right; // Make T2 the left subtree of A
     B.right = A; // Make A the left child of B
     updateHeight((AVLTreeNode<E>)A);
     updateHeight((AVLTreeNode<E>)B);
     }
            private void balanceLR(TreeNode<E> A, TreeNode<E> parentOfA) {
    TreeNode<E> B = A.left; // A is left-heavy
     TreeNode<E> C = B.right; // B is right-heavy

     if (A == root) {
     root = C;
     }
     else {
     if (parentOfA.left == A) {
     parentOfA.left = C;
     }
     else {
     parentOfA.right = C;
     }
     }

     A.left = C.right; // Make T3 the left subtree of A
     B.right = C.left; // Make T2 the right subtree of B
     C.left = B;
     C.right = A;

     // Adjust heights
     updateHeight((AVLTreeNode<E>)A);
     updateHeight((AVLTreeNode<E>)B);
     updateHeight((AVLTreeNode<E>)C);
     }


           
       
    private void balanceRR(TreeNode<E> A, TreeNode<E> parentOfA) {
    TreeNode<E> B = A.right; // A is right-heavy and B is right-heavy

     if (A == root) {
     root = B;
     }
     else {
     if (parentOfA.left == A) {
     parentOfA.left = B;
     }
     else {
     parentOfA.right = B;
     }
     }

     A.right = B.left; // Make T2 the right subtree of A
            B.left = A;
     updateHeight((AVLTreeNode<E>)A);
     updateHeight((AVLTreeNode<E>)B);
     }
        private void balanceRL(TreeNode<E> A, TreeNode<E> parentOfA) {
           TreeNode<E> B = A.right; // A is right-heavy
     TreeNode<E> C = B.left; // B is left-heavy

     if (A == root) {
     root = C;
     }
     else {
     if (parentOfA.left == A) {
     parentOfA.left = C;
     }
     else {
     parentOfA.right = C;
     }
     }

     A.right =C.left; // Make T2 the right subtree of A
     B.left = C.right; // Make T3 the left subtree of B
     C.left = A;
     C.right = B;

     // Adjust heights
     updateHeight((AVLTreeNode<E>)A);
     updateHeight((AVLTreeNode<E>)B);
     updateHeight((AVLTreeNode<E>)C);
        }
        private void balancePath(E o){
         java.util.ArrayList<TreeNode<E>> path = path(o);
     for (int i = path.size() - 1; i >= 0; i--) {
     AVLTreeNode<E> A = (AVLTreeNode<E>)(path.get(i));
     updateHeight(A);
     AVLTreeNode<E> parentOfA = (A == root) ? null :
     (AVLTreeNode<E>)(path.get(i - 1));

     switch (balanceFactor(A)) {
     case -2:
     if (balanceFactor((AVLTreeNode<E>)A.left) <= 0) {
     balanceLL(A, parentOfA); // Perform LL rotation
     }
     else {
     balanceLR(A, parentOfA); // Perform LR rotation
     }
     break;
     case +2:
     if (balanceFactor((AVLTreeNode<E>)A.right) >= 0) {
     balanceRR(A, parentOfA); // Perform RR rotation
     }
     else {
     balanceRL(A, parentOfA); // Perform RL rotation
     }
     }
     }
     }
           
        public boolean delete(E element) {
            if (root == null)
     return false; // Element is not in the tree

     // Locate the node to be deleted and also locate its parent node
     TreeNode<E> parent = null;
     TreeNode<E> current = root;
     while (current != null) {
     if (element.compareTo(current.element) < 0) {
     parent = current;
     current = current.left;
     }
     else if (element.compareTo(current.element) > 0) {
    parent = current;
     current = current.right;
     }
     else
     break; // Element is in the tree pointed by current
     }

     if (current == null)
     return false; // Element is not in the tree
    if (current.left == null) {
     // Connect the parent with the right child of the current node
     if (parent == null) {
     root = current.right;
     }
     else {
     if (element.compareTo(parent.element) < 0)
     parent.left = current.right;
     else
     parent.right = current.right;
     // Balance the tree if necessary
     balancePath(parent.element);
     }
     }
     else {
     // Case 2: The current node has a left child
     // Locate the rightmost node in the left subtree of
     // the current node and also its parent
     TreeNode<E> parentOfRightMost = current;
     TreeNode<E> rightMost = current.left;

     while (rightMost.right != null) {
     parentOfRightMost = rightMost;
     rightMost = rightMost.right; // Keep going to the right
     }

     // Replace the element in current by the element in rightMost
     current.element = rightMost.element;

     // Eliminate rightmost node
    if (parentOfRightMost.right == rightMost)
    parentOfRightMost.right = rightMost.left;
     else
     // Special case: parentOfRightMost is current
     parentOfRightMost.left = rightMost.left;

     // Balance the tree if necessary
     balancePath(parentOfRightMost.element);
     }

     size--;
     return true; // Element insert
     // Case 1: current has no left children (See Figure 23.6)
        }

        private void updateHeight(AVLTreeNode<E> avlTreeNode) {
            throw new UnsupportedOperationException("Not yet implemented");
        }
        protected static class AVLTreeNode<E extends Comparable<E>>
        extends BinaryTree.TreeNode<E> {
            int height = 0;
            public AVLTreeNode(E o) {
                super(o);
            }
        }
    }
     
     
    Last edited: Mar 22, 2012
  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?



Similar Discussions: AVLTree program and Binary Tree program help
  1. Mathcad programming (Replies: 0)

Loading...