java - 如何在二叉搜索树中实现重新平衡？

Question

我已经为二叉搜索树添加了以下方法:

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

}

}

如何使用已有的结构完成重新平衡方法？我想通过查找中点并递归地对它们进行排序来使用排序的数组列表。我不确定如何使用我设置树的方式(使用内部节点类)来实现这一点，因此我需要有关此代码的一些帮助。

Answer 1

将数组分成两个大小相等的部分。取中间元素作为新的根节点。然后再次分割两部分，取中间元素作为二级节点，以此类推。最好递归实现......