Java Code must be written as stated in the Instructions. The task of this project is to

 

Java Code must be written as stated in the Instructions.
 

Transcribed Image Text:

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 the BST. Specification The project must implement the following specification 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 may find it necessary to do so! Structure LazyBinarySearchTree |-root : TreeNode +insert(key: int): boolean (throws IllegalArgumentException} +delete(key: int): boolean {throws IllegalArgumentException} +findMin(): int +findMax(): int +contains(key: int): boolean {throws IllegalArgumentException} +toString(): String +height(): int +size(): int TreeNode key: int leftChild: TreeNode rightChild: TreeNode deleted: boolean 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 duplicate 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 indicate 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. 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 the BST. Specification The project must implement the following specification 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 may find it necessary to do so! Structure LazyBinarySearchTree |-root : TreeNode +insert(key: int): boolean (throws IllegalArgumentException} +delete(key: int): boolean {throws IllegalArgumentException} +findMin(): int +findMax(): int +contains(key: int): boolean {throws IllegalArgumentException} +toString(): String +height(): int +size(): int TreeNode key: int leftChild: TreeNode rightChild: TreeNode deleted: boolean 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 duplicate 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 indicate 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.

Answer rating: 100% (QA)

LazyBinarySearchTreejava This class represents a binary search tree public class LazyBinarySearchTree private static final int MINKEY 1 private static final int MAXKEY 99 Inner class private class Tre... View the full answer