Height Balancing Search Trees Using JAVA

Hey, so it’s been a while since I made a post. I have been very busy with school. Now that its summer and I’m only taking one summer class and working, I have some extra time to put into making more posts.

I figured I could share some of what I learned about and worked on this semester in some of my classes. One of the major topics I learned about was Binary Trees and some of the many variations they can be implemented in. Binary Trees are really a family of data structures used to store, and organize data so that it is easily accessible. The project I have for you today implements both a Red and Black Tree, and a Splay Tree, both of which are sub-classes of the Height Balancing Tree SuperClass which uses java generics. Portions of the code was written by my professor, and other portions were written by myself.

For those of you who want to implement this project on your own. The project should be organized into five files in a source package named “Collection”. I will write the file name above each block of code respectively.

• File name: “Collection.java”
  This file is an interface which both the RedBlack Tree file and the Splay Tree file both implement. It contains the generic methods that both types of trees need.

  
  package collection;
  
  /**
   * Interface for a collection class. 
   * @author Nathaniel Kell
   * @param  type of objects in the collection. 
  */
  public interface Collection{
      
      /**
       * Insert an element into the collection.
       * @param element: object to be inserted
       */ 
      public void insert(T element);
      
      /**
       * Delete an element from the collection.
       * @param element: object to be deleted
       * @return true if the element was deleted (false otherwise).
       */ 
      public boolean delete(T element);
      
       /**
       * Check if an element exists in the collection.
       * @param element: object to be checked for containment.
       * @return true if the element exists in the collection (false otherwise).
       */ 
      public boolean contains(T element);
      
      /**
       * Returns the number of elements in the collection.
       * @return size of the collection.
       */
      public int getSize(); 
      
  }
  

• File name: “HeightBalancedTree.java”
  This file contains an abstract class from which Redblack Tree and Splay tree both extend.

  
  package collection;
  import java.util.*;
  
  /**
   * Abstract class for height balancing trees to extend from.
   * @author *Kyle Supple*, Nathaniel Kell
   * @param  type of objects in the tree. 
   */
  public abstract class HeightBalancedTree> implements Collection{
      Node root; 
      int size; 
      Node nullNode; // node to serve as null pointer 
      
      /* Indices for the nodes returned by deleteNode() */
      protected final static int DELETED = 0; 
      protected final static int REPLACED = 1; 
      protected final static int PARENT = 2;
          
      /* Node class used for storing the structure of the tree */
      protected class Node{ 
          protected Node left, right, parent;
          protected T data;
          
          protected Node(Node l, Node r, Node p , T d){
              left = l; 
              right = r; 
              parent = p; 
              data = d; 
          }
      }
      
      /* Construct an emepty height balancing tree */
      public HeightBalancedTree(){
          size = 0; 
          nullNode = null; 
          root = nullNode;
      }
         
      /**
       * Balances the tree after an insertion (starting at node n).
       * @param n : node where balancing procedure begins
       */
      protected abstract void insertionFix(Node n); 
      
       /**
       * Balances the tree after a deletion.
       * @param del : node that was just deleted from the tree.
       * @param replace: node that took the place del in the tree. 
       * @param parent: parent of del. 
       */
      protected abstract void deletionFix(Node del, Node replace, Node parent);
      
      @Override 
      public int getSize(){
          return size; 
      }
      
      @Override 
      public boolean contains(T element){
          return findNode(element) != nullNode;
      }  
      
       /**
       * Insert a new node into the tree and return the newly constructed node.
       * @param element : element to be inserted into the tree.
       * @return : newly inserted node. 
       */
      protected Node insertNode(T element){
          Node current = root;
          Node par = nullNode; 
          boolean left = false; // whether we take left or right links
          
          /* Find the correct location to insert */
          while(current != nullNode){
              par = current; 
              if (current.data.compareTo(element) >= 0){
                  current = current.left;
                  left = true; 
              }
              else{
                  current = current.right; 
                  left = false;
              }
          }
          
          Node newNode = new Node(nullNode, nullNode, par, element);
          
          /* Check if new node is the root */
          if(par == nullNode)
              root = newNode;
          /* Set up parent links */
          else if(left == true)
              par.left = newNode;
          else
              par.right = newNode;
  
          return newNode; 
      }
      
       /**
       * Deletes a node from the tree with data equal to element. 
       * @param element : element to be deleted from the tree.
       * @return an array list that contains the node deleted, the node 
       * that replaced it, and the parent of the deleted node. 
       */
      public ArrayList> deleteNode(T element){
          Node del = findNode(element);
          Node replace = nullNode; 
          Node parent = nullNode; 
          ArrayList> ret = new ArrayList();
          
          ret.add(del);
          ret.add(replace);
          ret.add(parent);
      
          /* The node does not exist in the tree */
          if(del != nullNode){
              /* Case 1: left is null */
              if(del.left == nullNode){
                  replace = del.right; 
                  setParentLink(del.parent, del, del.right);
              }
              /* Case 2: right is null */
              else if(del.right == nullNode){
                  replace = del.left;
                  setParentLink(del.parent, del, del.left);
              }  
              /* Case 4: two children */
              else{
                  Node successor = findMinNode(del.right);
                  del.data = successor.data; 
                  setParentLink(successor.parent, successor, successor.right);     
              
                  /* In this case, we've deleteed successor, and its right 
                  child has taken its place */
                  del = successor; 
                  replace = del.right;
              }
          
              ret.set(DELETED,del);
              ret.set(REPLACED,replace);
              ret.set(PARENT, del.parent);
          }
          return ret;
      }
   
      /**
       * Searches for and returns a node with data equal to element. 
       * @param element: method finds a node with data equal to element.
       * @return node that has data equal to element.
       */
      protected Node findNode(T element){
          Node current = root;
          while(current != nullNode){
              if(current.data.equals(element))
                  return current; 
              else if (current.data.compareTo(element) >= 0)
                  current = current.left;
              else 
                  current = current.right; 
          }
          return nullNode;  
      }
      
      /** 
       * Perform a left rotation on the subtree rooted at rotRoot.
       * @param rotRoot: root of the subtree to be rotated.
       */
      protected void leftRotate(Node rotRoot){
          
          //nephew of rotRoot
          Node temp = rotRoot.right.left; 
          
          //Keep track of nodes
          Node LC = rotRoot.right;
          Node RC = rotRoot.left;
          Node P = rotRoot.parent;
  
          //change the parent of rotRoot to rotRoot.right
          setParentLink(rotRoot.right, temp, rotRoot);
  
          //change parent of left child to rotRoot.parent
          setParentLink(P, rotRoot, LC);
  
          //change parent of temp to rotRoot
          setParentLink(rotRoot, LC, temp);
            
          
      }
      
      /** 
       * Perform a right rotation on the subtree rooted at rotRoot.
       * @param rotRoot: root of the subtree to be rotated.
       */
      protected void rightRotate(Node rotRoot){
          
          Node temp = rotRoot.left.right; //nephew of rotRoot
          
          //Keep track of nodes
          Node LC = rotRoot.left;
          Node LGC = rotRoot.left.left;
          Node RC = rotRoot.right;
          Node P = rotRoot.parent;
          
          //change the parent of rotRoot to rotRoot.left
          setParentLink(rotRoot.left, temp, rotRoot);
            
  
          //change left child of rotRoot to temp
          setParentLink(rotRoot, rotRoot.left, temp);
  
          //change the parent of left child to rotRoot.parent
          setParentLink(P, rotRoot, LC);
  
          
      }
  
      /**
       * Find the minimum node the subtree rooted at node n.
       * @param n : starting node of the search
       * @return node with minimum value in the subtree rooted at n.
       */
      protected Node findMinNode(Node n){
          Node cur = n;
          while(cur.left != nullNode)
              cur = cur.left;
          return cur; 
      }
      
      /**
       * Replaces parent's child pointer to child with newChild. 
       * @param par : node to replace child link.
       * @param child : original child of parent.
       * @param newChild : new child of parent.
       */
      protected void setParentLink(Node par, Node child, Node newChild){
          if(newChild != nullNode)
              newChild.parent = par;
          if(par != nullNode){
              
              //If children have the same value, favor right 
              if(child == par.left){
                  if(par.left == par.right && par.data.compareTo(newChild.data) < 0){
                      par.right = newChild;
                  }else{
                      par.left = newChild;
                  }
              }else {
                  par.right = newChild; 
          }}
          else 
              root = newChild; 
      }
      
      /**
       * Return the pre-order representation of the tree
       * @return string containing the pre-order sequence of the tree.
       */
      @Override 
      public String toString(){
          ArrayList stringList = new ArrayList();
          preOrder(root, stringList);
         
          String treeString = "";
          for(int i = 0; i < stringList.size() - 1; i++)
              treeString += stringList.get(i) + ", ";
          treeString += stringList.get(stringList.size()-1);
         
          return treeString;
     }
     
       /**
       * Return the in-order representation of the tree
       * @return string containing the in-order sequence of the tree.
       */
      public String inOrderString(){
          ArrayList stringList = new ArrayList();
          inOrder(root, stringList);
         
          String treeString = "";
          for(int i = 0; i < stringList.size() - 1; i++)
              treeString += stringList.get(i) + ", ";
          treeString += stringList.get(stringList.size()-1);
         
          return treeString;
      }
      
      /**
       * Recursively perform an in-order traversal or the tree.
       * @param cur : current node of the traversal.
       * @param stringList : string that will contain the sequence at the end of search.
       */
      protected void preOrder(Node cur, ArrayList stringList){
         if(cur != nullNode){
             stringList.add(cur.data.toString());
             preOrder(cur.left, stringList);
             preOrder(cur.right, stringList);   
         }   
      }
      
      /**
       * Recursively perform an in-order traversal or the tree.
       * @param cur : current node of the traversal.
       * @param stringList : string that will contain the sequence at the end of search.
       */
      protected void inOrder(Node cur, ArrayList stringList){
         if(cur != nullNode){
             inOrder(cur.left, stringList);
             stringList.add(cur.data.toString());
             inOrder(cur.right, stringList);   
         }   
      } 
     
  }
     

Watch for Part 2 of this post. I will publish the code for the Red Black Tree and the Splay Tree.