Java coding progam

BINARY SEARCH TREES WITH LAZY DELETION

The task of this project is to implement in Java a binary search tree with lazy deletion. The BST class should contain a nested tree node class that is used to implement BST.

Specification

The project must implement the follwoing EXACTLY, which includes identifier names, method signatures, the presence or absence of exceptional behavior, etc. Anything not clearly indicated by the UML class diagram (such as the access level of TreeNode fields, note the TreeNode class itself is private nested inside LazyBinarySearchTree class) or explicitly stated in the natural language description is left up to your discretion. You may also add helper methods and additional fields as you see fit - in fact, you man find it necessary to do so!

Note that the (+) relation in UML denotes nesting of scope, and not just composition of use.

Behavior

insert - should insert a new element to a leaf node. The valid set of keys is all integers in the range[1,99]. If the new element would be a duplicate of a non-deleted element already in the tree, then insert should do nothing. However, if the new element is not a duplicate of a non-deleted element, but is a duplicated of a deleted element, then insert should "undelete" the deleted element in-place rather than physically inserting a new copy of the element. The return value of insert should indicated whether insert logically ( as opposed to physically) inserted a new element.

delete - should not physically remove an element from the tree. Rather, it should mark the specified element as logically deleted. If the specified element is not in the tree or is already marked as deleted, then delete should do nothing. The return value of delete should indicate whether delete logically deleted an element.

findMin should return the value of the minimum non-deleted element, or -1 if none exists.

findMax should return the value of the maximum non-deleted element, or -1 if none exists.

toString should perform an pre-order traversal of the tree and print the value of each element, including elements marked as deleted. However, elements that are marked as deleted should be preceded by a single asterisk. Every pair of adjacent elements should be separated by whitespace in the printing. but no whitespace should occur between an asterisk and the element with which it is associated. Leading and trailing whitespace is tolerable, but it will be ignored. ( no additional messages should be printed, either) An example of the output is as follows:

45 30 2 *5 47 50 *60

height should return the height of the tree, including deleted elements.

size should return the count of elements in the tree, including deleted ones.

The vaild set of keys is all integers in the range [1,99]. Every method that accepts a key argument should through an IllegalArgumentException with an appropriate message if the argument is invalid. No method specified herein should (intentionally) throw any other exception.

Do not define any package( for this project, anyway). I.e you should use the default package.

Along with the LazyBinarySearchTree class include another class that has a main function. You can name this class anything just clearly indicate the name in Readme File. This class will take two command line arguments. The first argument will be the input file name and second will be output file name. The input file will be given to the program and the output file will be generated by the program. This main class will create an instance of LazyBinarySearchTree and do the operations specified in the input file.

The format of the input file will be

Insert:98

Insert:67

Insert:55

Insert:45

PrintTree

Delete:84

Delete:45

Contains:45

FindMin

FindMax

PrintTree

Height

Size

Insert:84

Insert:32

Insert:132

PrintTree

Insert:980

Insert

hih

{Insert and Delete will be followed by : semicolon and the key to be inserted. You have to check for validity of the key as well as the line in the file.PrintTree corresponds to toString method in the class.}

The corresponding correct output file will be

True

True

True

True

98 67 55 45

False

True

False

55

98

98 67 55 *45

3

4

True

True

Error in insert:IllegalArgumentException raised

98 67 55 *45 32 84

Error in insert:IllegalArgumentException raised

Error in Line: Insert

Error in Line: hih

Structure LazyBinarySearchTree -root: TreeNode TreeNode +insert(key: int): boolean fthrows IllegalArgumentExceptionj +delete(key: int): boolean (throws IlegalArgumentException] +findMinO: int +findMax0: int +contains(key: int): boolean (throws IllegalArgumentException +toString0: String +height0: int +size0: int key: int leftChild: TreeNode rightChild: TreeNode deleted: boolean