Shana8426 0 Newbie Poster

Hi

I have to create an iterative insert for an avl tree and I have to use enumeration for my balance factors. My enumeration is

enum balanceFactor {TILTS_LEFT, BALANCE, TILTS_RIGHT}

Please help me. I have been struggling with this for almost 2 weeks.

When I enter input such as 20 and 10, the balance factor for both are balanced and when 20's balance factor is supposed to be TILTS_LEFT and 10 is supposed to be BALANCED.

Any help would be greatly appreciated

public class BinarySearchTree implements BSTInterface
{
  protected BSTNode root;      // reference to the root of this BST

  boolean found;   // used by remove
  
  // for traversals
  protected ArrayBndQueue inOrderQueue;    // queue of info
  protected ArrayBndQueue preOrderQueue;   // queue of info
  protected ArrayBndQueue postOrderQueue;  // queue of info
  
  int leftHeight = 0;
  int rightHeight = 0;
  //BSTNode pivotNode;
  //BSTNode parentNode;
  boolean taller;

  public BinarySearchTree()
  // Creates an empty BST object.
  {
    root = null;
  }

  public boolean isEmpty()
  // Returns true if this BST is empty; otherwise, returns false.
  {
    return (root == null);
  }

  private int recSize(BSTNode tree)
  // Returns the number of elements in tree.
  {
    if (tree == null)    
      return 0;
    else
      return recSize(tree.getLeft()) + recSize(tree.getRight()) + 1;
  }

  public int size()
  // Returns the number of elements in this BST.
  {
    return recSize(root);
  }

  public int size2()
  // Returns the number of elements in this BST.
  {
    int count = 0;
    if (root != null)
    {
      LinkedStack hold = new LinkedStack();
      BSTNode currNode;
      hold.push(root);
      while (!hold.isEmpty())
      {
        currNode = (BSTNode) hold.top();
        hold.pop();
        count++;
        if (currNode.getLeft() != null)
          hold.push(currNode.getLeft());
        if (currNode.getRight() != null)
          hold.push(currNode.getRight());
      }
    }
    return count;
  }

  private boolean recContains(Comparable element, BSTNode tree)
  // Returns true if tree contains an element e such that 
  // e.compareTo(element) == 0; otherwise, returns false.
  {
    if (tree == null)
      return false;       // element is not found
    else if (element.compareTo(tree.getInfo()) < 0)
      return recContains(element, tree.getLeft());   // Search left subtree
    else if (element.compareTo(tree.getInfo()) > 0)
      return recContains(element, tree.getRight());  // Search right subtree
    else
      return true;        // element is found
  }

  public boolean contains (Comparable element)
  // Returns true if this BST contains an element e such that 
  // e.compareTo(element) == 0; otherwise, returns false.
  {
    return recContains(element, root);
  }
  
  private Comparable recGet(Comparable element, BSTNode tree)
  // Returns an element e from tree such that e.compareTo(element) == 0;
  // if no such element exists, returns null.
  {
    if (tree == null)
      return null;             // element is not found
    else if (element.compareTo(tree.getInfo()) < 0)
      return recGet(element, tree.getLeft());          // get from left subtree
    else
    if (element.compareTo(tree.getInfo()) > 0)
      return recGet(element, tree.getRight());         // get from right subtree
    else
      return tree.getInfo();  // element is found
  }

  public Comparable get(Comparable element)
  // Returns an element e from this BST such that e.compareTo(element) == 0;
  // if no such element exists, returns null.
  {
    return recGet(element, root);
  }
  
  public int leftHeight(BSTNode node)
   {
     int left;
     
      if (node == null)
         return 0;
      else
      {
         left = leftHeight(node.left) + 1; 
      }

     return left;
   }
  
  public int rightHeight(BSTNode node)
   {
     int right;
     
      if (node == null)
         return 0;
      else
      {
         right = rightHeight(node.right) + 1; 
      }

     return right;
   }
  
  public void add (Comparable element)
  {
     BSTNode newNode = new BSTNode(element);    	// make new node

      if(root==null)             		// no node in root
      {
         root = newNode;
      }
      else   
      {                      	// root occupied
         BSTNode current = root;       	// start at root
         BSTNode parent;
         while(true) // (exits internally)
         {              	
            parent = current;
            if(Integer.parseInt(element.toString()) < Integer.parseInt(current.info.toString())){ 	// go left?
               current = current.left;
               if(current == null) // if end of the line
               { 	
                  parent.left = newNode;    // insert on left
                  return;
               }

               if(taller)        /* left subtree was taller  */
               {
                  switch(parent.bFactor)
                  {
                     case TILTS_LEFT:                      /* node was left high       */
                     parent = leftBalance(parent,taller);
                     break;

                     case BALANCED:                      /* make node left high      */
                     parent.bFactor = balanceFactor.TILTS_LEFT;
                     break;

                     case TILTS_RIGHT:                       /* node now balanced height */
                     parent.bFactor = balanceFactor.BALANCED;
		     taller = false;   /* FALSE */
                     break;
                  }
               }
            }  // end if go left
            else // or go right
            {                  	
               current = current.right;
               if(current == null)  // if end of the line
               { 	
                  parent.right = newNode;  // insert on right
                  return;
               }
               
               if(taller)                           /* right subtree is taller  */
               {
                 switch(parent.bFactor)
                 {
                     case TILTS_LEFT:
                     parent.bFactor = balanceFactor.BALANCED;   /* node now balanced height */
	             taller = false;   /* FALSE */
                      break;

                     case BALANCED:                      /* make node right high     */
                     parent.bFactor = balanceFactor.TILTS_RIGHT;
                     break;

                    case TILTS_RIGHT:                      /* node was right high      */
                    parent = rightBalance(parent,taller);
                    break;
                 }
              }
            }  // end else go right
         }  // end while
      }  
  }
  
  public BSTNode rotateLeft(BSTNode node)
  {
    BSTNode rightChild = node;
    
    if(node == null)
         System.out.println("node for rotateLeft is empty");
    else if(node.right == null)
         System.out.println("node.right for rotateLeft is empty");
    else
    {
       rightChild = node.right;
       node.right = rightChild.left;
       rightChild.left = node;
    }
    
    return rightChild;
  }
  
  public BSTNode rotateRight(BSTNode node)
  {
     BSTNode leftChild = node.left;
     
     node.left = leftChild.right;
     leftChild.right = node;
     return leftChild;
  }
  
  public BSTNode leftBalance(BSTNode node, boolean isTaller)
  {
    BSTNode rightTree, leftTree;

    leftTree = node.left;

switch(leftTree.bFactor)
{
    case TILTS_LEFT:
    node.bFactor = balanceFactor.BALANCED;
    leftTree.bFactor = balanceFactor.BALANCED;
    node = rotateRight(node);
    isTaller = false;
    break;
    
    case BALANCED:
    System.out.println("Tree is already balanced");
    break;
    
    case TILTS_RIGHT:
    rightTree = leftTree.right;
    
    switch(rightTree.bFactor)
    {
        case TILTS_LEFT:
            node.bFactor = balanceFactor.TILTS_RIGHT;
            leftTree.bFactor = balanceFactor.BALANCED;
            break;
        case BALANCED:
            node.bFactor = balanceFactor.BALANCED;
            leftTree.bFactor = balanceFactor.BALANCED;
             break;
        case TILTS_RIGHT:
            node.bFactor = balanceFactor.BALANCED;
            leftTree.bFactor = balanceFactor.TILTS_LEFT;
            break;
    }
    rightTree.bFactor= balanceFactor.BALANCED;
     node.left = rotateLeft (leftTree);
     node = rotateRight(node);
     isTaller = false;
     break;
  }
  return node;
}
 
  public BSTNode rightBalance(BSTNode node, boolean isTaller)
  {
      BSTNode rightTree, leftTree;

       rightTree = node.right;

    switch (rightTree.bFactor)
    {
        case TILTS_RIGHT:
            node.bFactor = balanceFactor.BALANCED;
            rightTree.bFactor = balanceFactor.BALANCED;
            node = rotateLeft(node);
            isTaller = false;
            break;
            
             case BALANCED:
            System.out.println("Tree is already balanced");
            break;
            
             case TILTS_LEFT:
            leftTree = rightTree.left;
            
            switch (leftTree.bFactor)
            {
                 case TILTS_LEFT:
                  node.bFactor = balanceFactor.TILTS_LEFT;
                 rightTree.bFactor = balanceFactor.BALANCED;
                 break;

                 case BALANCED:
                 node.bFactor = balanceFactor.BALANCED;
                 rightTree.bFactor = balanceFactor.BALANCED;
                 break;

                 case TILTS_RIGHT:
                 node.bFactor = balanceFactor.BALANCED;
                 rightTree.bFactor = balanceFactor.TILTS_RIGHT;
                 break;
    }
    leftTree.bFactor = balanceFactor.BALANCED;
    node.right = rotateRight(rightTree);
    node = rotateLeft(node);
    isTaller = false;
    break;      
  }
   return node;
}
  
  public BSTNode findParent(String element)
  {
     BSTNode p = root;
     BSTNode prev = null;
     
     while(p != null && (p.info.compareTo(element) != 0))
     {
        prev = p;
        if(p.info.compareTo(element) < 0)
           p = p.right;
        else
           p = p.left;
     }
     return prev;
  }

  
  private Comparable getPredecessor(BSTNode tree)
  // Returns the information held in the rightmost node in tree
  {
    while (tree.getRight() != null)
      tree = tree.getRight();
    return tree.getInfo();
  }

  private BSTNode removeNode(BSTNode tree)
  // Removes the information at the node referenced by tree.
  // The user's data in the node referenced by tree is no
  // longer in the tree.  If tree is a leaf node or has only
  // a non-null child pointer, the node pointed to by tree is
  // removed; otherwise, the user's data is replaced by its
  // logical predecessor and the predecessor's node is removed.
  {
    Comparable data;

    if (tree.getLeft() == null)
      return tree.getRight();
    else if (tree.getRight() == null) 
      return tree.getLeft();
    else
    {
      data = getPredecessor(tree.getLeft());
      tree.setInfo(data);
      tree.setLeft(recRemove(data, tree.getLeft()));  
      return tree;
    }
  }

  private BSTNode recRemove(Comparable element, BSTNode tree)
  // Removes an element e from tree such that e.compareTo(element) == 0
  // and returns true; if no such element exists, returns false. 
  {
    if (tree == null)
      found = false;
    else if (element.compareTo(tree.getInfo()) < 0)
      tree.setLeft(recRemove(element, tree.getLeft()));
    else if (element.compareTo(tree.getInfo()) > 0)
      tree.setRight(recRemove(element, tree.getRight()));
    else  
    {
      tree = removeNode(tree);
      found = true;
	 }
    return tree;
  }

  public boolean remove (Comparable element)
  // Removes an element e from this BST such that e.compareTo(element) == 0
  // and returns true; if no such element exists, returns false. 
  {
    root = recRemove(element, root);
    return found;
  }

  private void inOrder(BSTNode tree)
  // Initializes inOrderQueue with tree elements in inOrder order.
  {
    if (tree != null)
    {
      inOrder(tree.getLeft());
      inOrderQueue.enqueue(tree.getInfo());
      inOrder(tree.getRight());
    }
  }

  private void preOrder(BSTNode tree)
  // Initializes preOrderQueue with tree elements in preOrder order.
  {
    if (tree != null)
    {
      preOrderQueue.enqueue(tree.getInfo());
      preOrder(tree.getLeft());
      preOrder(tree.getRight());
    }
  }

  private void postOrder(BSTNode tree)
  // Initializes postOrderQueue with tree elements in postOrder order.
  {
    if (tree != null)
    {
      postOrder(tree.getLeft());
      postOrder(tree.getRight());
      postOrderQueue.enqueue(tree.getInfo());
    }
  }

  public int reset(int orderType)
  // Initializes current position for an iteration through this BST
  // in orderType order. Returns current number of nodes in the BST.
  {
    int numNodes = size();
    if (orderType == INORDER)
    {
      inOrderQueue = new ArrayBndQueue(numNodes);
      inOrder(root);
    }
    else
    if (orderType == PREORDER)
    {
      preOrderQueue = new ArrayBndQueue(numNodes);
      preOrder(root);
    }
    if (orderType == POSTORDER)
    {
      postOrderQueue = new ArrayBndQueue(numNodes);
      postOrder(root);
    }
    return numNodes;
  }
  
  public String toString(BSTNode node)
  {
     String result = "";
     
     if(node != null)
      {
         result = toString(node.left);
         System.out.println("Node: " + node.info.toString() + 
                            "   Balance factor: " + node.bFactor);
         result = toString(node.right);
      }
     
     return result;
  }
  
  public Comparable getNext (int orderType)
  // Preconditions: The BST is not empty
  //                The BST has been reset for orderType
  //                The BST has not been modified since the most recent reset
  //                The end of orderType iteration has not been reached
  //
  // Returns the element at the current position on this BST for orderType
  // and advances the value of the current position based on the orderType. 
  {
    if (orderType == INORDER)
      return (Comparable)inOrderQueue.dequeue();
    else
    if (orderType == PREORDER)
      return (Comparable)preOrderQueue.dequeue();
    else
    if (orderType == POSTORDER)
      return (Comparable)postOrderQueue.dequeue();
    else return null;
  }
}

This is my code for the BSTNode class:

import java.util.*;

enum balanceFactor { TILTS_LEFT, BALANCED, TILTS_RIGHT };

public class BSTNode 
{
  // Used to hold references to BST nodes for the linked implementation
  protected Comparable info;       // The info in a BST node
  protected BSTNode left;          // A link to the left child node
  protected BSTNode right;         // A link to the right child node

  protected balanceFactor bFactor;

  public BSTNode(Comparable info)
  {
    this.info = info;
    this.left = null;
    this.right = null;
    this.bFactor = balanceFactor.BALANCED;
  }
 
  public void setInfo(Comparable info)
  // Sets info of this BSTNode.
  {
    this.info = info;
  }

  public Comparable getInfo()
  // Returns info of this BSTNode.
  {
    return info;
  }
 
  public void setLeft(BSTNode link)
  // Sets left link of this BSTNode.
  {
    left = link;
  }

  public void setRight(BSTNode link)
  // Sets right link of this BSTNode.
  {
    right = link;
  }

  public BSTNode getLeft()
  // Returns left link of this BSTNode.
  {
    return left;
  }

  public BSTNode getRight()
  // Returns right link of this BSTNode.
  {
    return right;
  }
}

This is my driver class

import java.util.*; 
import java.util.regex.*;

public class BST_Driver 
{
   public static void main(String[] args) 
   {

       Scanner scan = new Scanner(System.in).useDelimiter(" ");
       BinarySearchTree bsTree = new BinarySearchTree();
       String input = "";
       String storeInput = "";
       
       //Prompts the user to enter the list of integers
       System.out.println("Enter your input: \n");
       input = scan.nextLine();
       
       Scanner scan2 = new Scanner(input);

           while(scan2.hasNext())
           {
               storeInput = scan2.next();
               
               //Exits the loop if the sentinel value 0 is entered
               if(storeInput.equals("0"))
               {
                  System.out.println("Sentinel value entered. Exiting loop");
                  break;
               }
               
               //Determine if the input is valid
               if(storeInput.matches("\\d+")) //Numbers that are 0 and greater
               {
                  if(!bsTree.contains((Comparable) storeInput))
                      bsTree.add((Comparable) storeInput);  
               }
               else //Do not accept negative numbers or non-digits
               { 
                  System.err.println("Invalid input: " + storeInput);
               }
           }
       
        System.out.println("\n\n");
       
       //Displays the tree
         bsTree.toString(bsTree.root);

         System.out.println("left tree: " + bsTree.leftHeight(bsTree.root));
         System.out.println("right tree: " + bsTree.rightHeight(bsTree.root));
   }
}