Binary Search Trees with Lazy Deletion Implement binary search tree class with l
ID: 3673377 • 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.
1. insert
//Should insert a new element to a leaf node. If new element is aduplicatethen do nothing.
If the new element is previously deleted one, then do not add other copy just mark the previous
deleted as valid now
2. delete
//Should not remove the element from the tree. It should just mark the element as deleted.
3. findMin
//Should return the minimum element, butif it is marked deleted return appropriate minimum
4. findMax
//Should return the maximumelement, butif it is marked deleted return appropriate maximum
5. contains
//Should return true if a particular element is in the tree and is not marked as deleted
6. In order tree Traversal
//Should print the in order traversal of the tree. Indicating with * symbol for elements that are marked deleted
7. 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
8. No Of nodes ( returns number of nodes)
//Return 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.
Sample Run:
Binary Search Trees
1. Insert
2. Delete
3. Find Max
4. FindMin
5. Contains
6. In order Tree Traversal
7. Height
8. No Of Nodes
Your Option: 1
Enter element: 11
Element inserted
Your Option: 1
Enter Element: 36
Element Inserted
Your option: 1
Enter Element: 5
Element Inserted
Your Option: 6
In order Traversal
5 11 36
Your Option: 7
Height = 1
Your Option: 8
No Of Nodes = 3
No Of Deleted Nodes = 0
Note you will be doing lazy deletion, meaning you will not be deleting the node but only mark it for deletion. It is ok to display the deleted node put an * before it to indicate it is deleted.
Example:
In order Traversal = 20 *5 30 45 47 50 *60
(Indicating 5 and 60 are deleted node)
Explanation / Answer
Hi, I have implemented all function. I have also tested with insert function.
Please add menu in main program, just use whichever function you wan t to use.
// Java program to demonstrate insert operation in binary search tree
class BinarySearchTree {
/* Class containing left and right child of current node and key value*/
class Node {
int key;
Node left, right;
boolean deleted;
public Node(int item) {
key = item;
left = right = null;
deleted = false;
}
}
// Root of BST
Node root;
int N; // number of nodes
// Constructor
BinarySearchTree() {
root = null;
N = 0;
}
// This method mainly calls insertRec()
void insert(int key) {
root = insertRec(root, key);
N++; // increase number of nodes
}
/* A recursive function to insert a new key in BST */
Node insertRec(Node root, int key) {
/* If the tree is empty, return a new node */
if (root == null) {
root = new Node(key);
return root;
}
/* Otherwise, recur down the tree */
if (key < root.key)
root.left = insertRec(root.left, key);
else if (key > root.key)
root.right = insertRec(root.right, key);
/* return the (unchanged) node pointer */
return root;
}
// This method mainly calls InorderRec()
void inorder() {
inorderRec(root);
}
// A utility function to do inorder traversal of BST
void inorderRec(Node root) {
if (root != null) {
inorderRec(root.left);
System.out.println(root.key);
inorderRec(root.right);
}
}
// A utility function to search a given key in BST
public boolean contains(Node root, int key)
{
// Base Cases: root is null or key is present at root
if (root==null)
return false;
if(root.key==key)
return true;;
// val is greater than root's key
if (root.key > key)
return contains(root.left, key);
// val is less than root's key
return contains(root.right, key);
}
// This method mainly calls deleteRec()
void deleteKey(int key)
{
root = deleteRec(root, key);
}
/* A recursive function to insert a new key in BST */
void deleteRec(Node root, int key)
{
/* Base Case: If the tree is empty */
if (root == null) return ;
/* Otherwise, recur down the tree */
if (key < root.key)
deleteRec(root.left, key);
else if (key > root.key)
deleteRec(root.right, key);
// if key is same as root's key, then This is the node
// to be deleted
else
{
root.deleted = true;
N--; // decrease number of nodes
}
return
}
/* Given a non-empty binary search tree,
return the minimum data value found in that
tree. Note that the entire tree does not need
to be searched. */
int minvalue(Node node) {
Node current = node;
/* loop down to find the leftmost leaf */
while (current.left != null) {
current = current.left;
}
return (current.data);
}
/* Given a non-empty binary search tree,
return the maximum data value found in that
tree. Note that the entire tree does not need
to be searched. */
int maxvalue(Node node) {
Node current = node;
/* loop down to find the leftmost leaf */
while (current.left != null) {
current = current.left;
}
return (current.data);
}
/* Compute the "height" of a tree -- the number of
nodes along the longest path from the root node
down to the farthest leaf node.*/
int height(Node node) {
if (node == null) {
return 0;
} else {
/* compute the depth of each subtree */
int lDepth = height(node.left);
int rDepth = height(node.right);
/* use the larger one */
if (lDepth > rDepth) {
return (lDepth + 1);
} else {
return (rDepth + 1);
}
}
}
// retuen Number of Nodes of tree
int numberOfNodes(){
return N;
}
// Driver Program to test above functions
public static void main(String[] args) {
BinarySearchTree tree = new BinarySearchTree();
/* Let us create following BST
50
/
30 70
/ /
20 40 60 80 */
tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(70);
tree.insert(60);
tree.insert(80);
// print inorder traversal of the BST
tree.inorder();
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.