Programming Language : Racket Objective: Implement a Standard Binary Search Tree
ID: 3816769 • Letter: P
Question
Programming Language: Racket
Objective: Implement a Standard Binary Search Tree which include the following functions:
.
.
.
AT THE MINIMUM, IMPLEMENT ADD AND SEARCH TO THE BINARY SEARCH TREE:
1.) (constructBST)
constructs empty BST
2.) (addToBST BST key value)
Adds a key-value pair to a BST, where key is an integer and value is a string, integer, list, etc...
3.) (searchBST BST key)
Searches for a value based on key. Return key if value is not found for the key. Return key and value if value is found for the key.
.
.
.
IMPLEMENT THESE IF YOU ARE CAPABLE OF DOING SO:
4.) (mapBST BST someFunction)
Maps a BST to a new BST with modified values.The values should be modified by an arbitrary function someFunction
Map means is that you apply the function to all the nodes in the tree
mapBST should leave the input BST as is, and create a new BST with the same "treeshape" and same keys, but with different value in each node (based on someFunction)
For example: if there's a tree with root node 2, and children 1 and 3 and I call map with the function addOne, it becomes one with root 2, children 3 4
5.) (foldBST BST someFunction)
Folding a BST to a single fold-value
Based on traversal of the tree from leaves to root
The returned fold-value should be produced by user-provided someFunction based on key/value of current node a fold-values return from left and right children
.
.
.
It's okay to submit partially completed BST, although a fully functional BST is much appreciated.
NOTE: BST = Binary Search Tree, Implement add and search functions at the minimum for the binary search tree
Explanation / Answer
Binary Search Tree Implementations:
public class BST {
public static Node roots;
public BST(){
this.roots = null;
}
// find the elements
public boolean find(int id){
Node current = roots;
while(current!=null){
if(current.bData==id){
return true;
}else if(current.bData>id){
current = current.bLeft;
}else{
current = current.bRight;
}
}
return false;
}
//delete the elemenets
public boolean delete(int id){
Node parent = roots;
Node current = roots;
boolean isLeftChild = false;
while(current.bData!=id){
parent = current;
if(current.bData>id){
isLeftChild = true;
current = current.bLeft;
}else{
isLeftChild = false;
current = current.bRight;
}
if(current ==null){
return false;
}
}
//if i am here that means we have found the node
//Case 1: if node to be deleted has no children
if(current.bLeft==null && current.bRight==null){
if(current==roots){
roots = null;
}
if(isLeftChild ==true){
parent.bLeft = null;
}else{
parent.bRight = null;
}
}
//Case 2 : if node to be deleted has only one child
else if(current.bRight==null){
if(current==roots){
roots = current.bLeft;
}else if(isLeftChild){
parent.bLeft = current.bLeft;
}else{
parent.bRight = current.bLeft;
}
}
else if(current.bLeft==null){
if(current==roots){
roots = current.bRight;
}else if(isLeftChild){
parent.bLeft = current.bRight;
}else{
parent.bRight = current.bRight;
}
}else if(current.bLeft!=null && current.bRight!=null){
//now we have found the minimum element in the right sub tree
Node successor = getSuccessor(current);
if(current==roots){
roots = successor;
}else if(isLeftChild){
parent.bLeft = successor;
}else{
parent.bRight = successor;
}
successor.bLeft = current.bLeft;
}
return true;
}
public Node getSuccessor(Node deleleNode){
Node successsor =null;
Node successsorParent =null;
Node current = deleleNode.bRight;
while(current!=null){
successsorParent = successsor;
successsor = current;
current = current.bLeft;
}
//check if successor has the right child, it cannot have left child for sure
// if it does have the right child, add it to the left of successorParent.
// successsorParent
if(successsor!=deleleNode.bRight){
successsorParent.bLeft = successsor.bRight;
successsor.bRight = deleleNode.bRight;
}
return successsor;
}
public void insert(int id){
Node newNode = new Node(id);
if(roots==null){
roots = newNode;
return;
}
Node current = roots;
Node parent = null;
while(true){
parent = current;
if(id<current.bData){
current = current.bLeft;
if(current==null){
parent.bLeft = newNode;
return;
}
}else{
current = current.bRight;
if(current==null){
parent.bRight = newNode;
return;
}
}
}
}
public void display(Node root){
if(root!=null){
display(root.bLeft);
System.out.print(" " + root.bData);
display(root.bRight);
}
}
public static void main(String arg[]){
BST b = new BST();
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.roots);
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(roots);
System.out.println(" Delete Node with one child (4) : " + b.delete(4));
b.display(roots);
System.out.println(" Delete Node with Two children (10) : " + b.delete(10));
b.display(roots);
}
}
class Node{
int bData;
Node bLeft;
Node bRight;
public Node(int bData){
this.bData = bData;
bLeft = null;
bRight = null;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.