The following is to be written in Java The following is the

The following is to be written in Java:

The following is the BSTree.java I have written. Use this code and extend it to achieve the problems listed above:

import java.io.*;
import java.util.*;

class BSTNode {
BSTNode left, right;
Comparable data;

public BSTNode(){
left = null;
right = null;
data = 0;
}
/* Constructor */
public BSTNode(Comparable n){
left = null;
right = null;
data = n;
}
public void setLeft(BSTNode n){
left = n;
}
public void setRight(BSTNode n){
right = n;
}
public BSTNode getLeft(){
return left;
}
public BSTNode getRight(){
return right;
}
public void setData(int d){
data = d;
}
public Comparable getData(){
return data;
}
}
class BST {
private BSTNode root;

/* Constructor */
public BST(){
root = null;
}
/* Functions to insert data */
public void insert(Comparable data){
if (root == null){
root = new BSTNode(data);
}
else insert(root, data);
}
/* Function to insert data recursively */
private void insert(BSTNode node, Comparable data){
//if (node.getData().equals(data)) thr();
if (data.compareTo(node.getData()) < 0){
//when data < node\'s data
//add data as left child of node if it doesnt have one
//else insert into node\'s left subtree
if (node.getLeft() == null) node.setLeft(new BSTNode(data));
else insert(node.getLeft(), data);
} else {
//when data > node\'s data
//insert data as right child of node if it doesnt have one
//else insert into node\'s right subtree
if (node.getRight() == null) node.setRight(new BSTNode(data));
else insert(node.getRight(), data);
}
}
public boolean search(Comparable data) {
return search(root, data);
}

private static boolean search(BSTNode node, Comparable data) {
if (node == null) return false;
if (node.getData().equals(data)) return true;
if (data.compareTo(node.getData()) < 0) {
// data < this node\'s key; look in left subtree
    return search(node.getLeft(), data);
}
else {
// data > this node\'s key; look in right subtree
    return search(node.getRight(), data);
}
}

/* Function for inorder traversal */
public void inorder(){
inorder(root);
}
private void inorder(BSTNode r){
if (r != null){
inorder(r.getLeft());
System.out.print(r.getData() +\" \");
inorder(r.getRight());
}
}
}

public class BSTree {
public static void main(String[] args) {
BST bst = new BST();
int[] x = {4,2,6,1,3,5,7,8,12,15,10,13,14,9};
for(int i=0;i<x.length;i++){
bst.insert(x[i]);
}
bst.inorder();
System.out.println(\"\");
System.out.println(\"Does the BST include 8? \" + bst.search(8));
   System.out.println(\"Does the BST include 3? \" + bst.search(3));
}
}

Solution

REDBLACK.java

/*

-------------------------------------------------------------------------------------------------------------------------------------------------------------------

RBBST.java