How to implement a rebalance in binary search tree?

Question

I have already put in the following methods for a binary search tree:

import java.util.Collections;
import java.util.NoSuchElementException;
import java.util.ArrayList;

public class MyTree {

        private class Node
        {
            public String data;
            public int data2;
            public Node left;
            public Node right;
            public Node(String data, Node left, Node right)
            {
                this.data = data;
                this.left = left;
                this.right = right;
            }
        }

private static Node root = null;

private int getHeight(Node subroot)
{
    if (subroot == null)
        return -1;
    int maxLeft = getHeight(subroot.left);
    int maxRight = getHeight(subroot.right);
    return Math.max(maxLeft, maxRight) + 1;
}

public String toString()
{
    return toString(this.root);
}

private String toString(Node subroot)
{
    if (subroot==null)
        return "";
    return toString(subroot.left)+subroot.data+toString(subroot.right);
}

public boolean containsRecursive(String value)
{
    return contains(value, this.root);
}

private boolean contains(String value, Node subroot)
{
    if (subroot==null)
        return false;
    else if (value.equals(subroot.data))
        return true;
    else if (value.compareTo(subroot.data) < 0)
        return contains(value, subroot.left);
    else
        return contains(value, subroot.right);
}

public boolean contains(String value) // not recursive
{
    Node subroot = this.root;
    while (subroot != null)
    {
        if (value.equals(subroot.data))
            return true;
        else if (value.compareTo(subroot.data) < 0)
            subroot = subroot.left;
        else
            subroot = subroot.right;
    }
    return false;
}

public int addUp()
{
    return addUp(this.root);
}

private int addUp(Node subroot)
{
    if (subroot==null)
        return 0;
    return addUp(subroot.left)+subroot.data2+addUp(subroot.right);
} //data = String, data2 = int

public int count()
{
    return count(this.root);
}

private int count(Node subroot)
{
    if (subroot==null)
        return 0;
    return count(subroot.left)+1+count(subroot.right);
}

public int numberLess(int x)
{
    return numberLess(this.root, x);
}

private int numberLess(Node subroot, int x)
{
    if (subroot==null)
        return 0;
    if (x < subroot.data2)
        return numberLess(subroot.left, x)+1+numberLess(subroot.right, x);
    return numberLess(subroot.left, x)+numberLess(subroot.right, x);
}

public int findMax()
{
    return findMax(this.root);
}

private int findMax(Node subroot) throws NoSuchElementException
{
    if (subroot==null)
        throw new NoSuchElementException();
    return Math.max(findMax(subroot.left), findMax(subroot.right));
}

private ArrayList<Integer> addToList(Node subroot, ArrayList<Integer> a)
{
    if (subroot!=null){
    a.add(subroot.data2);
    addToList(subroot.left, a).addAll(addToList(subroot.right, a));
    return a;
    }
    return new ArrayList<Integer>();
}

private ArrayList<Integer> getSortedList(){
    ArrayList<Integer> rawList = addToList(this.root, new ArrayList<Integer>());
    Collections.sort(rawList);
    return rawList;
}

public void rebalance(){
    ArrayList<Integer> list = getSortedList();

}

}

How can I finish the rebalance method using the structure I already have? I'd like to use the sorted arraylist by finding the midpoints and recursively ordering them. I'm not sure how this would be approached using the way I have my tree set up (with the internal node class) so I'd like some help with this code.

Answer 1

Split the array in two equal sized portions. Take the median element as new root node. Then split again the two portions and take the median element as second level nodes, etc. Best implemented recursively....