Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 2 of 2

Thread: Balanced Binary Search Tree

  1. #1
    Junior Member
    Join Date
    Jun 2011
    Posts
    16
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default 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.
    Attached Images Attached Images
    Last edited by D3158; June 23rd, 2011 at 10:41 PM.


  2. #2
    Crazy Cat Lady KevinWorkman's Avatar
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    5,424
    My Mood
    Hungover
    Thanks
    144
    Thanked 636 Times in 540 Posts

    Default Re: Balanced Binary Search Tree

    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.
    Useful links: How to Ask Questions the Smart Way | Use Code Tags | Java Tutorials
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

Similar Threads

  1. Binary Search Tree
    By lex25288 in forum Algorithms & Recursion
    Replies: 3
    Last Post: January 19th, 2011, 09:10 AM
  2. Left and Right rotation in a balanced binary tree problem
    By szuwi in forum Algorithms & Recursion
    Replies: 2
    Last Post: December 22nd, 2010, 07:20 PM
  3. Data Structures(Binary Search Tree to AVL Tree)ASAP
    By jfAdik in forum Algorithms & Recursion
    Replies: 2
    Last Post: April 5th, 2010, 03:58 AM
  4. Binary Search Tree
    By Koren3 in forum What's Wrong With My Code?
    Replies: 9
    Last Post: November 12th, 2009, 09:27 AM
  5. Binary Search Tree implementation
    By Ceasar in forum Java Theory & Questions
    Replies: 3
    Last Post: October 9th, 2009, 12:23 AM