In Java: Implement public void balance(). Read the bolded rules carefully. Will write good review and thumbs up. Thanks!

Here is the code provided for the class:

import java.util.Arrays; public class BSTree> { private static class Node> { public T data; public Node left, right;

public Node(Node left, T data, Node right) { this.left = left; this.data = data; this.right = right; }

public boolean contains(T d) { int comp = d.compareTo(data); if (comp == 0) return true; // Already in tree if (comp

} public int size() { // We know there is a node here int total = 1; // This node may have left children if (left != null) total = total + left.size(); // This node may have right children if (right != null) total = total + right.size(); // The total size of the tree from this point... return total; } public Node delete(T d) { int comp = d.compareTo(data); if (comp == 0) return deleteNode(); if (comp

private Node root;

public BSTree() { root = null; }

/** * Adds data to the tree if it didn't already contain it. * * @param data */

public boolean contains(T data) { if (root == null) return false; return root.contains(data); } public int size() { if (root == null) return 0; return root.size(); } public void delete(T data) { if (root == null) return; root = root.delete(data); } public T findRightmostLowest() { // TODO: Implement. return null; } }

4. EXTRA CREDIT 5 POINTS: Implement public void balance() Use a findByOrder-based approach to rebalance the tree using a pivot-style approach. The new root should be the tree's median (ordered index of size()/2). Recursively, the root of each branch should be the median of each branch (index within that subtree of its size / 2). This method should execute in O(n log n) time to receive full credit. 4. EXTRA CREDIT 5 POINTS: Implement public void balance() Use a findByOrder-based approach to rebalance the tree using a pivot-style approach. The new root should be the tree's median (ordered index of size()/2). Recursively, the root of each branch should be the median of each branch (index within that subtree of its size / 2). This method should execute in O(n log n) time to receive full credit