Thread: Balanced Binary Search Tree

I had to make a Balanced Binary Search Tree and I think I have it right but would like your opinion whether I am right or not, please.

Here is the code that I wrote for it:

 
package util;
import java.util.Iterator;
import java.util.NoSuchElementException;
/*Author: D3158*/
/**
 * 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(){
  // Create a new node then use get getBalanceFactor to get balance rotation 
  // by calling left rotation, right rotation, left right rotation, left right 
  // rotation
      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){
// Pushes a node down and to the left to balance the tree. 
// Right child replaces the old one to the new right child's
// left child and becomes it's right child
    Node newroot = newRoot;
    oldRoot.right = newroot.left;
    newroot.left = oldRoot;
    return newroot;
}
 
private Node rightRotation(Node oldRoot, Node newRoot){
// Pushes a node down and to the right to balance the tree. 
// Left child replaces the old one to the new left child's
// right child and becomes it's left child
    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);
   }
 }
}

Below is the output diagram

UUOutput.jpg


Also, I am having hard time doing the iterator using ArrayList. I tried to do it with Stack but I don't know where to begin. Algorithm or pseudo code or the code, whatever you like to share with me, is appreciated.


Thank you


ps. I have other files to go with this so let me know if you would like to take a look at it.

That's waaay too much code for anybody to go through. We have hundreds of posts here, so we don't have time to read through code dumps like that.

Does it work? Does it do what you expect it to? If so, it really doesn't matter what we think.

As for your question about iterators, where are you stuck? What have you tried? Post an SSCCE demonstrating the problem, and we can go from there.