Please don't spam or give a incomplete answer, if you can't help me out with this question Please don't answer it. Thank you

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. 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.

2. isHeightBalanced - this will return 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.

3. join - this will join two BSTs into a single BST. This will be described in below in detail.

6

4 11

2 5 7 12

1 3 9

8 10

Figure 1: This tree is not height-balanced

6

4 11

2 5 7 12

1 3

Figure 2: This tree is height-balanced

Height balancing

Suppose that height(v) returns the height of BST rooted at node v. Recall the that height of a (sub)tree rooted at a node v is the maximum number of edges from v to any leaf node. Recall also that the height of an empty tree is -1 and height of a tree with one node is 0. Consider the following tree.

A BST is height-balanced if for each node u in the BST, |height(u.left) - height(u.right) | 1, where u.left is the left subtree of u and u.right is the right subtree of u. The rebalance method will take the current BST and rebalance it so it is height-balanced.

Consider the BST given in Figure 1. This tree is not height-balanced. If you look at the node 7, its left subtree (which is empty) has height -1, while it right subtree has height 2. Another node that shows that this tree is not height-balanced is node 11. On the other hand, the BST given in Figure 2 is height-balanced.

The algorithm to rebalance a BST so that it is height-balanced can be done using the two steps as follows:

Step 1: You need to listify the BST. That is, turn the current BST into one in which each non-leaf node has only a right child (and no left child). This BST will look like a long linked-list. To achieve this, do the following:

1. Recursively listify the left child of the root (if there is a left child),

2. Recursively listify the right child of the root (if there is a right child),

3. Link the root onto the bottom end of the listified left child and then link the listified right child as the right child of the old root.

Note that the new root of this tree will be the root of the listified left child. Note that the term root in the above description of the algorithm refers to the root of the subtree in

question. The base case could be that a tree consisting of one node which is alreadyy listified. The recursive part should return a reference to the root of the listified tree that it constructs.

In your BST class, you should implement a public driver method listify along with a recursive private helper method with the same name that does the actual work of listifying a BST.

If you listified the BST given in Figure 1, the resulting listified BST is given by Figure 3

1

2

3

4

5

6

7

8

9

10

11

12

Figure 3: Listified BST of the BST given in Figure 1

Step 2: You need to height balance the listified BST. That is, you need to take the listified BST from step 1 and manipulate it so that the resulting BST is height-balanced. To achieve this, do the following:

1. Find the middle value of the tree the value that is in the middle of the sorted order of the values stored in the tree. The node containing the middle value will be the root of the resulting height-balanced tree.

2. Split the listified tree into three disjoint pieces:

(a) The list of nodes containing values less than the middle value.

(b) The node containing the middle value - This node will be the root of the resulting height-balanced tree.

(c) The list of nodes containing values greater than the middle value.

6

3 9

1 4 7 11

2 5 8 10 12

Figure 4: Height-balanced BST of the listified BST given in Figure 3

3. Recursively height balance the nodes whose values are less than the middle value, and make it the left child of the node containing the middle value.

4. Recursively height-balance the nodes whose values are greater than the middle value, and make it the right child of the node containing the middle value.

For the base case, you could used the fact that a single node is already height-balanced, and a two-node tree is also height-balanced. Make sure that left and/or right references are set to null where appropriate. The recursive part should return a reference to the root of the height-balanced tree that it constructs.

In your BST class, you should implement a public driver method heightBalance along with a recursive private helper method with the same name that does the actual work of height-balancing the listified BST from step 1.

Figure 4 is the result of height-balancing the listified BST given in Figure 3. Depending on how you define the middle value (using floor or ceiling when dividing the number of nodes by 2), you could get a slightly different (yet still height-balanced) BST.

Important: In these two steps, you are not allowed to create or destroy nodes. If you break this rule, you will be heavily penalized. The nodes in the tree should merely be moved around and relinked. Do not change the data value stored (that is, the value stored in variable key) in a node. Furthermore, to do this operation, it is helpful to know the number of nodes in a given subtree of the BST you are working with. You could either do a traversal of the tree to count the number of nodes before beginning it, or you could store the number of nodes in the tree as part of the tree class (any insertion or deletion routines would, of course, have to correctly update the number of nodes).

Join

The join operation is to take two BSTs, join them into one height-balance BST. To implement the join operation you will make use of the operations above. Since this is an instance method of the BST class, one of the input trees, which well denote by T1, is implicit. The other tree, which well call T2, will be passed in as an argument to your join method. There are two scenario/cases to consider.

Easy Case: Suppose the maximum value in one tree is less than the minimum value in the other tree. If the maximum value in T1 the minimum value in T2. Then make the root of T2 the right child of the node in T1 containing the largest element. Otherwise, if the maximum value in T2 the minimum value in T1. Then make the (current) root of T1 the right child of the node in T2 containing the largest element, and set the root of T1 to be the root of T2. The node containing the minimum and maximum values can be obtained using the methods that you have already implemented above. Then you should call heightBalance to height-balance your the BST T1. Figure 5 shows an example of a join (before height balancing). Then to height-balance the BST T1.You should make T2 the empty tree (by setting its root variable to null) before returning. Note that in this case, you should not create or destroy any nodes. Your joined tree should be constructing simply by relinking the existing nodes.

2

1 3

4

T1

9

8 10

T2

2

1 3

4

9

8 10

T1.join(T2)

Figure 5: Joining two BSTs-easy case

7

1 12

15

T1

9

8 10

T2

7

1 12

15

8

9

10

T1.join(T2)

Figure 6: Joining two BSTs : harder case

Harder Case: In this case, there is no nice separation of the values in the two trees. Some of the values of one tree fall between the smallest and largest values in the other tree. In this case, repeatedly remove a node of minimum value from T2 (using the deleteMin operation you have implemented already) and insert it into the implicit BST (T1). Then you should call heightBalance to height-balance your the BST T1. Figure 6 illustrates the result of joining two trees (but before height balancing). In this example, you would remove node 8 from T2, insert it to T1, remove node 9, insert it to T1 and finally remove node 10, insert it to T1. In this case, you are allowed to create new nodes when doing an insertion (if you are using the existing insert method to insert into the BST).

Your Main Class

You should create a file called A3.java that will contain the main method along with a modified BST class that will contain your implemention of the methods required. You can copy contents of BST.java into this java file (but make sure the class is NOT declared public). In your main method you will prompt the user for a filename that contains the input data, which consists of two (2) trees.

Each tree in the file will begin with the number of values in the tree, followed by that number of values, which should be inserted one by one into an empty tree. For example,

4

7

1

12

15

represents the tree T1 in Figure 6.

A complete input file may look like:

4

7

1

12

15

3

9

8

10

representing the trees T1, T2 respectively in Figure 6. You may always assume that the input is correct and that both trees in the input file are non-empty.

After you have read in the two trees and created two BST objects (say T1, T2) from the input, you should:

1. print the first tree (T1) using an inorder traversal.

2. print the height of the tree.

3. print whether the tree is height-balanced or not.

4. print the second tree (T2) using an inorder traversal.

5. print the height of the tree.

6. print whether the tree is height-balanced or not.

7. perform the join operation T1.join(T2).

8. print the tree T1 using an inorder traversal.

9. print the height of the tree.

10. print whether the tree is height-balanced or not. sample output (for the sample data file above):

Input filename is: a4test1.txt

1 7 12 15

height is: 2

Tree is height-balanced.

8 9 10

height is: 1

Tree is height-balanced.

1 7 8 9 10 12 15

height is: 2

Tree is height-balanced.

End of Processing.

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.key)

curr = curr.left;

else

curr = curr.right;

}

if (val < prev.key)

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.key )

prev.left = newNode;

else

prev.right = newNode;

} //recursive case

else {

if (val < curr.key)

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.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 < curr.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.key)

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);

}

}

}

Sample text file:

4 7 1 12 15 3 9 8 10