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));
}
}