Modify the class BinarySearchTree (BST) from your completed Lab Below to add a p
ID: 3547989 • Letter: M
Question
Modify the class BinarySearchTree (BST) from your completed Lab Below to add a public boolean remove(int item) method. The method must be capable of removing an item in the BST no matter where it happens to be stored, and making the necessary rearrangements to the BST so it remains correct. If the Node to be removed has two child Nodes, then its replacement should be from the longer of its two sub-trees. Rename the class containing the main() to Lab6B, and modify the main to demonstrate that your method works for various cases, while preserving the BST.
Be sure the entire solution maintains a single file structure containing all three of the classes involved.
class Node {
private int info; // element stored in this node
private Node left; // link to left child
private Node right; // link to right child
// Initializes the node
Node() {
info = 0;
left = right = null;
}
// Sets this node
void setNode(int x, Node l, Node r) {
info = x;
left = l;
right = r;
}
// Returns the value in this node
int getInfo() {
return info;
}
// Returns the link to the left child
Node getLeftChild() {
return left;
}
// Returns the link to the right child
Node getRightChild() {
return right;
}
// Sets the value for this node
void setInfo(int x) {
info = x;
}
// Sets the link to the left child
void setLeftChild(Node l) {
left = l;
}
// Sets the link to the right child
void setRightChild(Node r) {
right = r;
}
}
// /////////////////////////////////////////////////////////////////////////////
// Class implementing a binary search tree
class BinarySearchTree {
private Node root; // root of the bst. It's implemented as a dummy node.
private String inOrderString = "";
// Initializes the bst to empty creating a dummy root node
public BinarySearchTree() {
root = new Node(); // dummy node as the root
root.setLeftChild(null);
root.setRightChild(null);
root.setInfo(-1);
}
// Determines whether the bst is empty
public boolean isEmpty() {
return root.getLeftChild() == null;
}
// Prints the bst elements using inorder traversal
// This method invokes the private inorderDisplay mehod
public void display() {
inorderDisplay(root.getLeftChild());
System.out.println();
}
private int nodeCountHelper(Node p,int count){
if (p != null) {
count = nodeCountHelper(p.getLeftChild(),count);
count ++;
count = nodeCountHelper(p.getRightChild(),count);
}
return count;
}
public int nodeCount(){
return nodeCountHelper(root.getLeftChild(), 0);
}
private void inOrderToString(Node p){
if (p != null) {
inOrderToString(p.getLeftChild());
inOrderString += p.getInfo() + " ";
inOrderToString(p.getRightChild());
}
}
public String toString(){
inOrderString = "";
inOrderToString(root.getLeftChild());
return inOrderString;
}
// Determines if an item exists in the bst. This method invokes the private
// method search, passing to it the element to be found and the root
// of the actual tree.
public boolean contains(int x) {
return search(x, root.getLeftChild());
}
// Adds the element x to the bst. This method invokes the private method
// insert, passing to it the element to be added to the bst and the root
// of the actual tree.
public void add(int x) {
if (root.getLeftChild() == null) {
Node p = new Node();
p.setNode(x, null, null);
root.setLeftChild(p);
} else
insert(x, root.getLeftChild());
}
// Finds the smallest element in the bst. This method invokes the overloaded
// method getMin, passing to it the root of the tree.
public int getMin() {
return getMin(root);
}
public int getMax(){
return getMax(root.getLeftChild());
}
// //////////////// Private methods ////////////////////////////////////////
// Prints the elements of the subtree whose root is referenced by p. Uses
// inorder traversal.
private void inorderDisplay(Node p) {
if (p != null) {
inorderDisplay(p.getLeftChild());
System.out.print(p.getInfo() + " ");
inorderDisplay(p.getRightChild());
}
}
// Finds if x is inserted in the subtree whose root is referenced by p. The
// search is conducted recursively, using the bst property: keys in the left
// subtree of a node are smaller than or equal to the key in the node, while
// the keys in the right subtree of the node are greater.
private boolean search(int x, Node p) {
if (p == null)
return false;
else if (x == p.getInfo())
return true;
else if (x < p.getInfo())
return search(x, p.getLeftChild());
else
return search(x, p.getRightChild());
}
// Adds x to the subtree referenced by p. The search for the location to
// insert the new node is conducted recursively, using the bst property:
// keys in the left subtree of a node are smaller than or equal to the key
// in the node, while the keys in the right subtree of the node are greater.
private void insert(int x, Node p) {
if (x < p.getInfo())
if (p.getLeftChild() == null) {
Node q = new Node();
q.setNode(x, null, null);
p.setLeftChild(q);
}
else
insert(x, p.getLeftChild());
else if (p.getRightChild() == null) {
Node q = new Node();
q.setNode(x, null, null);
p.setRightChild(q);
}
else
insert(x, p.getRightChild());
}
// Recursively finds the smallest element in the subtree referenced by p.
// The method uses this property of BSTs: the smallest value is stored in
// the leftmost node.
private int getMin(Node p) {
if (p.getLeftChild() == null)
return p.getInfo();
else
return getMin(p.getLeftChild());
}
private int getMax(Node p) {
if(p.getRightChild()==null){
return p.getInfo();
}else{
return getMax(p.getRightChild());
}
}
}
// /////////////////////////////////////////////////////////////////////////////
// Class testing the binary search tree.
public class Lab6A {
public static void main(String[] args) {
BinarySearchTree bst = new BinarySearchTree();
for (int i = 0; i < 10; i++) {
int x = (int) (Math.random() * 100);
System.out.print(x + " ");
bst.add(x);
}
System.out.println();
bst.display();
System.out.println("Max node: "+bst.getMax());
System.out.println("BST to string function: "+bst);
System.out.println("Node count: "+bst.nodeCount());
}
}
Explanation / Answer
class Node
{
private int info; // element stored in this node
private Node left; // link to left child
private Node right; // link to right child
// Initializes the node
Node()
{
info = 0;
left = right = null;
}
// Sets this node
void setNode(int x, Node l, Node r)
{
info = x;
left = l;
right = r;
}
// Returns the value in this node
int getInfo()
{
return info;
}
// Returns the link to the left child
Node getLeftChild()
{
return left;
}
// Returns the link to the right child
Node getRightChild()
{
return right;
}
// Sets the value for this node
void setInfo(int x)
{
info = x;
}
// Sets the link to the left child
void setLeftChild(Node l)
{
left = l;
}
// Sets the link to the right child
void setRightChild(Node r)
{
right = r;
}
}
// /////////////////////////////////////////////////////////////////////////////
// Class implementing a binary search tree
class BinarySearchTree
{
private Node root; // root of the bst. It's implemented as a dummy node.
private String inOrderString = "";
// Initializes the bst to empty creating a dummy root node
public BinarySearchTree()
{
root = new Node(); // dummy node as the root
root.setLeftChild(null);
root.setRightChild(null);
root.setInfo(-1);
}
// Determines whether the bst is empty
public boolean isEmpty()
{
return root.getLeftChild() == null;
}
// Prints the bst elements using inorder traversal
// This method invokes the private inorderDisplay mehod
public void display()
{
inorderDisplay(root.getLeftChild());
System.out.println();
}
private int nodeCountHelper(Node p, int count)
{
if (p != null)
{
count = nodeCountHelper(p.getLeftChild(), count);
count++;
count = nodeCountHelper(p.getRightChild(), count);
}
return count;
}
public int nodeCount()
{
return nodeCountHelper(root.getLeftChild(), 0);
}
private void inOrderToString(Node p)
{
if (p != null)
{
inOrderToString(p.getLeftChild());
inOrderString += p.getInfo() + " ";
inOrderToString(p.getRightChild());
}
}
public String toString()
{
inOrderString = "";
inOrderToString(root.getLeftChild());
return inOrderString;
}
// Determines if an item exists in the bst. This method invokes the private
// method search, passing to it the element to be found and the root
// of the actual tree.
public boolean contains(int x)
{
return search(x, root.getLeftChild());
}
// Adds the element x to the bst. This method invokes the private method
// insert, passing to it the element to be added to the bst and the root
// of the actual tree.
public void add(int x)
{
if (root.getLeftChild() == null)
{
Node p = new Node();
p.setNode(x, null, null);
root.setLeftChild(p);
}
else
insert(x, root.getLeftChild());
}
// Finds the smallest element in the bst. This method invokes the overloaded
// method getMin, passing to it the root of the tree.
public int getMin()
{
return getMin(root);
}
public int getMax()
{
return getMax(root.getLeftChild());
}
// //////////////// Private methods ////////////////////////////////////////
// Prints the elements of the subtree whose root is referenced by p. Uses
// inorder traversal.
private void inorderDisplay(Node p)
{
if (p != null)
{
inorderDisplay(p.getLeftChild());
System.out.print(p.getInfo() + " ");
inorderDisplay(p.getRightChild());
}
}
// Finds if x is inserted in the subtree whose root is referenced by p. The
// search is conducted recursively, using the bst property: keys in the left
// subtree of a node are smaller than or equal to the key in the node, while
// the keys in the right subtree of the node are greater.
private boolean search(int x, Node p)
{
if (p == null)
return false;
else if (x == p.getInfo())
return true;
else if (x < p.getInfo())
return search(x, p.getLeftChild());
else
return search(x, p.getRightChild());
}
// Adds x to the subtree referenced by p. The search for the location to
// insert the new node is conducted recursively, using the bst property:
// keys in the left subtree of a node are smaller than or equal to the key
// in the node, while the keys in the right subtree of the node are greater.
private void insert(int x, Node p)
{
if (x < p.getInfo())
if (p.getLeftChild() == null)
{
Node q = new Node();
q.setNode(x, null, null);
p.setLeftChild(q);
}
else
insert(x, p.getLeftChild());
else if (p.getRightChild() == null)
{
Node q = new Node();
q.setNode(x, null, null);
p.setRightChild(q);
}
else
insert(x, p.getRightChild());
}
// Recursively finds the smallest element in the subtree referenced by p.
// The method uses this property of BSTs: the smallest value is stored in
// the leftmost node.
private int getMin(Node p)
{
if (p.getLeftChild() == null)
return p.getInfo();
else
return getMin(p.getLeftChild());
}
private int getMax(Node p)
{
if (p.getRightChild() == null)
{
return p.getInfo();
}
else
{
return getMax(p.getRightChild());
}
}
// Remove the item from the tree
public boolean remove(int x)
{
return removeItem(root, root.getLeftChild(), x);
}
public boolean removeItem(Node parent, Node p, int x)
{
if (p == null)
return false;
if (x < p.getInfo())
return removeItem(p, p.getLeftChild(), x);
else if (x > p.getInfo())
return removeItem(p, p.getRightChild(), x);
// find x
if (p.getLeftChild() == null) // no left child
{
if (parent.getLeftChild() == p)
parent.setLeftChild(p.getRightChild());
else
parent.setRightChild(p.getRightChild());
}
else if (p.getRightChild() == null) // no right child
{
if (parent.getLeftChild() == p)
parent.setLeftChild(p.getLeftChild());
else
parent.setRightChild(p.getLeftChild());
}
else if (nodeCountHelper(p.getLeftChild(), 0) > nodeCountHelper(p.getRightChild(), 0))
{
// its replacement from left subtree
Node rp = null;
Node next = p.getLeftChild();
while (next.getRightChild() != null)
{
rp = next;
next = next.getRightChild();
}
if (rp == null)
{
p.setInfo(next.getInfo());
p.setLeftChild(next.getLeftChild());
}
else
{
p.setInfo(next.getInfo());
rp.setRightChild(next.getLeftChild());
}
}
else
{
// its replacement from right subtree
Node rp = null;
Node next = p.getRightChild();
while (next.getLeftChild() != null)
{
rp = next;
next = next.getLeftChild();
}
if (rp == null)
{
p.setInfo(next.getInfo());
p.setRightChild(next.getRightChild());
}
else
{
p.setInfo(next.getInfo());
rp.setLeftChild(next.getRightChild());
}
}
return true;
}
}
// /////////////////////////////////////////////////////////////////////////////
// Class testing the binary search tree.
public class Lab6B
{
public static void main(String[] args)
{
BinarySearchTree bst = new BinarySearchTree();
int[] data = new int[10];
for (int i = 0; i < 10; i++)
{
int x = (int) (Math.random() * 100);
data[i] = x;
System.out.print(x + " ");
bst.add(x);
}
System.out.println();
bst.display();
System.out.println("Max node: " + bst.getMax());
System.out.println("BST to string function: " + bst);
System.out.println("Node count: " + bst.nodeCount());
// delete random 5 numbers
for (int i = 0; i < 5; i++)
{
int x = (int) (Math.random() * 100);
System.out.print("remove("+x+")=" + bst.remove(x));
System.out.println(" : " + bst);
}
// delete 10 numbers
for (int i = 0; i < 10; i++)
{
int x = data[i];
System.out.print("remove("+x+")=" + bst.remove(x));
System.out.println(" : " + bst);
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.