Programming Language: Java Please adapt/implement and expand a binary search tre
ID: 3572770 • Letter: P
Question
Programming Language: Java
Please adapt/implement and expand a binary search tree (BST) data structure along with all common operations on BSTs plus several additional operations with a main method/function containing testing code. It is highly preferred that your program is implemented in one single class
Basic Setup: Implement or adapt a BST class (preferred) or a package of data structures and functions that contains implementation of the following operations on BSTs: inorder/preorder/postorder walk, search, maximum, minimum, predecessor, successor, insert and delete. You also need to include testing code to verify the correctness of your program. In particular, you should test all the operations on a randomly built BST. For this project, each node in a BST should at least four fields: key (called element in the provided code), p, left, and right, representing the key value, and parent, left, and right child nodes of the given node. In addition, key values of all nodes in a BST are assumed to be integers.
Sub-BST: Write a method/function that decides whether a given BST is a sub-BST of another BST. Note that a BST t1 is a sub-BST of t2 iff one of the following holds:
key[root[t1]] = key[root[t2]], and left[t1] and right[t1] are sub-BSTs of left[t2] and right[t2], respectively,
t1 is a sub-BST of left[t2], or
t1 is a sub-BST of right[t2].
Note also that an empty BST (root=nil) is a subBST of any BST.
Difference of Pairs on a BST: Write a method/function that outputs two pointers pointing to two nodes, x and y, in a given BST, where the key values of x and y differ by a given integer k. Recall that we had given the following algorithm that on an sorted input array A and given value k returns two indices i and j, where A[i] – A[j] = k, or report error if such i and j do not exist:
i1; j2;
nlength[A] //assuming indices of A start with 1
while (jn and in)
d A[i] – A[j]
if (d==k)
return (i, j)
if (d<k)
i++
else
j++
return (-1, -1) //To indicate no such i and j exists.
Now you just need to adapt the above algorithm to work on a BST and return two (references/pointers of) nodes (not just the values) in the BST with the desired property. Since the above algorithm runs in O(n) time on an sorted array of n elements, the algorithm entailed by your method/function should also run in O(n) time.
Pruning BSTs: write a method/function that prunes a BST by “deleting” nodes with key values out of a given range [min, max]. Since actual deletions of nodes from BST is expensive (O(h) time for BSTs of height h) and also some applications might require fast recovery of deleted nodes, we will just put “deletion marks” on those nodes instead of actually deleting them. There are two types of marks we can use to mark nodes: (1) type-I marks indicating that the marked nodes are unavailable (“deleted”); and (2) type-II marks indicating that all nodes in the subtree rooted at the marked nodes are unavailable (“deleted”). The algorithm entailed by your program should run in O(h) time and mark no more than O(h) nodes.
Explanation / Answer
class BSTNode {
private String key;
private BSTNode parent;
private BSTNode leftChild;
private BSTNode rightChild;
public String getKey() {
return key;
}
public void setKey(String key) {
this.key = key;
}
public BSTNode getParent() {
return parent;
}
public void setParent(BSTNode parent) {
this.parent = parent;
}
public BSTNode getLeftChild() {
return leftChild;
}
public void setLeftChild(BSTNode leftChild) {
this.leftChild = leftChild;
}
public BSTNode getRightChild() {
return rightChild;
}
public void setRightChild(BSTNode rightChild) {
this.rightChild = rightChild;
}
}
// this class provides the API for a Binary Search Tree implementation
class BSTree {
private BSTNode root; // this field refers to the root node of the Binary Search Tree
// this is the constructor for the Binary Search Tree class
public BSTree() { this.root = null; }
public void setRoot(BSTNode root) { this.root = root; }
public BSTNode getRoot() { return this.root; }
// this method does the inorder tree walk on the binary search tree
public void inorderTreeWalk(BSTNode node) {
if(node == null) {
return;
}
inorderTreeWalk(node.getLeftChild());
System.out.print(node.getKey() + " ");
inorderTreeWalk(node.getRightChild());
}
// this method does the pre-order tree walk on the binary search tree
public void preorderTreeWalk(BSTNode node) {
if(node == null) {
return;
}
System.out.print(node.getKey() + " ");
preorderTreeWalk(node.getLeftChild());
preorderTreeWalk(node.getRightChild());
}
// this method does the post-order tree walk on the binary search tree
public void postorderTreeWalk(BSTNode node) {
if(node == null) {
return;
}
postorderTreeWalk(node.getLeftChild());
postorderTreeWalk(node.getRightChild());
System.out.print(node.getKey() + " ");
}
// this method finds the node with the minimum key value in the Binary Search Tree
public BSTNode findMinimum() {
BSTNode temp = this.root;
while(temp.getLeftChild() != null) {
temp = temp.getLeftChild();
}
return temp;
}
// this method finds the node with the maximum key value in the Binary Search Tree
public BSTNode findMaximum() {
BSTNode temp = this.root;
while (temp.getRightChild() != null) {
temp = temp.getRightChild();
}
return temp;
}
// this method is used to search the Binary Search Tree for a node with the value passed in the parameter
public BSTNode searchNode(String key) {
BSTNode temp = this.root;
while(temp != null && !temp.getKey().equals(key)) {
if(key.compareTo(temp.getKey()) <= 0) {
temp = temp.getLeftChild();
} else {
temp = temp.getRightChild();
}
}
return temp;
}
// this is a private method that is useful in finding the successor of a node passed to the method
private BSTNode helpFindSuccessor(BSTNode node) {
if(node == null) {
return null;
}
while(node.getLeftChild() != null) {
node = node.getLeftChild();
}
return node;
}
// this method is used to find the successor node of the node with the given input key
public BSTNode getSuccessor(String key) {
BSTNode node = searchNode(key);
if(node == null) {
return null;
}
if(node.getRightChild() != null) {
return helpFindSuccessor(node.getRightChild());
}
BSTNode successorNode = node.getParent();
while(successorNode != null && successorNode.getLeftChild() != node) {
node = successorNode;
successorNode = successorNode.getParent();
}
return successorNode;
}
// this private method helps us in find the predecessor node in the left subtree of a binary search tree
private BSTNode helpFindPredecessor(BSTNode node) {
if(node == null) {
return null;
}
while(node.getRightChild() != null) {
node = node.getRightChild();
}
return node;
}
// this method is used to find the predecessor node of the node with the given input key
public BSTNode getPredecessor(String key) {
BSTNode node = searchNode(key);
if(node == null) {
return null;
}
if(node.getLeftChild() != null) {
return helpFindPredecessor(node.getLeftChild());
}
BSTNode predecessorNode = node.getParent();
while(predecessorNode != null && node != predecessorNode.getRightChild()) {
node = predecessorNode;
predecessorNode = predecessorNode.getParent();
}
return predecessorNode;
}
// this method inserts a node with a given value in the Binary Search Tree
public void insertNode(String value) {
// allocate a new node object for the key that needs to be inserted in the Binary Search Tree
BSTNode node = new BSTNode();
node.setKey(value);
node.setParent(null);
node.setLeftChild(null);
node.setRightChild(null);
// if the Binary Search Tree is initially empty then we make the new node to be the root of the Binary Search Tree
if(this.root == null) {
this.root = node;
} else {
BSTNode parentNode = null;
BSTNode temp = this.root;
while(temp != null) {
parentNode = temp;
int compareValue = node.getKey().compareTo(temp.getKey());
if(compareValue <= 0) {
temp = temp.getLeftChild();
} else {
temp = temp.getRightChild();
}
}
// set the new node's parent to be the parentNode object that was set in the loop
node.setParent(parentNode);
if(node.getKey().compareTo(parentNode.getKey()) <= 0) {
parentNode.setLeftChild(node);
} else {
parentNode.setRightChild(node);
}
}
}
// this method is used to delete a node from the Binary Search Tree
public void deleteNode(BSTNode node) {
// check if the node to be deleted is a valid reference, if its an invalid reference then we don't need to do anything at all
if(node == null) {
return;
}
// Case-1 : If the node to be deleted has no child references at all
if(node.getLeftChild() == null && node.getRightChild() == null) {
BSTNode parentNode = node.getParent();
// if the node to be deleted is the root node
if(parentNode == null) {
this.root = null;
} else if (parentNode.getLeftChild() == node) {
parentNode.setLeftChild(null );
} else {
parentNode.setRightChild(null);
}
node.setParent(null);
}
// Case-2 : If the node to be deleted has one node as its child node
if(node.getLeftChild() != null && node.getRightChild() == null) {
BSTNode parentNode = node.getParent();
// if the node to be deleted is the root node and it has a left child then make the left child of the root node as root
if(parentNode == null) {
this.root = node.getLeftChild();
} else {
// if the node to be deleted is the left child of its parent node
if(parentNode.getLeftChild() == node) {
parentNode.setLeftChild(node.getLeftChild());
} else {
parentNode.setRightChild(node.getLeftChild());
}
}
node.getLeftChild().setParent(parentNode);
node.setParent(null);
node.setLeftChild(null);
}
if(node.getLeftChild() == null && node.getRightChild() != null) {
BSTNode parentNode = node.getParent();
// if the node to be deleted is the root node and it has a right child
if(parentNode == null) {
this.root = node.getRightChild();
} else {
// if the node to be deleted is the left child of its parent node
if(parentNode.getLeftChild() == node) {
parentNode.setLeftChild(node.getRightChild());
} else {
parentNode.setRightChild(node.getRightChild());
}
}
node.getRightChild().setParent(parentNode);
node.setParent(null);
node.setRightChild(null);
}
// Case-3 : if the node to be deleted has both a left and a right child
if(node.getLeftChild() != null && node.getRightChild() != null) {
BSTNode parentNode = node.getParent();
// first we get the successor of the node in the Binary Search Tree
BSTNode successorNode = getSuccessor(node.getKey());
BSTNode successorParent = successorNode.getParent();
BSTNode successorRightChild = successorNode.getRightChild();
// if the successor node doesn't have any right child, it obviously doesn't have any left child as its the successor node
if(successorRightChild == null) {
node.setKey(successorNode.getKey());
if(successorParent.getRightChild() == successorNode) {
successorParent.setRightChild(null);
} else {
successorParent.setLeftChild(null);
}
return;
} else {
node.setKey(successorNode.getKey());
if(successorParent.getRightChild() == successorNode) {
successorParent.setRightChild(successorRightChild);
} else {
successorParent.setLeftChild(successorRightChild);
}
}
successorRightChild.setParent(successorParent);
successorNode.setParent(null);
successorNode.setLeftChild(null);
successorNode.setRightChild(null);
}
}
}
public class BinarySearchTree {
public static void main(String[] args) {
BSTree tree = new BSTree();
tree.insertNode("D");
tree.insertNode("B");
tree.insertNode("C");
tree.insertNode("A");
tree.insertNode("F");
tree.insertNode("G");
// tree.insertNode("E");
tree.insertNode("I");
tree.insertNode("H");
tree.insertNode("J");
tree.insertNode("L");
tree.insertNode("K");
System.out.println("Inorder Tree Walk : ");
tree.inorderTreeWalk(tree.getRoot());
System.out.println();
System.out.println("Preorder Tree Walk : ");
tree.preorderTreeWalk(tree.getRoot());
System.out.println();
System.out.println("Postorder Tree Walk : ");
tree.postorderTreeWalk(tree.getRoot());
System.out.println();
System.out.println("Node with the minimum key in the Binary Search Tree : " + tree.findMinimum().getKey());
System.out.println("Node with the maximum key in the Binary Search Tree : " + tree.findMaximum().getKey());
tree.deleteNode(tree.searchNode("D"));
System.out.println("Inorder Tree Walk after deletion of node D : ");
tree.inorderTreeWalk(tree.getRoot());
System.out.println();
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.