Question

In: Computer Science

Binary Search Trees with Lazy Deletion Implement binary search tree class with lazy deletion that has...

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.

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.

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 + number of deleted nodes)

//Return and 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.

The Java program should prompt user with options to do one of the above routines.

Solutions

Expert Solution

public class BinarySearchTree {

                public static Node root;

                public BinarySearchTree(){

                this.root = null;

                }

                public boolean find(int id){

                Node current = root;

                while(current!=null){

                if(current.data==id){

                return true;

                }else if(current.data>id){

                current = current.left;

                }else{

                current = current.right;

                }

                }

                return false;

                }

                public boolean delete(int id){

                Node parent = root;

                Node current = root;

                boolean isLeftChild = false;

                while(current.data!=id){

                parent = current;

                if(current.data>id){

                isLeftChild = true;

                current = current.left;

                }else{

                isLeftChild = false;

                current = current.right;

                }

                if(current ==null){

                return false;

                }

                }

                if(current.left==null && current.right==null){

                if(current==root){

                root = null;

                }

                if(isLeftChild ==true){

                parent.left = null;

                }else{

                parent.right = null;

                }

                }

                else if(current.right==null){

                if(current==root){

                root = current.left;

                }else if(isLeftChild){

                parent.left = current.left;

                }else{

                parent.right = current.left;

                }

                }

                else if(current.left==null){

                if(current==root){

                root = current.right;

                }else if(isLeftChild){

                parent.left = current.right;

                }else{

                parent.right = current.right;

                }

                }else if(current.left!=null && current.right!=null){

                Node successor                = getSuccessor(current);

                if(current==root){

                root = successor;

                }else if(isLeftChild){

                parent.left = successor;

                }else{

parent.right = successor;

}                                             

successor.left = current.left;

}                             

return true;                       

}

public Node getSuccessor(Node deleleNode){

Node successsor =null;

Node successsorParent =null;

Node current = deleleNode.right;

while(current!=null){

successsorParent = successsor;

successsor = current;

current = current.left;

}

if(successsor!=deleleNode.right){

successsorParent.left = successsor.right;

successsor.right = deleleNode.right;

}

return successsor;

}

public void insert(int id){

Node newNode = new Node(id);

if(root==null){

root = newNode;

return;

}

Node current = root;

Node parent = null;

while(true){

parent = current;

if(id<current.data){                                                        

current = current.left;

if(current==null){

parent.left = newNode;

return;

}

}else{

current = current.right;

if(current==null){

parent.right = newNode;

return;

}

}

}

}

public void display(Node root){

if(root!=null){

display(root.left);

System.out.print(" " + root.data);

display(root.right);

}

}

public static void main(String arg[]){

BinarySearchTree b = new BinarySearchTree();

b.insert(3);b.insert(8);

b.insert(1);b.insert(4);b.insert(6);b.insert(2);b.insert(10);b.insert(9);

b.insert(20);b.insert(25);b.insert(15);b.insert(16);

System.out.println("Original Tree : ");

b.display(b.root);                            

System.out.println("");

System.out.println("Check whether Node with value 4 exists : " + b.find(4));

System.out.println("Delete Node with no children (2) : " + b.delete(2));                               

b.display(root);

System.out.println("\n Delete Node with one child (4) : " + b.delete(4));                              

b.display(root);

System.out.println("\n Delete Node with Two children (10) : " + b.delete(10));                 

b.display(root);

}

}

class Node

{

int data;

Node left;

Node right;        

public Node(int data)

{

this.data = data;

left = null;

right = null;

}

}


Related Solutions

Lab 5: Binary Search Tree Implement operations for a Binary Search Tree class starting from the...
Lab 5: Binary Search Tree Implement operations for a Binary Search Tree class starting from the template provided under the PolyLearn assignment, using the class TreeNode that is also provided. You may (should) implement helper methods that make your code easier to write, read, and understand. You will also need to write test cases of your own as you develop the methods. You may use iterative and/or recursive functions in your implementation. The following starter files are available . •...
Implement a function to find a node in a binary search tree. Using the following class...
Implement a function to find a node in a binary search tree. Using the following class and function definition. If a node with a matching value is found, return a pointer to it. If no match is found, return nullptr. #include <iostream> class BTNode { public: int item; BTNode *left; BTNode *right; BTNode(int i, BTNode *l=nullptr, BTNode *r=nullptr):item(i),left(l),right(r){} }; BTNode *root = nullptr; BTNode *find(int item) { //implement code here return nullptr; } int main() {    root = new...
Implement a function to find a node in a binary search tree. Using the following class...
Implement a function to find a node in a binary search tree. Using the following class and function definition: class BTNode { public: int item; BTNode *left; BTNode *right; BTNode(int i, BTNode *l=nullptr, BTNode *r=nullptr):item(i),left(l),right(r){} }; BTNode *root = nullptr; BTNode* find(int i) { // implement } If a node with a matching value is found, return a pointer to it. If no match is found, return nullptr. #include <iostream> class BTNode { public: int item; BTNode *left; BTNode *right;...
I was trying to implement a simple binary search tree using this given class of bst...
I was trying to implement a simple binary search tree using this given class of bst in c++ public: BST(); ~BST(); void insertKey(int newKey); bool hasKey(int searchKey); std::vector<int> inOrder(); int getHeight(); however; i am still required to use another class for the nodes as a pointer and i need to manage memory leak. in main we should ask for the numbers we need to insert in the binary search tree and also let the user end it with a letter...
Implement a Binary tree using an array using class.
Implement a Binary tree using an array using class.
In C++, dealing with Binary Search trees. Implement search, insert, removeLeaf, and removeNodeWithOneChild methods in BST.h....
In C++, dealing with Binary Search trees. Implement search, insert, removeLeaf, and removeNodeWithOneChild methods in BST.h. BST.h code below. CPP code also provided for reference, nothing to be changed on cpp code. #include #include "BSTNode.h" using namespace std; #ifndef BST_H_ #define BST_H_ class BST { public: BSTNode *root; int size; BST() { root = NULL; size = 0; } ~BST() { if (root != NULL) deepClean(root); } BSTNode *search(int key) { // complete this method } BSTNode *insert(int val) {...
In C++, dealing with Binary Search trees. Implement search, insert, removeLeaf, and removeNodeWithOneChild methods in BST.h....
In C++, dealing with Binary Search trees. Implement search, insert, removeLeaf, and removeNodeWithOneChild methods in BST.h. BST.h code below #include <iostream> #include "BSTNode.h" using namespace std; #ifndef BST_H_ #define BST_H_ class BST { public: BSTNode *root; int size; BST() { root = NULL; size = 0; } ~BST() { if (root != NULL) deepClean(root); } BSTNode *search(int key) { // complete this method } BSTNode *insert(int val) { // complete this method } bool remove(int val) { // complete this...
In C++, dealing with Binary Search trees. Implement search, insert, removeLeaf, and removeNodeWithOneChild methods in BST.h....
In C++, dealing with Binary Search trees. Implement search, insert, removeLeaf, and removeNodeWithOneChild methods in BST.h. BST.h code below #include <iostream> #include "BSTNode.h" using namespace std; #ifndef BST_H_ #define BST_H_ class BST { public: BSTNode *root; int size; BST() { root = NULL; size = 0; } ~BST() { if (root != NULL) deepClean(root); } BSTNode *search(int key) { // complete this method } BSTNode *insert(int val) { // complete this method } bool remove(int val) { // complete this...
Prerequisite Knowledge Understand binary search tree structure Understand binary search tree operations Understand binary search tree...
Prerequisite Knowledge Understand binary search tree structure Understand binary search tree operations Understand binary search tree worst case and best case time. Learning Outcomes Describe AVL tree structure Trace and implement AVL tree operations Explain and prove AVL tree performance
Binary Tree Develop algorithms for performing various operations of binary tree like insertion and deletion of...
Binary Tree Develop algorithms for performing various operations of binary tree like insertion and deletion of elements, finding an element in the binary tree. Analyse time and space complexity of the designed algorithm Write C++ program to implement binary tree
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT