Lab 3.2B Java

profilehjfnmb12345
Lab3.2B.zip
Home>Computer Science homework help>Lab 3.2B Java

Lab 3.2B/~$enario.docx

Lab 3.2B/Provided Code/BinaryTree (1).java

Lab 3.2B/Provided Code/BinaryTree (1).java

import  java . util . Optional ;

public   interface   BinaryTree < K , V >   {
     void  put ( K key , V value );

     Optional < V >  get ( K key );
}

Lab 3.2B/Provided Code/BinaryTreeNode.java

Lab 3.2B/Provided Code/BinaryTreeNode.java

import  java . util . Optional ;

public   class   BinaryTreeNode < K , V >   {
     private   BinaryTreeNode < K , V >  left ;
     private   BinaryTreeNode < K , V >  right ;
     private  K key ;
     private  V value ;

     public   BinaryTreeNode ( K key ,  V value )   {
         this . key  =  key ;
         this . value  =  value ;
     }

     public   Optional < BinaryTreeNode < K , V >>  getLeft ()   {
         return   Optional . ofNullable ( left );
     }

     public   Optional < BinaryTreeNode < K , V >>  getRight ()   {
         return   Optional . ofNullable ( right );
     }

     public   void  setLeft ( BinaryTreeNode < K , V >  left )   {
         this . left  =  left ;
     }

     public   void  setRight ( BinaryTreeNode < K , V >  right )   {
         this . right  =  right ;
     }

     public  K getKey ()   {
         return  key ;
     }

     public   void  setKey ( K key )   {
         this . key  =  key ;
     }

     public  V getValue ()   {
         return  value ;
     }

     public   void  setValue ( V value )   {
         this . value  =  value ;
     }
}

Lab 3.2B/Provided Code/InOrderSuccessorBinaryTree.java

Lab 3.2B/Provided Code/InOrderSuccessorBinaryTree.java

import  java . until . Optional ;

public   class   InOrderSuccessorBinaryTree < K ,  V >   extends   SimpleBinaryTree < K ,  V >  
{
     public   Optional < K >  inOrderSuccessorKey ( K key )
      {
         Optional < BinaryTreeNode < K ,  V >>  node  =   Optional . ofNullable ( root );
         Optional < K >  successor  =   Optional . empty ();
             while   ( node . isPresent ()   &&   ! node . get (). getKey (). equals ( key ))   {
                 if   ((( Comparable )  node . get (). getKey ()). compareTo ( key )   >   0 )   {
                    successor  =  node . map ( BinaryTreeNode :: getKey );
                    node  =  node . flatMap ( BinaryTreeNode :: getLeft );
}    
                 else
                node  =  node . flatMap ( BinaryTreeNode :: getRight );
}

return  node . flatMap ( BinaryTreeNode :: getRight ). map ( this :: minKey )
. map ( Optional :: of ). orElse ( successor );
}

Lab 3.2B/Provided Code/SimpleBinaryTree.java

Lab 3.2B/Provided Code/SimpleBinaryTree.java

import  java . util . LinkedList ;
import  java . util . Optional ;
import  java . util . Queue ;

public   class   SimpleBinaryTree < K ,  V >   implements   BinaryTree < K ,  V >   {
     protected   BinaryTreeNode < K ,  V >  root ;

     public   void  put ( K key ,  V value )   {
         if   ( root  ==   null )
            root  =   new   BinaryTreeNode <> ( key ,  value );
         else
            put ( key ,  value ,  root );
     }

     private   void  put ( K key ,  V value ,   BinaryTreeNode < K ,  V >  node )   {
         if   ((( Comparable )  key ). compareTo ( node . getKey ())   ==   0 )   {
            node . setKey ( key );
            node . setValue ( value );
         }   else   if   ((( Comparable )  key ). compareTo ( node . getKey ())   <   0 )   {
             if   ( node . getLeft (). isPresent ())
                put ( key ,  value ,  node . getLeft (). get ());
             else
                node . setLeft ( new   BinaryTreeNode <> ( key ,  value ));
         }   else   {
             if   ( node . getRight (). isPresent ())
                put ( key ,  value ,  node . getRight (). get ());
             else
                node . setRight ( new   BinaryTreeNode <> ( key ,  value ));
         }
     }

     public   Optional < V >  get ( K key )   {
         return   Optional . ofNullable ( root ). flatMap ( n  ->  get ( key ,  n ));
     }

     private   Optional < V >  get ( K key ,   BinaryTreeNode < K ,  V >  node )   {
         if   ((( Comparable )  key ). compareTo ( node . getKey ())   ==   0 )
             return   Optional . of ( node . getValue ());
         else   if   ((( Comparable )  key ). compareTo ( node . getKey ())   <   0 )
             return  node . getLeft (). flatMap ( n  ->  get ( key ,  n ));
         else
             return  node . getRight (). flatMap ( n  ->  get ( key ,  n ));
     }

     public   void  leftRotate ( BinaryTreeNode < K ,  V >  nodeX ,
                            BinaryTreeNode < K ,  V >  parent )   {
         BinaryTreeNode < K ,  V >  nodeY  =  nodeX . getRight (). get ();
        nodeX . setRight ( nodeY . getLeft (). orElse ( null ));
         if   ( parent  ==   null )
             this . root  =  nodeY ;
         else   if   ( parent . getLeft (). filter ( n  ->  n  ==  nodeX ). isPresent ())
            parent . setLeft ( nodeY );
         else
            parent . setRight ( nodeY );
        nodeY . setLeft ( nodeX );
     }

     public   void  rightRotate ( BinaryTreeNode < K ,  V >  nodeX ,
                            BinaryTreeNode < K ,  V >  parent )   {
         BinaryTreeNode < K ,  V >  nodeY  =  nodeX . getLeft (). get ();
        nodeX . setLeft ( nodeY . getRight (). orElse ( null ));
         if   ( parent  ==   null )
             this . root  =  nodeY ;
         else   if   ( parent . getRight (). filter ( n  ->  n  ==  nodeX ). isPresent ())
            parent . setRight ( nodeY );
         else
            parent . setLeft ( nodeY );
        nodeY . setRight ( nodeX );
     }


     public   Optional < K >  minKey ()   {
         return   Optional . ofNullable ( root ). map ( this :: minKey );
     }

     protected  K minKey ( BinaryTreeNode < K ,  V >  node )   {
         return  node . getLeft (). map ( this :: minKey ). orElse ( node . getKey ());
     }

     public   void  printBfs ()   {
         Optional . ofNullable ( root ). ifPresent ( r  ->   {
             Queue < BinaryTreeNode < K ,  V >>  queue  =   new   LinkedList <> ();
            queue . add ( r );
             while   ( ! queue . isEmpty ())   {
                 BinaryTreeNode < K ,  V >  node  =  queue . remove ();
                 System . out . println ( node . getKey ());
                node . getLeft (). ifPresent ( queue :: add );
                node . getRight (). ifPresent ( queue :: add );
             }
         });
     }


     public   void  printDfs ()   {
         Optional . ofNullable ( root ). ifPresent ( this :: printDfs );
     }

     private   void  printDfs ( BinaryTreeNode < K ,  V >  node )   {
         //System.out.println("PREORDER " + node.getKey());
        node . getLeft (). ifPresent ( this :: printDfs );
         System . out . println ( "INORDER "   +  node . getKey ());
        node . getRight (). ifPresent ( this :: printDfs );
         //System.out.println("POSTORDER " + node.getKey());
     }

     public   static   void  main ( String []  args )   {
         /*   
        * This main method is a stub.
        * It does nothing.
        * Feel free to write your own code to test your implementation.
        * In this case, we have nothing actionable in here, just this comment block, so the JVM should rapidly lose interest and move on to the rest of your code.
        */
     }
}

Lab 3.2B/Scenario.docx

Scenario

We need to write a method that, given a key as an argument, returns the next in order key found in the binary search tree. If the key given as an argument is not found, the method should still return the next in order key. If the binary tree is empty or all the stored keys are smaller than the argument, then the return value should be empty.

For example, using a collection of {10,13,52,67,68,83} stored in the binary search tree:

· An input of 13 results in 52

· An input of 67 results in 68

· An input of 55 results in 67

· An input of 5 results in 10

· An input of 83 results in Optional.empty

· An input of 100 results in Optional.empty

· Any input on an empty binary tree results in Optional.empty

Both the in order successor and predecessor algorithms have many applications. As an example, think about if you had to keep a scoreboard at some sports event where you only want to show the first three runners. If you keep your data in a binary search tree, you can find the maximum key and then work out the next two predecessor nodes.

The solution needs to have a runtime complexity of O(log n).

Aim

Retrieve the successor of an element when the tree is traversed in inorder.

Prerequisites

1. Implement the following method, provided in the InOrderSuccessorBinaryTree class that extends the SimpleBinaryTree class.

public Optional<K> inOrderSuccessorKey(K key)

Steps for Completion

1. Use a non-recursive search operation first to find the first node with a key equal to or less than the input.

2. Realize that the inorder successor can be in only one of two places, either as a parent of this node or the minimum key on the subtree of the right child of this node (if any).

Grading

Complete each task listed below. Each task contains automated checks which are used to calculate your grade. When you have completed each task by clicking the checkbox, open the task list panel on the left navigation bar and click the "Submit" button.

Task

0.00

out of

10.00

Use a non-recursive search operation to retrieve the successor element when traversing a tree inorder.

7

0 out of 7 checks passed. Review the results below for more details.

Checks

Unit TestIncomplete

Program handles getting the successor of a node in an empty tree

Unit TestIncomplete

Program handles getting the successor from an unset node

Unit TestIncomplete

Program handles getting the successor of a tree containing only the root element

Unit TestIncomplete

Program gets the Successor of a lower key value than root

Unit TestIncomplete

Program handles getting the successor of the max key value

Unit TestIncomplete

Program handles getting the successor for subtree

Unit TestIncomplete

Programs handles subtree getting successor in parent tree