Binary Search Trees with Lazy Deletion Implement binary search tree class with l
ID: 3797347 • Letter: B
Question
Binary Search Trees with Lazy Deletion
Implement binary search tree class with lazy deletion that has TreeNode as nested class in Java.
Design the class, TreeNode to have following class variables: int key; // All keys are in the range 1 to 99
TreeNode leftChild;
TreeNode rightChild;
boolean deleted;
Your program method must have routines to do the following operations.
insert
//Should insert a new element to a leaf node. If new element is a duplicate then do nothing. If the new element is previously deleted one, then do not add other copy just mark the previous deleted as valid now
delete
//Should not remove the element from the tree. It should just mark the element as deleted.
findMin
//Should return the minimum element, but if it is marked deleted return appropriate minimum
findMax
//Should return the maximum element, but if it is marked deleted return appropriate maximum
contains
//Should return true if a particular element is in the tree and is not marked as deleted
In order tree Traversal
//Should print the in order traversal of the tree. Indicating with * symbol for elements that are marked deleted
Height ( returns the height of the tree)
//Return the height of the tree, count all the elements even the ones that are marked as deleted
No Of nodes ( returns number of nodes + number of deleted nodes)
//Print size of the tree, count all the elements even the ones that are marked as deleted. And
also return the number of deleted elements.
You may have other routines that may be necessary.
The program should prompt user with options to do one of the above routines.
Explanation / Answer
Binary Search Tree with Lazy Deletion implementation in Java Program:
Java Code:
public class BinarySearchTree {
/*-----------------------*
* Variable Declarations *
*-----------------------*/
private TreeNode root;
private int numberOfNodes;
private int numberOfDeletedNodes;
/**
* Constructs a tree with an empty root
*/
public BinarySearchTree() {
root = null;
}
/**
* Releases the root of the tree, rendering it empty
*
* @return void
*/
public void makeEmpty() {
root = null;
}
/**
* Checks to see if the tree is empty
* @return
*/
public boolean isEmpty() {
return root == null;
}
/**
* Searches the tree to see if it contains the specified element
* @param key
* @return
*/
public boolean contains(int key) {
return contains(key, root);
}
/**
* Finds the smallest element in the tree
*
* @return the smallest element in the tree
* @throws Exception
*/
public int findMin() throws Exception {
if (isEmpty()) {
throw new Exception("Tree is empty!");
} else {
return findMin(root).key;
}
}
/**
* Finds the largest element in the tree
*
* @return the largest element in the tree
* @throws Exception
*/
public int findMax() throws Exception {
if (isEmpty()) {
throw new Exception("Tree is empty!");
} else {
return findMax(root).key;
}
}
/**
* Inserts the given element into the tree
* @param key
*/
public void insert(int key) {
root = insert(key, root);
}
/**
* Removes the specified element from the tree
* @param key
*/
public void remove(int key) {
remove(key, root);
}
/**
* Prints the tree contents in sorted order
*
* @return void
*/
public void printTree() {
if (isEmpty()) {
System.out.println("Empty Tree");
} else {
printTree(root);
}
}
public int height() throws Exception{
if (isEmpty()) {
throw new Exception("Tree is empty!");
} else {
return height(root);
}
}
/**
* Internal method to compute height of a subtree.
* @param treeNode
* @return
*/
private int height(TreeNode treeNode) {
if (treeNode == null) {
return -1;
} else {
return 1 + Math.max(height(treeNode.leftChild), height(treeNode.rightChild));
}
}
/**
* The method to find an item in a subtree
* @param key
* @param treeNode
* @return
*/
private boolean contains(int key, TreeNode treeNode) {
if (treeNode == null) {
return false;
}
if (key < treeNode.key) {
return contains(key, treeNode.leftChild);
} else if (key > treeNode.key) {
return contains(key, treeNode.rightChild);
} else if(treeNode.deleted) {
return false; // Match & deleted
}else{
return true;
}
}
/**
* The method to find the smallest item in a subtree
* @param treeNode
* @return
*/
private TreeNode findMin(TreeNode treeNode) {
if (treeNode == null) {
return null;
} else if (treeNode.leftChild == null) {
return treeNode;
} else {
return findMin(treeNode.leftChild);
}
}
/**
* The method to find the largest item in a subtree
* @param treeNode
* @return
*/
private TreeNode findMax(TreeNode treeNode) {
if (treeNode == null) {
return null;
} else if (treeNode.rightChild == null) {
return treeNode;
} else {
return findMax(treeNode.rightChild);
}
}
/**
* The method to insert into a subtree Duplicates are not allowed and
* ignored
* @param key
* @param treeNode
* @return
*/
private TreeNode insert(int key, TreeNode treeNode) {
if (treeNode == null) {
numberOfNodes++;
return new TreeNode(key);
}
if (key < treeNode.key) {
treeNode.leftChild = insert(key, treeNode.leftChild);
} else if (key > treeNode.key) {
treeNode.rightChild = insert(key, treeNode.rightChild);
} else if(treeNode.deleted) {
//mark the previous deleted as valid now
treeNode.deleted=false;
numberOfDeletedNodes--;
}else{
// Duplicate; do nothing
}
return treeNode;
}
/**
* The method to remove an element from a subtree
* @param key
* @param treeNode
* @return
*/
private void remove(int key, TreeNode treeNode) {
if (treeNode == null) {
System.out.println("Element not found to remove!");
}
if (key < treeNode.key) {
remove(key, treeNode.leftChild);
} else if (key > treeNode.key) {
remove(key, treeNode.rightChild);
} else {
//Mark soft delete
treeNode.deleted=true;
numberOfNodes--;
// Match
}
}
/**
* The method to print a subtree in sorted order
*
* @param treeNode
*/
private void printTree(TreeNode treeNode) {
if (treeNode != null) {
printTree(treeNode.leftChild);
if(!treeNode.deleted)
System.out.print(treeNode.key+" ");
printTree(treeNode.rightChild);
}
}
public int noOfNodes(){
return numberOfNodes+numberOfDeletedNodes;
}
/**
* TreeNode as nested class
*/
private static class TreeNode {
/*-----------------------*
* Variable Declarations *
*-----------------------*/
private int key; // The data in the node
private TreeNode leftChild; // The left child node
private TreeNode rightChild; // The right child node
private boolean deleted; // The lazy deleted flag
/**
* Constructs a new TreeNode of type int that contains the given element
*
* @param key
*/
private TreeNode(int key) {
this(key, null, null);
}
/**
* Constructs a new TreeNode of type int that contains the given key and
* has the given nodes as its left and right children respectively
*
* @param key
* @param leftChild
* @param rightChild
*/
private TreeNode(int key, TreeNode leftChild, TreeNode rightChild) {
this.key = key;
this.leftChild = leftChild;
this.rightChild = rightChild;
}
}
}
public class BinarySearchTreeDriver {
/**
* @param args
*/
public static void main(String[] args) {
try {
BinarySearchTree binarySearchTree=new BinarySearchTree();
binarySearchTree.insert(10);
binarySearchTree.insert(20);
binarySearchTree.insert(30);
binarySearchTree.insert(40);
binarySearchTree.insert(50);
System.out.println("");
binarySearchTree.printTree();
System.out.println(" Height:"+binarySearchTree.height());
//delete
binarySearchTree.remove(50);
System.out.println("");
binarySearchTree.printTree();
System.out.println(" "+binarySearchTree.contains(50));
binarySearchTree.remove(30);
System.out.println("");
binarySearchTree.printTree();
binarySearchTree.insert(60);
System.out.println("");
binarySearchTree.printTree();
System.out.println("Max:"+binarySearchTree.findMax());
System.out.println("Min:"+binarySearchTree.findMin());
System.out.println("noOfNodes:"+binarySearchTree.noOfNodes());
System.out.println("");
System.out.println(" Height:"+binarySearchTree.height());
} catch (Exception e) {
System.out.println(e.getMessage());
}
}
}
Steps to run the program:
1. Compile program :
javac BinarySearchTree.java
javac BinarySearchTreeDriver.java
2. Run program:
java BinarySearchTreeDriver
Sample Output:
10 20 30 40 50
Height:4
10 20 30 40
false
10 20 40
10 20 40 60 Max:60
Min:10
noOfNodes:4
Height:5
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.