BST.java

//sample implementation of a BST

class BST {

Node root; //reference to root of the binary search tree

public BST() {

root = null;

}

//iterative insert

public void insert(int val) {

Node newNode,prev,curr;

boolean done = false;

prev = null;

curr = root;

newNode = new Node(val,null,null);

if (root == null) {

root = newNode;

}

else {

while (curr != null) {

prev = curr;

if (val

curr = curr.left;

else

curr = curr.right;

}

if (val

prev.left = newNode;

else

prev.right = newNode;

}

}

//recursive insert public drive method

public void insertR(int val) {

Node newNode;

if (root == null) {

root = new Node(val,null,null);

}

else {

insertR(null,root,val);

}

}

//recursive insert private helper method.

//this method does the actual insertion into a non-empty tree

private void insertR(Node prev, Node curr, int val) {

//prev-reference to previous node being considered.

//curr-reference to current node being considered.

//val - value to insert.

Node newNode;

if (curr == null) { //base case

newNode = new Node(val,null,null);

if (val

prev.left = newNode;

else

prev.right = newNode;

} //recursive case

else {

if (val

insertR(curr,curr.left,val);

else

insertR(curr,curr.right,val);

}

}

//iterative search

public boolean search(int key) {

Node curr=root;

boolean result = false;

while (curr !=null) {

if (curr.key == key) {

result = true;

break;

}

else if (key

curr = curr.left;

else

curr = curr.right;

}

return result;

}

//recursive search

public boolean searchR(int key) { //driver method

return searchR(key,root);

}

//this method does the actual recursive searching.

private boolean searchR(int key, Node curr) {

boolean result = false;

if (curr !=null) {

if (curr.key == key)

result = true;

else if (key

result = searchR(key,curr.left);

else

result = searchR(key,curr.right);

}

return result;

}

//inorder traversal (recursive)

private void inorder(Node curr) {

if (curr != null) {

inorder(curr.left);

curr.print();

inorder(curr.right);

}

}

public void inorder() {

inorder(root);

}

class Node {

int key;

Node left;

Node right;

public Node(int val, Node l, Node r) {

key = val;

left = l;

right = r;

}

public void print() {

System.out.println(key);

}

}

private Node findNode(int val) {

Node curr;

curr = root;

while (curr != null) {

if (curr.key == val)

break;

}

return curr;

}

private void easyDelete(Node delNode, Node delParent, Node delChild) {

//delNode-Node to be deleted

//delParent-parent of delNode

//delChild-child of delNode

if (delParent == null) { //deleting root node

root = delChild;

}

else { //delNode is not root

if (delNode == delParent.left)

delParent.left = delChild;

else

delParent.right = delChild;

}

}

private void twoChildrenDelete(Node curr) {

Node is, isParent; //inorder successor and inorder successor's parent

is = curr.right;

isParent = curr;

while (is.left != null) { //find inorder successor to curr.

isParent = is;

is = is.left;

}

curr.key = is.key; //put inorder sucessor's value into node curr.

easyDelete(is,isParent,is.right); //delete inorder successor node, which has no left child.

}

public void delete(int val) {

Node curr = root;

Node prev = null;

while (curr != null && curr.key != val) {

prev = curr;

if (val

curr = curr.left;

else

curr = curr.right;

}

if (curr != null) { //key found

if (curr.left == null)

easyDelete(curr,prev, curr.right);

else if (curr.right == null)

easyDelete(curr,prev,curr.left);

else

twoChildrenDelete(curr);

}

}

}

Text File (for testing):

4 7 1 12 15 3 9 8 10 

Programming Standards programming standards, a UMLearn. Failure to do so will result in the loss of marks Objective The objective of this assignment is to height-balance a BST and to join two BSTs. Your Program General Overview: In this assignment, your task is to implement some new operations to the Binary Search Tree data structure covered in class and to test the new operations. Details Given the BST class template (see BST.java) you are to implement some new operations (that is, instance methods of the BST class) for the BST class 1. min - this returns a reference to the Node in the BST that contains the smallest key. This method will not have any parameters. not have any parameters. node. This method will not have any parameters. 2. max-this returns a reference to the Node in the BST that contains the smallest key. This method will 3. deleteMin - this will remove the node that contains the smallest key and return a reference to that 4. height this will return the height of the tree. 5. heightBalance this will "rebalance" the BST so that it is height balanced. This will be described 6. isHeightBalanced - this will return a boolean stating whether the BST is height balanced or not below in detail. This method will not have any parameters. This method will return true if the tree is height-balanced, and false if it is not. A definition of height balanced is given in the discussion of the Rebalance operation 7. join- this will join two BSTs into a single BST. This will be described in below in detail. Programming Standards programming standards, a UMLearn. Failure to do so will result in the loss of marks Objective The objective of this assignment is to height-balance a BST and to join two BSTs. Your Program General Overview: In this assignment, your task is to implement some new operations to the Binary Search Tree data structure covered in class and to test the new operations. Details Given the BST class template (see BST.java) you are to implement some new operations (that is, instance methods of the BST class) for the BST class 1. min - this returns a reference to the Node in the BST that contains the smallest key. This method will not have any parameters. not have any parameters. node. This method will not have any parameters. 2. max-this returns a reference to the Node in the BST that contains the smallest key. This method will 3. deleteMin - this will remove the node that contains the smallest key and return a reference to that 4. height this will return the height of the tree. 5. heightBalance this will "rebalance" the BST so that it is height balanced. This will be described 6. isHeightBalanced - this will return a boolean stating whether the BST is height balanced or not below in detail. This method will not have any parameters. This method will return true if the tree is height-balanced, and false if it is not. A definition of height balanced is given in the discussion of the Rebalance operation 7. join- this will join two BSTs into a single BST. This will be described in below in detail