Java- Data Structures and Analysis- Balancing Binary Search Trees

profilebrinco
word_doc_and_.java_.zip
Home>Computer Science homework help>Java- Data Structures and Analysis- Balancing Binary Search Trees

Word doc and .java/BST.java

Word doc and .java/BST.java


// Liang - Introduction to Java Programming, 9th Edition (Code Examples of Chapter 27 Binary Search Trees)
// Source code of the examples available at: 
// http://www.cs.armstrong.edu/liang/intro9e/examplesource.html

public   class  BST < E  extends   Comparable < E >>   {
    
   protected   TreeNode < E >  root ;
   protected   int  size  =   0 ;

   /** Create a default binary tree */
   public  BST ()   {
   }

   /** Create a binary tree from an array of objects */
   public  BST ( E []  objects )   {
     for   ( int  i  =   0 ;  i  <  objects . length ;  i ++ )
      insert ( objects [ i ]);
   }

   /** Returns true if the element is in the tree */
   public   boolean  search ( E e )   {
     TreeNode < E >  current  =  root ;   // Start from the root

     while   ( current  !=   null )   {
       if   ( e . compareTo ( current . element )   <   0 )   {
        current  =  current . left ;
       }
       else   if   ( e . compareTo ( current . element )   >   0 )   {
        current  =  current . right ;
       }
       else   // element matches current.element
         return   true ;   // Element is found
     }

     return   false ;
   }

   /** Insert element o into the binary tree
   * Return true if the element is inserted successfully */
   public   boolean  insert ( E e )   {
     if   ( root  ==   null )
      root  =  createNewNode ( e );   // Create a new root
     else   {
       // Locate the parent node
       TreeNode < E >  parent  =   null ;
       TreeNode < E >  current  =  root ;
       while   ( current  !=   null )
         if   ( e . compareTo ( current . element )   <   0 )   {
          parent  =  current ;
          current  =  current . left ;
         }
         else   if   ( e . compareTo ( current . element )   >   0 )   {
          parent  =  current ;
          current  =  current . right ;
         }
         else
           return   false ;   // Duplicate node not inserted

       // Create the new node and attach it to the parent node
       if   ( e . compareTo ( parent . element )   <   0 )
        parent . left  =  createNewNode ( e );
       else
        parent . right  =  createNewNode ( e );
     }

    size ++ ;
     return   true ;   // Element inserted
   }

   protected   TreeNode < E >  createNewNode ( E e )   {
     return   new   TreeNode < E > ( e );
   }

   /** Inorder traversal from the root*/
   public   void  inorder ()   {
    inorder ( root );
   }

   /** Inorder traversal from a subtree */
   protected   void  inorder ( TreeNode < E >  root )   {
     if   ( root  ==   null )   return ;
    inorder ( root . left );
     System . out . print ( root . element  +   " " );
    inorder ( root . right );
   }

   /** Postorder traversal from the root */
   public   void  postorder ()   {
    postorder ( root );
   }

   /** Postorder traversal from a subtree */
   protected   void  postorder ( TreeNode < E >  root )   {
     if   ( root  ==   null )   return ;
    postorder ( root . left );
    postorder ( root . right );
     System . out . print ( root . element  +   " " );
   }

   /** Preorder traversal from the root */
   public   void  preorder ()   {
    preorder ( root );
   }

   /** Preorder traversal from a subtree */
   protected   void  preorder ( TreeNode < E >  root )   {
     if   ( root  ==   null )   return ;
     System . out . print ( root . element  +   " " );
    preorder ( root . left );
    preorder ( root . right );
   }

   /** This inner class is static, because it does not access 
      any instance members defined in its outer class */
   public   static   class   TreeNode < E  extends   Comparable < E >>   {
     protected  E element ;
     protected   TreeNode < E >  left ;
     protected   TreeNode < E >  right ;

     public   TreeNode ( E e )   {
      element  =  e ;
     }
   }

   /** Get the number of nodes in the tree */
   public   int  getSize ()   {
     return  size ;
   }

   /** Returns the root of the tree */
   public   TreeNode < E >  getRoot ()   {
     return  root ;
   }

   /** Returns a path from the root leading to the specified element */
   public  java . util . ArrayList < TreeNode < E >>  path ( E e )   {
    java . util . ArrayList < TreeNode < E >>  list  =
       new  java . util . ArrayList < TreeNode < E >> ();
     TreeNode < E >  current  =  root ;   // Start from the root

     while   ( current  !=   null )   {
      list . add ( current );   // Add the node to the list
       if   ( e . compareTo ( current . element )   <   0 )   {
        current  =  current . left ;
       }
       else   if   ( e . compareTo ( current . element )   >   0 )   {
        current  =  current . right ;
       }
       else
         break ;
     }

     return  list ;   // Return an array of nodes
   }

   /** Delete an element from the binary tree.
   * Return true if the element is deleted successfully
   * Return false if the element is not in the tree */
   public   boolean  delete ( E e )   {
     // Locate the node to be deleted and also locate its parent node
     TreeNode < E >  parent  =   null ;
     TreeNode < E >  current  =  root ;
     while   ( current  !=   null )   {
       if   ( e . compareTo ( current . element )   <   0 )   {
        parent  =  current ;
        current  =  current . left ;
       }
       else   if   ( e . compareTo ( current . element )   >   0 )   {
        parent  =  current ;
        current  =  current . right ;
       }
       else
         break ;   // Element is in the tree pointed at by current
     }

     if   ( current  ==   null )
       return   false ;   // Element is not in the tree

     // Case 1: current has no left children
     if   ( current . left  ==   null )   {
       // Connect the parent with the right child of the current node
       if   ( parent  ==   null )   {
        root  =  current . right ;
       }
       else   {
         if   ( e . compareTo ( parent . element )   <   0 )
          parent . left  =  current . right ;
         else
          parent . right  =  current . right ;
       }
     }
     else   {
       // Case 2: The current node has a left child
       // Locate the rightmost node in the left subtree of
       // the current node and also its parent
       TreeNode < E >  parentOfRightMost  =  current ;
       TreeNode < E >  rightMost  =  current . left ;

       while   ( rightMost . right  !=   null )   {
        parentOfRightMost  =  rightMost ;
        rightMost  =  rightMost . right ;   // Keep going to the right
       }

       // Replace the element in current by the element in rightMost
      current . element  =  rightMost . element ;

       // Eliminate rightmost node
       if   ( parentOfRightMost . right  ==  rightMost )
        parentOfRightMost . right  =  rightMost . left ;
       else
         // Special case: parentOfRightMost == current
        parentOfRightMost . left  =  rightMost . left ;      
     }

    size -- ;
     return   true ;   // Element inserted
   }

   /** Obtain an iterator. Use inorder. */
   public  java . util . Iterator < E >  iterator ()   {
     return   new   InorderIterator ();
   }

   // Inner class InorderIterator
   private   class   InorderIterator   implements  java . util . Iterator < E >   {
     // Store the elements in a list
     private  java . util . ArrayList < E >  list  =
       new  java . util . ArrayList < E > ();
     private   int  current  =   0 ;   // Point to the current element in list

     public   InorderIterator ()   {
      inorder ();   // Traverse binary tree and store elements in list
     }

     /** Inorder traversal from the root*/
     private   void  inorder ()   {
      inorder ( root );
     }

     /** Inorder traversal from a subtree */
     private   void  inorder ( TreeNode < E >  root )   {
       if   ( root  ==   null ) return ;
      inorder ( root . left );
      list . add ( root . element );
      inorder ( root . right );
     }

     /** More elements for traversing? */
     public   boolean  hasNext ()   {
       if   ( current  <  list . size ())
         return   true ;

       return   false ;
     }

     /** Get the current element and move to the next */
     public  E next ()   {
       return  list . get ( current ++ );
     }

     /** Remove the current element */
     public   void  remove ()   {
      delete ( list . get ( current ));   // Delete the current element
      list . clear ();   // Clear the list
      inorder ();   // Rebuild the list
     }
   }

   /** Remove all elements from the tree */
   public   void  clear ()   {
    root  =   null ;
    size  =   0 ;
   }
}

Word doc and .java/homework 9JUN2016.docx

Balancing Binary Search Trees

1. Specification

The search effort for locating a node in a Binary Search Tree (BST) depends on the tree shape (topology). For a BST

with n nodes the ACE value is defined (Wiener and Pinson) as the Average Comparison Effort for locating a node in a tree

by summing all comparison operations for all tree nodes and dividing the result by the total number of tree nodes:

for (int level = 0, sum = 0; level < treeHeight; level++ ) {

sum += numberOfNodesAtLevel(level) * (level + 1)

}

ACE = sum / n

When the average comparison effort (i.e. the ACE value) gets over a certain threshold or after a certain number of tree

insert/delete operations, for optimizing the search process, a tree balance operation should be executed resulting a tree

whose height equals |_ log n _| + 1 (or floor(log n) + 1), thus requiring at most |_ log n _| + 1 (or floor(log n) + 1)

comparison operations to identify any tree node.

For a given BST with n nodes we define MinACE as the minimum value of ACE and MaxACE as the maximum value of

ACE. MinACE value for a BST with n nodes, corresponds to the ACE value calculated for a BST of height floor(log n) + 1

which has all levels completely full, except for the last level. The ACE value of a balanced BST equals MinACE. MaxACE

value for a BST with n nodes corresponds to the ACE value calculated for a BST which degenerates into a linear linked list

with n nodes.

Part 1

Consider the attached file BST.java which defines a generic BST class.

Enhance the BST class with the following methods:

· treeHeight, calculates tree height;

· nodeBalanceLevel calculates the balance level of a user specified node as the difference between the height of its left subtree and the height of its right subtree;

· numberOfNodesAtLevel calculates the number of nodes at the specified level;

· calculateACE, calculates the ACE value according to the above algorithm;

· calculateMinACE, calculates the minimum value of the ACE;

· calculateMaxACE, calculates the maximum value of the ACE;

· needsBalancing, evaluates whether this BST needs to be balanced or not. We consider that a BST needs to be balanced when its ACE value is greater than K * MinACE where K = 1.28;

· doBalanceBST, executes the balance operation on this BST;

Additional methods may be added if necessary.

The enhanced BST class should compile without errors.

Part 2

Design and implement a driver program TestBST for testing the methods implemented in Part 1. The driver program

should build an initial BST whose nodes contain positive integer values taken from an input file. In the input file, the

values should be separated by the semicolon character. After building the BST, in a loop, the program should invite the

user to select for execution one of the following operations: (1) in-order tree traversal, (2) pre-order tree traversal, (3)

calculateACE, (4) calculateMinACE, (5) calculateMaxACE, (6) numberOfNodesAtLevel, (7) treeHeight, (8)

nodeBalanceLevel (9) needsBalancing, (10) doBalanceBST, (11) insert value, and (0) exit the loop and the program.

As a result of each operation execution, relevant information will be displayed to the user. For example, as a result of

executing the in-order traversal, the values of the tree nodes should be shown to the console or, as a result of executing

the calculateACE operation, the ACE value should be displayed to the console.

Notes.

1. If an operation requires additional information, the user will be prompted to enter it.

2. The input file (a simple .txt file) should be generated by the students using a simple text editor such as Notepad.

3. You may assume that there are no errors in the input file structure.

4. Tree root is considered as located at level 0. Tree height will be calculated by counting the nodes, starting with the

root, along the longest path.

2. Submission requirements

Submit the following before the due date listed in the Calendar:

1. All .java source files and the input file. The source code should use Java code conventions and appropriate code layout

(white space management and indents) and comments.

2. The solution description document <YourSecondName>_P2 (.pdf or .doc / .docx) containing:

(2.1) assumptions, main design decisions, error handling; (2.2) test cases and two relevant screenshots; (2.3) lessons

learned and (2.4) possible improvements. The size of the document file (including the screenshots) should be of 3 pages,

single spaced, font size 10

Grading requirements:

Design (20 points):

Employs Modularity (including proper use of parameters, use of local variables etc.) most of the time

Employs correct & appropriate use of programming structures (loops, conditionals, classes etc.) most of the time

Efficient algorithms used most of the time

Excellent use of object-oriented design

Functionality (20 points):

Program fulfills all functionality

All requirements were fulfilled

Extra effort was apparent

Test Plan (20 points):

Comprehensive test plan.

Documentation (20 points):

Excellent comments

Comprehensive lessons learned

Excellent possible improvements included

Excellent approach discussion and references