- Joined
- Jun 13, 2011
- Messages
- 15
Hi guys, specifically Dr.SuperGood, who is probably reading this.
I have a unbalanced binary tree and I show you the description of what I am doing. I just don't know how to make it "balanced" binary search tree. Please help.
BinarySearchTree
BinarySearchTreeADT
DuplicateElementException
Lab4
I have updated my BinarySearchTree.java. I think it's > BALANCED Binary Search Tree. However, I dont know how to make Iterator to work with Stacks. Can someone assist me please?
I have a unbalanced binary tree and I show you the description of what I am doing. I just don't know how to make it "balanced" binary search tree. Please help.
BinarySearchTree
Code:
package util;
import java.util.Iterator;
import java.util.NoSuchElementException;
/**
* A <code>BinarySearchTree</code>(BST) implements the <code>BinarySearchTreeADT</code>
* interface, allowing <code>Comparable</code> objects to be inserted or
* removed. At all times, the tree is balanced (i.e. -1 <= balance factor <= 1
* at every node in the tree).
*
* <p>The <code>BinarySearchTree</code> has two constructors:
* <ul>
* <li>a default constructor</li>
* <li>a constructor that has a <code>Comparable</code> item as a parameter</li>
* </ul></p>
* <p>The public methods implement the <code>BinarySearchTreeADT</code> interface.</p>
* <p>The implementation of this class is the lab 4 assignment for COMP 139 students.</p>
*/
public class BinarySearchTree implements BinarySearchTreeADT {
private static final String INDENT = " ";
private Node root; // The root of the BST.
/**
* Create a blank String that consists of a set of indents.
* @param indent the number of indents.
* @return a String that contains 'indent' * INDENT.length() spaces.
*/
private static String makeIndents(int indent) {
String result = "";
for (int i = 0; i < indent; i++) {
result = result + BinarySearchTree.INDENT;
}
return result;
}
@Override
public final void add(Comparable item) {
this.root = addIterative(item, this.root);
}
private Node addIterative(Comparable item, Node n) {
Node originalTree = n;
// If the tree is empty, just create a new tree with one node.
if (n == null) {
Node newNode = new Node();
newNode.item = item;
return newNode;
}
// Find the insertion point.
while (n != null) {
int compare = item.compareTo(n.item);
// Duplicate items are not allowed.
if (compare == 0) throw new DuplicateElementException();
// See if item belongs in the left subtree.
if (compare < 0) {
// If there is space then add a new node; otherwise,
// keep looking for space.
if (n.left == null) {
n.left = new Node();
n.left.item = item;
//break; // Node added, don't look any more.
return balanceTree();
}
else n = n.left;
}
// The item must belong in the right subtree.
else {
// If there is space then add a new node; otherwise,
// keep looking for space.
if (n.right == null) {
n.right = new Node();
n.right.item = item;
//break; // Node added, don't look any more.
return balanceTree();
}
else n = n.right;
}
}
return originalTree;
}
private Node balanceTree(){
if (root.getBalanceFactor()!= 2 && root.getBalanceFactor()!= 2) return root;
Node newRootHere = new Node();
if (root.getBalanceFactor() == -2 && root.left.getBalanceFactor()== -1) {
newRootHere = rightRotation(root, root.left);
}
if (root.getBalanceFactor()== 2 && root.right.getBalanceFactor()== 1) {
newRootHere = leftRotation(root, root.right);
}
if (root.getBalanceFactor()== 2 && root.right.getBalanceFactor()== -1) {
Node tempNode = rightRotation(root.right,root.right.left);
newRootHere = leftRotation(root, tempNode);
}
if (root.getBalanceFactor()== -2 && root.left.getBalanceFactor()== 1) {
newRootHere = leftRotation(root, root.left);
}
if (root.getBalanceFactor()== 2 && root.right.getBalanceFactor()== 0) {
newRootHere = leftRotation(root, root.right);
}
if (root.getBalanceFactor()== -2 && root.left.getBalanceFactor()== 0) {
newRootHere = rightRotation(root, root.left);
}
return newRootHere;
}
private Node leftRotation(Node oldRoot, Node newRoot){
Node newroot = newRoot;
oldRoot.right = newroot.left;
newroot.left = oldRoot;
return newroot;
}
private Node rightRotation(Node oldRoot, Node newRoot){
Node newroot = newRoot;
oldRoot.left = newroot.right;
newroot.right = oldRoot;
return newroot;
}
@Override
public Iterator<Comparable> iterator() /*throws ConcurrentModificationException,
UnsupportedOperationException*/ {
return new BinarySearchTreeIterator();
}
private final class BinarySearchTreeIterator implements Iterator<Comparable> {
//private int root;
private BinarySearchTreeIterator() {
//this.root = 0;
}
@Override
public boolean hasNext() {
throw new UnsupportedOperationException("Not supported yet.");
}
@Override
public Comparable next() {
throw new UnsupportedOperationException("Not supported yet.");
}
@Override
public void remove() {
throw new UnsupportedOperationException("Not supported yet.");
}
}
@Override
public String printTree() {
if (this.root == null) return "";
return "\n" + printTree(this.root, 0);
}
/**
* Create a string representation for a subtree of a binary search tree.
* @param root the node at the root of the subtree.
* @param level the node level (in the entire tree) for the root of this subtree.
* @return a diagram, as a <code>String</code>, that represents this subtree.
*/
private String printTree(Node root, int level) {
String result = "";
if (root.right != null) {
result = result + printTree(root.right, level + 1);
}
result = result + makeIndents(level) + root.item.toString() +
"(" + root.getBalanceFactor() + ")\n";
if (root.left != null) {
result = result + printTree(root.left, level + 1);
}
return result;
}
@Override
public void remove(Comparable item) {
//this.root = removeIterativeAlmost(item, this.root);
this.root = removeIterativeAlmost(item, this.root);
}
private Node removeIterativeAlmost(Comparable item, Node n) {
// Find the node that contains the item to be removed and
// the parent of that node.
Node parent = null;
Node toremove = n;
while (toremove != null) {
// Check to see if the item has been found.
int compare = item.compareTo(toremove.item);
if (compare == 0) break;
// If not found, look in the appropriate subtree.
parent = toremove;
if (compare < 0) toremove = toremove.left;
else toremove = toremove.right;
}
// Item was either found (toremove != null) or the item is not in the
// tree (toremove == null).
if (toremove == null) throw new NoSuchElementException();
// If the node to be removed has no more than one child
// then replace it with the other child.
if (toremove.left == null) {
replaceChildNodeInParent(parent, toremove, toremove.right);
return n;
}
if (toremove.right == null) {
replaceChildNodeInParent(parent, toremove, toremove.left);
return n;
}
// The node to remove has two children.
// 1. Find a replacemant value.
// 2. Replace the value in the node to remove.
// 3. Remove the node that contains the replacement value.
Comparable largest = findLargest(toremove.left);
toremove.item = largest;
toremove.left = removeIterativeAlmost(largest, toremove.left);
return n;
}
private void replaceChildNodeInParent(
Node parent, Node currentchild, Node newchild) {
if (parent == null) this.root = newchild;
else if (parent.left == currentchild) parent.left = newchild;
else parent.right = newchild;
}
/**
* Find the largest value in the tree with 'n' as its root.
* @param n the root of the tree.
* @return the rightmost value in the tree.
*/
private Comparable findLargest(Node n) {
while (n.right != null) {
n = n.right;
}
return n.item;
}
/**
* Find the smallest value in the tree with 'n' as its root.
* @param n the root of the tree.
* @return the leftmost value in the tree.
*/
private Comparable findSmallest(Node n) {
while (n.left != null) {
n = n.left;
}
return n.item;
}
/**
* Define the data structure of a node in a balanced binary search tree.
*/
private class Node {
private Comparable item; // The data item.
private Node left; // The root of the left subtree.
private Node right; // The root of the right subtree.
/**
* Determine the balance factor for this node.
* @return the difference between the right height and the left height.
*/
private int getBalanceFactor() {
// Note: This code needs to be replaced. It is here so that printTree()
// has a working getBalanceFactor() method to use.
//return -999;
int leftHeight = (left == null)?0:left.height();
int rightHeight = (right == null)?0:right.height();
return rightHeight - leftHeight;
}
private int height(){
int leftHeight = (left == null)?0:left.height();
int rightHeight = (right == null)?0:right.height();
return 1 + Math.max(leftHeight, rightHeight);
}
}
}BinarySearchTreeADT
Code:
package util;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
/**
* Defines a <code>BinarySearchTreeADT</code>. A binary search tree is a
* data structure that allows items to be added and removed and whose items
* are organized into a binary tree structure such that, at any node 'x' in
* the tree, all items in the left subtree at 'x' are less than the item at 'x'
* and all items in the right subtree at 'x' are greater than the item at 'x'.
* <p>Note: This definition means that duplicate items are <em>NOT</em>
* allowed in a binary search tree.</p>
* @author Paul Rushton
*/
public interface BinarySearchTreeADT {
/**
* Add an item to the tree.
* @param item the <code>Comparable</code> to be added.
* @throws DuplicateElementException if an item to be added is equivalent
* to one that is already in the tree.
*
* Note: The tree is re-balanced after each <code>add()</code> operation.
*/
public void add(Comparable item) throws DuplicateElementException;
/**
* Obtain an <code>Iterator<Comparable></code> for the tree.
* @return an iterator that visits the items in the tree using an in-order
* traversal.
* @throws <code>ConcurrentModificationException</code> in the face of
* concurrent modification.
* @throws <code>UnsupportedOperationException</code> if the
* <code>remove()</code> method is used.
*/
public Iterator<Comparable> iterator() throws ConcurrentModificationException,
UnsupportedOperationException;
/**
* Obtains a <code>String</code> representation for the tree.
* @return A string that graphically shows the tree structure.
*
* Note: If the <code>String</code> is printed then the output will be
* in the shape of a tree with the root node at the left, the right subtree
* above and to the right of the root, and the left subtree below and to
* the right of the root. The balance factors for each node are shown in
* parentheses beside the node.
*/
public String printTree();
/**
* Remove an item from the tree.
* @param item the <code>Comparable</code> to be removed.
*
* Note: The tree is re-balanced after the <code>remove()</code> operation.
*/
public void remove(Comparable item);
}DuplicateElementException
Code:
package util;
/**
* Defines the the condition of detecting a duplicate element in a collection.
* @author D3158
*/
public class DuplicateElementException extends RuntimeException {
}Lab4
Code:
public class BST {
// Change this next line to your name.
private static final String NAME = "D3158";
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
BinarySearchTree tree = new BinarySearchTree();
System.out.println("BBST: " + BST.NAME);
System.out.println("= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =");
tree.add("Eve");
tree.add("Pam");
tree.add("Zoe");
tree.add("Cam");
tree.add("Lee");
tree.add("Joy");
System.out.println("\nBinary search tree after add: Eve Pam Zoe Cam Lee Joy");
System.out.print(tree.printTree());
System.out.println("= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =");
tree.add("Ivy");
tree.add("Abe");
tree.add("Fay");
System.out.println("\nBinary search tree after add: Ivy Abe Fay");
System.out.print(tree.printTree());
System.out.println("= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =");
System.out.println("\nIterator output\n");
for (Iterator<Comparable> it = tree.iterator(); it.hasNext();) {
System.out.print(it.next() + " ");
}
System.out.println("\n\n= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =");
tree.remove("Lee");
tree.remove("Cam");
tree.remove("Abe");
System.out.println("\nBinary search tree after remove: Lee Cam Abe");
System.out.print(tree.printTree());
System.out.println("= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =");
}
}I have updated my BinarySearchTree.java. I think it's > BALANCED Binary Search Tree. However, I dont know how to make Iterator to work with Stacks. Can someone assist me please?
Last edited:
