Question: BST.JAVA //sample implementation of a BST class BST { Node root; //reference to root of the binary search tree public BST() { root = null;
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);
}
}
}
201: manitoba.desire2learn.com/content/enforced3/266657-50140.201810/Assignments/a4/a4-comp2140-2018.pdf Objective The objective of this assignment is to height-belance 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 termplate (see BST-java) you are to implement some new operations (that is, instance methods of the BST class) for the BST class 1. nin - this returns a reference to the Node in the BST that contains the smallest key. This method will 2. nax- this returns a reference to the Node in the BST that contains the snallest 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. not have any parameters. not have any parameters node. This method will not have any parameters. 5. heightBalance this will "rebalance the BST so that it is height balanced. This will be described below in detail. This method will not have any parameters isHeightBalanced this will retur a boolean stating whether the BST is height balanced or not. 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. 6. 7. join- this will join two BSTs into a single BST. This will he deseribed in below in detail
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help