Splay tree

profileAndyL
Collection.zip
Home>Computer Science homework help>Splay tree

Collection/build.xml

Builds, tests, and runs the project Collection.

Collection/build/classes/collection/Collection.class

package collection;
public abstract interface Collection {
    public abstract void insert(Object);
    public abstract boolean delete(Object);
    public abstract boolean contains(Object);
    public abstract int getSize();
}

Collection/build/classes/collection/HeightBalancedTree$Node.class

package collection;
public synchronized class HeightBalancedTree$Node {
    protected HeightBalancedTree$Node left;
    protected HeightBalancedTree$Node right;
    protected HeightBalancedTree$Node parent;
    protected Object data;
    protected void HeightBalancedTree$Node(HeightBalancedTree, HeightBalancedTree$Node, HeightBalancedTree$Node, HeightBalancedTree$Node, Object);
}

Collection/build/classes/collection/HeightBalancedTree.class

package collection;
public abstract synchronized class HeightBalancedTree implements Collection {
    HeightBalancedTree$Node root;
    int size;
    HeightBalancedTree$Node nullNode;
    protected static final int DELETED = 0;
    protected static final int REPLACED = 1;
    protected static final int PARENT = 2;
    public void HeightBalancedTree();
    protected abstract void insertionFix(HeightBalancedTree$Node);
    protected abstract void deletionFix(HeightBalancedTree$Node, HeightBalancedTree$Node, HeightBalancedTree$Node);
    public int getSize();
    public boolean contains(Comparable);
    protected HeightBalancedTree$Node insertNode(Comparable);
    public java.util.ArrayList deleteNode(Comparable);
    protected HeightBalancedTree$Node findNode(Comparable);
    protected void leftRotate(HeightBalancedTree$Node);
    protected void rightRotate(HeightBalancedTree$Node);
    protected HeightBalancedTree$Node findMinNode(HeightBalancedTree$Node);
    protected void setParentLink(HeightBalancedTree$Node, HeightBalancedTree$Node, HeightBalancedTree$Node);
    public String toString();
    public String inOrderString();
    protected void preOrder(HeightBalancedTree$Node, java.util.ArrayList);
    protected void inOrder(HeightBalancedTree$Node, java.util.ArrayList);
}

Collection/build/classes/collection/RedBlackTree$RBNode.class

package collection;
public synchronized class RedBlackTree$RBNode extends HeightBalancedTree$Node {
    protected boolean color;
    protected void RedBlackTree$RBNode(RedBlackTree, HeightBalancedTree$Node, HeightBalancedTree$Node, HeightBalancedTree$Node, Object, boolean);
}

Collection/build/classes/collection/RedBlackTree.class

package collection;
public synchronized class RedBlackTree extends HeightBalancedTree {
    private static final boolean RED = 1;
    private static final boolean BLACK = 0;
    public void RedBlackTree();
    public void insert(Comparable);
    public boolean delete(Comparable);
    protected void insertionFix(HeightBalancedTree$Node);
    protected void deletionFix(HeightBalancedTree$Node, HeightBalancedTree$Node, HeightBalancedTree$Node);
    private RedBlackTree$RBNode convertToRBNode(HeightBalancedTree$Node, boolean);
}

Collection/build/classes/collection/SplayTree.class

package collection;
public synchronized class SplayTree extends HeightBalancedTree {
    public void SplayTree();
    public void insert(Comparable);
    public boolean delete(Comparable);
    protected void insertionFix(HeightBalancedTree$Node);
    protected void deletionFix(HeightBalancedTree$Node, HeightBalancedTree$Node, HeightBalancedTree$Node);
    private void splay(HeightBalancedTree$Node);
}

Collection/build/classes/collection/TestHeightBalTrees.class

package collection;
public synchronized class TestHeightBalTrees {
    private static final String[] INORDER;
    private static final String[] ROT_PREORDER;
    private static final String[] SPLAY_PREORDER;
    public void TestHeightBalTrees();
    public static int doTests(HeightBalancedTree, String[], String[]);
    public static void testOne(HeightBalancedTree);
    public static void testTwo(HeightBalancedTree);
    public static void testThree(HeightBalancedTree);
    public static void testFour(HeightBalancedTree);
    public static void testFive(HeightBalancedTree);
    public static void printTestMessage(HeightBalancedTree, int, int[], String[], String[]);
    public static void main(String[]);
    static void <clinit>();
}

Collection/manifest.mf

Manifest-Version: 1.0 X-COMMENT: Main-Class will be added automatically by build

Collection/nbproject/build-impl.xml

Must set src.dir Must set test.src.dir Must set build.dir Must set dist.dir Must set build.classes.dir Must set dist.javadoc.dir Must set build.test.classes.dir Must set build.test.results.dir Must set build.classes.excludes Must set dist.jar Must set javac.includes No tests executed. Must set JVM to use for profiling in profiler.info.jvm Must set profiler agent JVM arguments in profiler.info.jvmargs.agent Must select some files in the IDE or set javac.includes To run this application from the command line without Ant, try: java -jar "${dist.jar.resolved}" Must select one file in the IDE or set run.class Must select one file in the IDE or set run.class Must select one file in the IDE or set debug.class Must select one file in the IDE or set debug.class Must set fix.includes This target only works when run from inside the NetBeans IDE. Must select one file in the IDE or set profile.class This target only works when run from inside the NetBeans IDE. This target only works when run from inside the NetBeans IDE. This target only works when run from inside the NetBeans IDE. Must select one file in the IDE or set run.class Must select some files in the IDE or set test.includes Must select one file in the IDE or set run.class Must select one file in the IDE or set applet.url Must select some files in the IDE or set javac.includes Some tests failed; see details above. Must select some files in the IDE or set test.includes Some tests failed; see details above. Must select some files in the IDE or set test.class Must select some method in the IDE or set test.method Some tests failed; see details above. Must select one file in the IDE or set test.class Must select one file in the IDE or set test.class Must select some method in the IDE or set test.method Must select one file in the IDE or set applet.url Must select one file in the IDE or set applet.url

Collection/nbproject/genfiles.properties

build.xml.data.CRC32=a24dc44d build.xml.script.CRC32=1fd00482 [email protected] # This file is used by a NetBeans-based IDE to track changes in generated files such as build-impl.xml. # Do not edit this file. You may delete it but then the IDE will never regenerate such files for you. nbproject/build-impl.xml.data.CRC32=a24dc44d nbproject/build-impl.xml.script.CRC32=f6a04097 nbproject/[email protected]

Collection/nbproject/private/private.properties

compile.on.save=true user.properties.file=C:\\Users\\nbkell\\AppData\\Roaming\\NetBeans\\8.2\\build.properties

Collection/nbproject/private/private.xml

file:/C:/Users/Nat/Box/CSC%20330%20Spring%202019/homeworks/coding-3-base/Collection/src/collection/Collection.java file:/C:/Users/Nat/Box/CSC%20330%20Spring%202019/homeworks/coding-3-base/Collection/src/collection/SplayTree.java file:/C:/Users/Nat/Box/CSC%20330%20Spring%202019/homeworks/coding-3-base/Collection/src/collection/TestHeightBalTrees.java file:/C:/Users/Nat/Box/CSC%20330%20Spring%202019/homeworks/coding-3-base/Collection/src/collection/RedBlackTree.java file:/C:/Users/Nat/Box/CSC%20330%20Spring%202019/homeworks/coding-3-base/Collection/src/collection/HeightBalancedTree.java

Collection/nbproject/project.properties

annotation.processing.enabled=true annotation.processing.enabled.in.editor=false annotation.processing.processor.options= annotation.processing.processors.list= annotation.processing.run.all.processors=true annotation.processing.source.output=${build.generated.sources.dir}/ap-source-output build.classes.dir=${build.dir}/classes build.classes.excludes=**/*.java,**/*.form # This directory is removed when the project is cleaned: build.dir=build build.generated.dir=${build.dir}/generated build.generated.sources.dir=${build.dir}/generated-sources # Only compile against the classpath explicitly listed here: build.sysclasspath=ignore build.test.classes.dir=${build.dir}/test/classes build.test.results.dir=${build.dir}/test/results # Uncomment to specify the preferred debugger connection transport: #debug.transport=dt_socket debug.classpath=\ ${run.classpath} debug.test.classpath=\ ${run.test.classpath} # Files in build.classes.dir which should be excluded from distribution jar dist.archive.excludes= # This directory is removed when the project is cleaned: dist.dir=dist dist.jar=${dist.dir}/Collection.jar dist.javadoc.dir=${dist.dir}/javadoc excludes= includes=** jar.compress=false javac.classpath= # Space-separated list of extra javac options javac.compilerargs= javac.deprecation=false javac.external.vm=true javac.processorpath=\ ${javac.classpath} javac.source=1.8 javac.target=1.8 javac.test.classpath=\ ${javac.classpath}:\ ${build.classes.dir} javac.test.processorpath=\ ${javac.test.classpath} javadoc.additionalparam= javadoc.author=false javadoc.encoding=${source.encoding} javadoc.noindex=false javadoc.nonavbar=false javadoc.notree=false javadoc.private=false javadoc.splitindex=true javadoc.use=true javadoc.version=false javadoc.windowtitle= main.class=collection.TestHeightBalTrees manifest.file=manifest.mf meta.inf.dir=${src.dir}/META-INF mkdist.disabled=false platform.active=default_platform run.classpath=\ ${javac.classpath}:\ ${build.classes.dir} # Space-separated list of JVM arguments used when running the project. # You may also define separate properties like run-sys-prop.name=value instead of -Dname=value. # To set system properties for unit tests define test-sys-prop.name=value: run.jvmargs= run.test.classpath=\ ${javac.test.classpath}:\ ${build.test.classes.dir} source.encoding=UTF-8 src.dir=src test.src.dir=test

Collection/nbproject/project.xml

org.netbeans.modules.java.j2seproject Collection

Collection/src/collection/Collection.java

Collection/src/collection/Collection.java

package  collection ;

/**
 * Interface for a collection class. 
 * Coding Assignment 3, CSC 330, Spring 2019
 * (Note there is nothing in this file for you to change).
 *  @author  Nathaniel Kell
 *  @param  <T> type of objects in the collection. 
*/
public   interface   Collection < T > {
    
     /**
     * 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 ();  
    
}

 

Collection/src/collection/HeightBalancedTree.java

Collection/src/collection/HeightBalancedTree.java

package  collection ;
import  java . util . * ;

/**
 * Abstract class for height balancing trees to extend from.
 * Coding Assignment 3, CSC 330, Spring 2019
 *  @author  *YOUR NAME HERE*
 *  @param  <T> type of objects in the tree. 
 */
public   abstract   class   HeightBalancedTree < T  extends   Comparable < T >>   implements   Collection < T > {
     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 < T > {  
         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 < T >  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 < T >  del ,   Node < T >  replace ,   Node < T >  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 < T >  insertNode ( T element ){
         Node < T >  current  =  root ;
         Node < T >  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 < T >  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 < Node < T >>  deleteNode ( T element ){
         Node < T >  del  =  findNode ( element );
         Node < T >  replace  =  nullNode ;  
         Node < T >  parent  =  nullNode ;  
         ArrayList < Node < T >>  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 < T >  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 < T >  findNode ( T element ){
         Node < T >  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 ){
         /**
         * 
         * 
         *** WRITE THIS METHOD ***
         * 
         *         
         **/
     }
    
     /** 
     * Perform a right rotation on the subtree rooted at rotRoot.
     *  @param  rotRoot: root of the subtree to be rotated.
     */
     protected   void  rightRotate ( Node  rotRoot ){
          /**
         * 
         * 
         *** WRITE THIS METHOD ***
         * 
         *         
         **/     
     }

     /**
     * 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 < T >  findMinNode ( Node < T >  n ){
         Node < T >  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 < T >  par ,   Node < T >  child ,   Node < T >  newChild ){
         if ( newChild  !=  nullNode )
            newChild . parent  =  par ;
         if ( par  !=  nullNode ){
             if ( child  ==  par . left )
                 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 < String >  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 < String >  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 < T >  cur ,   ArrayList < String >  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 < T >  cur ,   ArrayList < String >  stringList ){
        if ( cur  !=  nullNode ){
           inOrder ( cur . left ,  stringList );
           stringList . add ( cur . data . toString ());
           inOrder ( cur . right ,  stringList );    
        }    
     }  
   
}
   

Collection/src/collection/RedBlackTree.java

Collection/src/collection/RedBlackTree.java

package  collection ;

import  java . util . ArrayList ;

/**
 * Implementation of a red-black tree.
 * Coding Assignment 3, CSC 330, Spring 2019
 * (Note there is nothing in this file for you to change)
 *  @author  Nathaniel Kell
 *  @param  <T> type of objects in the tree. 
 */
public   class   RedBlackTree < T  extends   Comparable < T >>   extends   HeightBalancedTree < T > {
     /* boolean values corresponding to red and black. */
     private   static   final   boolean  RED  =   true ;  
     private   static   final   boolean  BLACK  =   false ;  
    
     /* Modified node class that now has a color value */
     protected   class   RBNode < T >   extends   Node < T > {
         protected   boolean  color ;  
   
         protected   RBNode ( Node  l ,   Node  r ,   Node  p  ,  T d ,   boolean  c ){
             super ( l ,  r ,  p ,  d );
            color  =  c ;  
         }
     }
    
     /* Construct an empty red-black tree */
     public   RedBlackTree (){
         super ();
        nullNode  =   new   RBNode ( null ,   null ,   null ,   null ,  BLACK );  
        nullNode . parent  =  nullNode ;
        nullNode . left  =  nullNode ;
        nullNode . right  =  nullNode ;
        root  =  nullNode ;  
     }
    
    @ Override  
     public   void  insert ( T element ){
         Node < T >  newNode  =  insertNode ( element );  
         RBNode < T >   RBnewNode   =  convertToRBNode ( newNode ,  RED );    
 
         if ((( RBNode ) RBnewNode . parent ). color  ==  RED )
            insertionFix ( RBnewNode );  
        
         (( RBNode ) root ). color  =  BLACK ;  
        size ++ ;  
     }
    
    @ Override  
     public   boolean  delete ( T element ){         
         ArrayList < Node < T >>  delNodes  =  deleteNode ( element );
         Node < T >  del  =  delNodes . get ( DELETED );
         Node < T >  replace  =  delNodes . get ( REPLACED );  
         Node < T >  parent  =  delNodes . get ( PARENT );  
        
         if ( del  ==  nullNode )
             return   false ;
        
         if ((( RBNode ) del ). color  ==  BLACK )
            deletionFix ( del ,  replace ,  parent );

        size -- ;  
         return   true ;  
     }

    @ Override  
     protected   void  insertionFix ( Node < T >  n ){
         RBNode  cur  =   ( RBNode ) n ;  
         while ((( RBNode ) cur . parent ). color  ==  RED ){
            RBNode  grandparent  =   ( RBNode ) cur . parent . parent ;

             /* Meta case 1: cur's parent is a left child of its parent */
             if ( cur . parent  ==  grandparent . left ){
                 RBNode  aunt  =   ( RBNode ) grandparent . right ;  
                 /* Case 1: cur's aunt is red */  
                 if ( aunt . color  ==  RED ){
                    
                     (( RBNode ) cur . parent ). color  =  BLACK ;  
                    aunt . color  =  BLACK ;
                    grandparent . color  =  RED ;  
                    cur  =  grandparent ;  
                 }
                 else {
                     /* Case 2: aunt is black and cur is a right child */
                     if ( cur  ==  cur . parent . right ){
                        leftRotate (( cur . parent ));  
                        cur  =   ( RBNode ) cur . left ;  
                     }
                     /* Case 3: aunt is black and cur is a left child */
                     (( RBNode ) cur . parent ). color  =  BLACK ;
                    grandparent . color  =  RED ;  
                    rightRotate ( grandparent );  
                 }
             }  
             /* Meta case 2: cur's parent is a right child of its parent
             * (each subcase are symmetric to those of meta-case 1) */
             else {
                
                 RBNode  aunt  =   ( RBNode ) grandparent . left ;  
                 if ( aunt . color  ==  RED ){
                     (( RBNode ) cur . parent ). color  =  BLACK ;
                    aunt . color  =  BLACK ;  
                    grandparent . color  =  RED ;  
                    cur  =  grandparent ;  
                 }
                 else {
                     if ( cur  ==  cur . parent . left ){
                        rightRotate (( cur . parent ));  
                        cur  =   ( RBNode ) cur . right ;  
                     }
                     (( RBNode ) cur . parent ). color  =  BLACK ;
                    grandparent . color  =  RED ;  
                    leftRotate ( grandparent );  
                 }
             }    
         }   // end while 
     }
    
    @ Override
     protected   void  deletionFix ( Node < T >  del ,   Node < T >  replace ,   Node < T >  parent ){
         RBNode < T >  cur  =   ( RBNode ) replace ;  
         while ( cur  !=  root  &&  cur . color  ==  BLACK ){
             RBNode < T >  par  =   ( RBNode ) cur . parent ;
             if ( cur  ==  nullNode )
                par  =   ( RBNode ) parent ;
             /* Meta-case 1: cure is a left child */
             if ( cur  ==  par . left ){
                 RBNode < T >  sibling  =   ( RBNode ) par . right ;  
                 /* Case 1: cur's sibling is red */  
                 if ( sibling . color  ==  RED ){
                    sibling . color  =  BLACK ;  
                    par . color  =  RED ;  
                    leftRotate ( par );
                    sibling  =   ( RBNode ) par . right ;  
                 }
                 /* Case 2: cur's sibling is black and sibling's children are both black */
                 if ((( RBNode ) sibling . left ). color  ==  BLACK  &&   (( RBNode ) sibling . right ). color  ==  BLACK ){
                    sibling . color  =  RED ;  
                    cur  =  par ;
                 }
                 /* Case 3: cur's sibling is black and just sibling's right child is black */
                 else {
                     if ((( RBNode ) sibling . right ). color  ==  BLACK ){
                         (( RBNode ) sibling . left ). color  =  BLACK ;
                        sibling . color  =  RED ;   
                        rightRotate ( sibling );  
                        sibling  =   ( RBNode ) par . right ;  
                     }
                     /* Case 4: cur's sibling is black and sibling's left child is red */
                    sibling . color  =  par . color ;  
                    par . color  =  BLACK ;
                     (( RBNode ) sibling . right ). color  =  BLACK ;  
                    leftRotate ( par );
                    cur  =   ( RBNode ) root ;   
                 }
             }
             /* Meta-case 2: cur is a right child 
             * (subcases are symmetric to those of meta-case 1) */
             else {
                 RBNode < T >  sibling  =   ( RBNode ) par . left ;  
           
                 if ( sibling . color  ==  RED ){
                    sibling . color  =  BLACK ;  
                    par . color  =  RED ;  
                    rightRotate ( par );
                    sibling  =   ( RBNode ) par . left ;  
                 }
                 if ((( RBNode ) sibling . left ). color  ==  BLACK  &&   (( RBNode ) sibling . right ). color  ==  BLACK ){
                    sibling . color  =  RED ;  
                    cur  =  par ;   
                 }
                 else {
                     if ((( RBNode ) sibling . left ). color  ==  BLACK ){
                         (( RBNode ) sibling . right ). color  =  BLACK ;
                        sibling . color  =  RED ;   
                        leftRotate ( sibling );  
                        sibling  =   ( RBNode ) par . left ;  
                     }
                    sibling . color  =  par . color ;  
                    par . color  =  BLACK ;
                     (( RBNode ) sibling . left ). color  =  BLACK ;  
                    rightRotate ( par );
                    cur  =   ( RBNode ) root ;   
                 }
             }    
         }   // end while 
        cur . color  =  BLACK ;
     }
    
     /**
     * Convert a standard node into a red-black node (where the the RBnode 
     * replaces the standard node in the tree with respect to its links).
     *  @param  n : standard node to be converted.
     *  @param  c : color of the red-black node
     *  @return  converted RBNode.
     */
     private   RBNode < T >  convertToRBNode ( Node < T >  n ,   boolean  c ){
         RBNode < T >  rbN  =   new   RBNode ( n . left ,  n . right ,  n . parent ,  n . data ,  c );  
         if ( rbN . parent  ==  nullNode )
            root  =  rbN ;  
         else   if ( rbN . parent . left  ==  n )
            rbN . parent . left  =   ( Node ) rbN ;
         else
            rbN . parent . right  = ( Node ) rbN ;   
        return  rbN ;
     }
    
}

Collection/src/collection/SplayTree.java

Collection/src/collection/SplayTree.java

package  collection ;

import   static  collection . HeightBalancedTree . DELETED ;
import  java . util . ArrayList ;

/**
 * SplayTree height balancing tree class. 
 * Coding Assignment 3, CSC 330, Spring 2019
 *  @author  *YOUR NAME HERE*
 *  @param  <T> type of objects in the tree. 
 */
public   class   SplayTree < T  extends   Comparable < T >>   extends   HeightBalancedTree < T > {
    
     /* Construct an empty splay tree*/  
     public   SplayTree (){
         super ();
     }

    @ Override  
     public   void  insert ( T element ){
         /**
         * 
         * 
         *** WRITE THIS METHOD ***
         * 
         *         
         **/
     }
    
    @ Override  
     public   boolean  delete ( T element ){
         /**
         * 
         * 
         *** WRITE THIS METHOD ***
         * 
         *         
         **/
     }
    
    @ Override
     protected   void  insertionFix ( Node < T >  n ){
         /**
         * 
         * 
         *** WRITE THIS METHOD ***
         * 
         *         
         **/  
     }
    
    @ Override
     protected   void  deletionFix ( Node < T >  del ,   Node < T >  replace ,   Node < T >  parent ){
         /**
         * 
         * 
         *** WRITE THIS METHOD ***
         * 
         *         
         **/
     }
    
     /**
     * Splay a node to the root of the tree. 
     *  @param  n : node to be splayed to the top of the tree
     */
     private   void  splay ( Node < T >  n ){
         /**
         * 
         * 
         *** WRITE THIS METHOD ***
         * 
         *         
         **/
     }

}

Collection/src/collection/TestHeightBalTrees.java

Collection/src/collection/TestHeightBalTrees.java

package  collection ;

/**
 * Coding Assignment 3, CSC 330, Spring 2019
 * (Note there is nothing in this file for you to change).
 *  @author  Nathaniel Kell
 */
public   class   TestHeightBalTrees   {
    
    private   static   final   String []  INORDER  =  
     {
         "80, 90, 100" ,
         "20, 30, 35, 40, 45, 50, 60, 70, 75, 80, 90, 100" ,
         "20, 30, 35, 40, 45, 50, 60, 70, 75, 80, 85, 90, 100, 110, 120, 130, 140, 150" ,
         "1, 2, 3, 4, 5, 6, 7, 8, 9, 20, 30, 35, 40, 45, 50, 60, 70, 75, 80, 85, 90, 100, 110, 120, 130, 140, 150, 200, 210, 220, 230, 240, 250" ,       
         "2, 5, 6, 8, 9, 20, 30, 35, 70, 85, 100, 120, 130, 150, 220, 230, 240" ,     
     };
    
     private   static   final   String []  ROT_PREORDER  =  
     {
         "90, 80, 100" ,
         "75, 45, 35, 30, 20, 40, 60, 50, 70, 90, 80, 100" ,
         "75, 45, 35, 30, 20, 40, 60, 50, 70, 110, 90, 80, 85, 100, 130, 120, 140, 150" ,
         "110, 45, 20, 6, 4, 2, 1, 3, 5, 8, 7, 9, 35, 30, 40, 75, 60, 50, 70, 90, 80, 85, 100, 150, 130, 120, 140, 210, 200, 230, 220, 240, 250" ,       
         "70, 6, 2, 5, 20, 8, 9, 35, 30, 120, 85, 100, 220, 150, 130, 240, 230"  
     };
    
        
     private   static   final   String []  SPLAY_PREORDER  =  
     {
         "80, 90, 100" ,
         "20, 30, 35, 40, 45, 50, 60, 70, 75, 80, 90, 100" ,
         "85, 30, 20, 50, 40, 35, 45, 80, 70, 60, 75, 140, 120, 110, 90, 100, 130, 150" ,
         "1, 2, 3, 4, 5, 6, 7, 8, 9, 250, 230, 210, 85, 20, 30, 50, 40, 35, 45, 80, 70, 60, 75, 200, 150, 140, 120, 110, 90, 100, 130, 220, 240" ,       
         "120, 9, 5, 2, 8, 6, 70, 30, 20, 35, 85, 100, 150, 130, 230, 220, 240" ,     
     };
    
     public   static   int  doTests ( HeightBalancedTree < Integer >  tree ,   String []  inorderStrings ,   String []  preOrderStrings ){
         int []  totalCorrect   =   { 0 };  
         int  testNumber  =   1 ;  
       
         /* Test 1 */
        testOne ( tree );
        printTestMessage ( tree ,  testNumber ,  totalCorrect ,  inorderStrings ,  preOrderStrings );
        testNumber ++ ;
    
         /* Test 2 */
        testTwo ( tree );
        printTestMessage ( tree ,  testNumber ,  totalCorrect ,  inorderStrings ,  preOrderStrings );
        testNumber ++ ;
        
         /* Test 3 */
        testThree ( tree );
        printTestMessage ( tree ,  testNumber ,  totalCorrect ,  inorderStrings ,  preOrderStrings );
        testNumber ++ ;
       
         /* Test 4 */
        testFour ( tree );
        printTestMessage ( tree ,  testNumber ,  totalCorrect ,  inorderStrings ,  preOrderStrings );
        testNumber ++ ;
 
         /* Test 5 */
        testFive ( tree );
        printTestMessage ( tree ,  testNumber ,  totalCorrect ,  inorderStrings ,  preOrderStrings );

         return  totalCorrect [ 0 ];
     }
    
    
     /* Modify the tree for test 1 */
     public   static   void  testOne ( HeightBalancedTree < Integer >  tree ){
        tree . insert ( 100 );
        tree . insert ( 90 );
        tree . insert ( 80 );
     }
    
     /* Modify the tree for test 2 */
     public   static   void  testTwo ( HeightBalancedTree < Integer >  tree ){
        tree . insert ( 70 );
        tree . insert ( 75 );
        tree . insert ( 60 );
        tree . insert ( 50 );
        tree . insert ( 45 );
        tree . insert ( 40 );
        tree . insert ( 30 );
        tree . insert ( 35 );
        tree . insert ( 20 );
     }
    
     /* Modify the tree for test 3 */
     public   static   void  testThree ( HeightBalancedTree < Integer >  tree ){
        tree . insert ( 110 );
        tree . insert ( 120 );
        tree . insert ( 130 );
        tree . insert ( 140 );
        tree . insert ( 150 );
        tree . insert ( 85 );
     }
   
     /* Modify the tree for test 4 */
     public   static   void  testFour ( HeightBalancedTree < Integer >  tree ){
        tree . insert ( 200 );
        tree . insert ( 210 );
        tree . insert ( 220 );
        tree . insert ( 230 );
        tree . insert ( 240 );
        tree . insert ( 250 );
        tree . insert ( 9 );
        tree . insert ( 8 );
        tree . insert ( 7 );
        tree . insert ( 6 );
        tree . insert ( 5 );
        tree . insert ( 4 );
        tree . insert ( 3 );
        tree . insert ( 2 );
        tree . insert ( 1 );
     }
    
     /* Modify the tree for test 5 */
     public   static   void  testFive ( HeightBalancedTree < Integer >  tree ){
        tree . delete ( 80 );
        tree . delete ( 110 );
        tree . delete ( 60 );
        tree . delete ( 40 );
        tree . delete ( 90 );
        tree . delete ( 140 );
        tree . delete ( 75 );
        tree . delete ( 45 );
        tree . delete ( 200 );
        tree . delete ( 210 );
        tree . delete ( 250 );
        tree . delete ( 7 );
        tree . delete ( 4 );
        tree . delete ( 3 );
        tree . delete ( 1 );
        tree . delete ( 50 );
     }
    
     /* Print test results of a test */
     public   static   void  printTestMessage ( HeightBalancedTree < Integer >  tree ,  
             int  tNum ,   int []  totalCorrect ,   String []  inOrderTests ,   String []  preOrderTests ){
         System . out . printf ( "Test Number: %d\n" ,  tNum );
         System . out . printf ( "Target in-order sequence: %s\n"
                 +   "Produced in-order sequence: %s\n"
                 +   "Target pre-order sequence: %s\n"
                 +   "Produced pre-order sequence: %s\n" ,
                inOrderTests [ tNum - 1 ],  tree . inOrderString (),  preOrderTests [ tNum - 1 ],  tree . toString ());
         if ( inOrderTests [ tNum - 1 ]. equals ( tree . inOrderString ())   &&  preOrderTests [ tNum - 1 ]. equals ( tree . toString ())){
             System . out . println ( "*** CORRECT ***\n" );
            totalCorrect [ 0 ] ++ ;  
         }
         else
               System . out . println ( "*** INCORRECT ***\n" );
     }

     /**
     *  @param  args the command line arguments
     */
     public   static   void  main ( String []  args )   {
        
         /* Rotation tests.*/
         System . out . println ( "\n**** ROTATION TESTS *****" );
         RedBlackTree < Integer >  tree  =   new   RedBlackTree ();  
         int  totalRotCorrect  =  doTests ( tree ,  INORDER ,  ROT_PREORDER );
         System . out . printf ( "Total Rotation Tests Correct: %d\n" ,  totalRotCorrect );
        
         /* SplayTreee tests */
         System . out . println ( "\n-\n\n**** SPLAY TREE TESTS *****" );
         SplayTree < Integer >  sTree  =   new   SplayTree ();  
         int  totalSplayCorrect  =  doTests ( sTree ,  INORDER ,   SPLAY_PREORDER );
         System . out . printf ( "Total Splay Tree TayTrests Correct: %d\n" ,  totalSplayCorrect );
        
        /* Total correct.*/
        System . out . printf ( "\nTotal Overall Correct: %d\n" ,  totalRotCorrect  +  totalSplayCorrect );  
        
     }
    
}