如何在二叉搜索樹中實現重新平衡？

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

將該陣列拆分成兩個相同大小的部分。以中間元素作爲新的根節點。 然後再分開兩個部分，並採取中間元素作爲第二級節點，等 最好實現遞歸....