// File: LazyBST.java

// Author: Rita Ester

// Date: March, 2018

// Description: BinarySearchTree class

//

class BSTNode {

//public member attributes

// direct access for simplicity

public int data;

public boolean removed; // true if data has been marked as removed: "the tombstone".

public BSTNode left, right;

// Default/leaf node constructor

public BSTNode(int value)

{

data = value;

removed = false;

left = null;

right = null;

}

}

public class LazyBST {

private BSTNode root;

private int size; // number of items not removed in the tree

private int nb_removedItems; // number of items marked as removed in the tree.

// default constructor

public LazyBST()

{

root = null;

size = 0;

nb_removedItems = 0;

}

// returns the number of items stored in the tree

public int size()

{

return size;

}

// returns the height of the tree

// an empty tree has height -1

// a tree of only the root has height 0

public int height()

{

return calculateHeight(root);

}

// Recursively computes the height of a subtree rooted at nd

// the height of an empty tree is -1.

private int calculateHeight(BSTNode nd)

{

// to be completed

return -1;

}

// Returns true if the search item is in the tree, false otherwise

// May be implemented iteratively in this function, or recursively

// using the private helper method below

public boolean contains(int item)

{

// to be completed

// contains(root, item); // calling the recursive contains method or

// or implement the iterative version here

return true;

}

// recursive contains method

private boolean contains(BSTNode nd, int item)

{

// to be completed

return true;

}

// Insert function

// Inserts a new leaf node while maintaining BST properties

// May be completed iteratively in this method,

// or recursively using a private method.

// do not insert duplicate key values.

public void insert(int item)

{

// to be completed

// insert(root, item); // calling the recursive insert method or

// or implementing the iterative version here

}

// recursive insert method

private void insert(BSTNode nd, int item)

{

// to be completed, if recursive solution is chosen

}

// rebuilds the tree with nodes marked as removed

// into a new tree, containing only the not removed nodes.

public void rebuild(){

if (size > 0)

{

LazyBST newTree = new LazyBST(); // used to build a the new tree

rebuild(newTree, root);

root = newTree.root;

nb_removedItems = 0;

}

else // size == 0

{

root = null;

size = 0;

nb_removedItems = 0;

}

}

// rebuilds the tree into a new tree,

// containing only the not removed nodes.

private void rebuild(LazyBST newTree, BSTNode nd){

// to be completed

}

// returns the value of the smallest key in the tree

// Throws IllegalStateException if tree is empty

public int findMin() throws IllegalStateException

{

if (size

throw new IllegalStateException("FindMin: tree is empty");

else

{

BSTNode minNd = findMin(root);

return minNd.data;

}

}

//returns a reference to the node with the smallest key in the tree

private BSTNode findMin(BSTNode nd){

// to be completed

return nd;

}

// returns false if item is not in the tree

// returns true if item can be found and is marked as removed

public boolean remove(int item)

{

// to be completed

return true;

}

public void inorderPrint(){

inOrderPrint(root);

}

// prints out the data of the tree at nd in inorder sequence,

// removed data will also be printed and marked with an "x".

private void inOrderPrint(BSTNode nd){

// to be completed

}

// Initial call to print the contents/structure of the tree.

public void printTree(){

printRecTree(root,0);

}

// recursively prints the contents/structure of the tree,

// rotated counter-clockwise 90 degrees.

// Use a modified in-order traversal.

// parameter level: the number of tab characters to insert

// example output: for a tree with root 12, left child 5, right child 17, removed

// print the following tree structure:

// 17x

// 12

// 5

//removed data will also be printed and marked with an "x".

private void printRecTree(BSTNode nd, int level){

// to be completed

}

}

// File: Ass4Driver.java

// Author: Rita Ester

// Date: March, 2018

// Description: Driver file for CSCI 225 Assignment 4

import java.util.Random;

public class Ass4Driver{

static Random rnd = new Random();

static final int maxvalue = 100; // the largest integer that can be randomly generated.

static final int numitems = 9; // number of items to insert, can be changed

static final int numitemstoremove = 5;

static int[] contents = new int[numitems];

public static void main(String[] args)

{

rnd.setSeed(System.currentTimeMillis());

BSTTest0();

//BSTTest1();

//BSTTest2();

//BSTTest3();

//BSTTest4();

//BSTTest5();

//BSTTest6();

//BSTTest7();

//BSTTest8();

//BSTTest9();

}

private static void printStats(LazyBST tree){

System.out.println("Printing tree...");

tree.printTree();

System.out.print("Tree height: " + tree.height() + ", Tree size: " + tree.size());

System.out.print(" In-order contents: ");

tree.inorderPrint();

}

public static void BSTTest0()

{

LazyBST treeA = new LazyBST();

System.out.println("New BST created.");

// insert random-valued nodes into tree

int item;

for (int i = 0; i

{

item = rnd.nextInt(maxvalue);

System.out.println("inserting: "+ item + "...");

treeA.insert(item);

contents[i] = item;

}

System.out.println(numitems + " random items inserted. ");

printStats (treeA);

System.out.println(" Removing items...");

for (int i = 0; i

{

int index = rnd.nextInt(numitems-1);

item = contents[index];

System.out.println("Removing " + item + "...");

treeA.remove(item);

}

printStats (treeA);

System.out.println(" Find minimum: " + treeA.findMin());

System.out.println(" Rebuild tree...");

treeA.rebuild();

printStats (treeA);

}

public static void BSTTest1()

// removing the key from a single node tree.

{

LazyBST treeA = new LazyBST();

System.out.println(" ******Test 1: removing the key from a single node tree");

// insert nodes into tree

int[] keys ={13};

for (int i = 0; i

{

treeA.insert(keys[i]);

}

System.out.print(keys.length + " keys inserted. ");

printStats (treeA);

System.out.println(" Removing key 13...");

treeA.remove(13);

printStats (treeA);

}

public static void BSTTest2()

// removing a leaf from a tree.

{

LazyBST treeA = new LazyBST();

System.out.println(" ******Test 2: removing a leaf from a tree.");

// insert nodes into tree

int[] keys ={13, 3, 23};

for (int i = 0; i

{

treeA.insert(keys[i]);

}

printStats (treeA);

System.out.println(" Removing key 3...");

treeA.remove(3);

printStats (treeA);

}

public static void BSTTest3()

// removing the root key from a tree and finding a predecessor.

{

LazyBST treeA = new LazyBST();

System.out.println(" ******Test 3: removing the root key from a tree and finding a successor");

// insert nodes into tree

int[] keys ={13, 3, 23, 8};

for (int i = 0; i

{

treeA.insert(keys[i]);

}

printStats (treeA);

System.out.println(" Removing key 13...");

treeA.remove(13);

printStats (treeA);

}

public static void BSTTest4()

// removing an inner node with no right tree.

{

LazyBST treeA = new LazyBST();

System.out.println(" ******Test 4: removing an inner node with no right subtree");

// insert nodes into tree

int[] keys ={13, 6, 23, 4};

for (int i = 0; i

{

treeA.insert(keys[i]);

}

printStats (treeA);

System.out.println(" Removing key 6...");

treeA.remove(6);

printStats (treeA);

}

public static void BSTTest5()

// removing an inner node with no left subtree.

{

LazyBST treeA = new LazyBST();

System.out.println(" ******Test 5: removing an inner node with no left subtree");

// insert nodes into tree

int[] keys ={13, 6, 23, 8};

for (int i = 0; i

{

treeA.insert(keys[i]);

}

printStats (treeA);

System.out.println(" Removing key 6...");

treeA.remove(6);

printStats (treeA);

}

public static void BSTTest6()

// removing an inner node with a left tree and a right subtree.

{

LazyBST treeA = new LazyBST();

System.out.println(" ******Test 6: removing an inner node with left and right subtrees");

// insert nodes into tree

int[] keys ={33,13,43, 6, 23, 27};

for (int i = 0; i

{

treeA.insert(keys[i]);

}

printStats (treeA);

System.out.println(" Removing key 13...");

treeA.remove(13);

printStats (treeA);

}

public static void BSTTest7()

// removing an inner node with a left tree and a right subtree.

{

LazyBST treeA = new LazyBST();

System.out.println(" ******Test 7: removing an inner node with left and right subtrees");

// insert nodes into tree

int[] keys ={33,13,43, 6, 23, 15,27,18};

for (int i = 0; i

{

treeA.insert(keys[i]);

}

printStats (treeA);

System.out.println(" Removing key 13...");

treeA.remove(13);

printStats (treeA);

}

public static void BSTTest8()

// removing an inner node with a left tree and a right subtree.

{

LazyBST treeA = new LazyBST();

System.out.println(" ******Test 8: removing an inner node with left and right subtrees");

// insert nodes into tree

int[] keys ={33,13,43, 6, 23, 3,8,7};

for (int i = 0; i

{

treeA.insert(keys[i]);

}

printStats (treeA);

System.out.println(" Removing key 13...");

treeA.remove(13);

printStats (treeA);

}

public static void BSTTest9()

// unsuccessful removal.

{

LazyBST treeA = new LazyBST();

System.out.println(" ******Test 9: unsuccessful removal");

// insert nodes into tree

int[] keys ={33,13,43, 6, 23, 3,8,7};

for (int i = 0; i

{

treeA.insert(keys[i]);

}

printStats (treeA);

System.out.println(" Removing key 1...");

if(treeA.remove(1))

System.out.println("found and deleted");

else

System.out.println("not found...");

printStats (treeA);

}

}

Binary Search Trees with Lazy Removal In this lab exercise, you will be completing a partial implementation of a LazyBST class for integer numbers, implementing a binary search tree with a lazy removal strategy, as seen in the lecture slides. The number of non-removed items in the tree and the number of items marked as removed is counted. Download the LazyBST.java file and Ass4Driver.java files from C4 and add them to a new Java project. The driver contains several test cases for insertion and removal. BSTTest00 generates random numbers and inserts them into a LazyBST object. The test cases BSTTest10..., BSTTest80 test specific situations of removing keys from a BST. You can run each test case separately Methods to be completed (18 marks) calculateHeight - this method recursively calculates the height of the (sub)tree rooted at its parameter Hints: The height of a node is 1 the height of its higher subtree. Math.max (a,b) returns the maximum of a and b.(**) contains - this (search) method returns true if an item is in the tree and has not been removed. (**) insert - inserts an item into the LazyBST object. Duplicate keys will be not be inserted, but true will be returned if the item to be inserted is already in the tree Inserting can be completed iteratively in the public method insert(int item), or handed over to a recursive private method insert(LazyBST nd, int item). (**) remove - Removes the specified key from the LazyBST object, using the lazy removal method(2) described in the lecture slides. The method returns false if the key is not found, true otherwise No recursion necessary. (**) rebuild - Rebuilds the existing tree (with nodes marked as removed) into a new tree, containing only the data of nodes not marked as removed. (*** findMin - Returns a reference to the node with the smallest key in the tree This is a recursive method called by findMin). (**) inOrderPrint - Prints the data of the tree in in-order sequence, Removed data will also be printed but marked with an "x". (*) printRecTree recursively prints the contents/structure of the tree, rotated counter-clockwise (2) 90 degrees. Removed data will also be printed but marked with an "x". (*) Deliverables Submit to C4: Your LazyBST.java file with the above methods completed. . Binary Search Trees with Lazy Removal In this lab exercise, you will be completing a partial implementation of a LazyBST class for integer numbers, implementing a binary search tree with a lazy removal strategy, as seen in the lecture slides. The number of non-removed items in the tree and the number of items marked as removed is counted. Download the LazyBST.java file and Ass4Driver.java files from C4 and add them to a new Java project. The driver contains several test cases for insertion and removal. BSTTest00 generates random numbers and inserts them into a LazyBST object. The test cases BSTTest10..., BSTTest80 test specific situations of removing keys from a BST. You can run each test case separately Methods to be completed (18 marks) calculateHeight - this method recursively calculates the height of the (sub)tree rooted at its parameter Hints: The height of a node is 1 the height of its higher subtree. Math.max (a,b) returns the maximum of a and b.(**) contains - this (search) method returns true if an item is in the tree and has not been removed. (**) insert - inserts an item into the LazyBST object. Duplicate keys will be not be inserted, but true will be returned if the item to be inserted is already in the tree Inserting can be completed iteratively in the public method insert(int item), or handed over to a recursive private method insert(LazyBST nd, int item). (**) remove - Removes the specified key from the LazyBST object, using the lazy removal method(2) described in the lecture slides. The method returns false if the key is not found, true otherwise No recursion necessary. (**) rebuild - Rebuilds the existing tree (with nodes marked as removed) into a new tree, containing only the data of nodes not marked as removed. (*** findMin - Returns a reference to the node with the smallest key in the tree This is a recursive method called by findMin). (**) inOrderPrint - Prints the data of the tree in in-order sequence, Removed data will also be printed but marked with an "x". (*) printRecTree recursively prints the contents/structure of the tree, rotated counter-clockwise (2) 90 degrees. Removed data will also be printed but marked with an "x". (*) Deliverables Submit to C4: Your LazyBST.java file with the above methods completed