Nicht in der Lage, einen binären Baum zu balancieren

Question

Ich bin neu in Algorithmen und ich lerne binäre Bäume und wie man sie balanciert. Das Problem, mit dem ich konfrontiert bin, ist, dass ich selbst nach dem Ausbalancieren des Binärbaums die Höhe des Baumes wie zuvor erhalten habe. Meiner Meinung nach ändert sich nach dem Ausbalancieren (das Raum zum Balancieren hat) ein binärer Baum die Höhe des Baumes. Im Anschluss ist mein Code: -

class Node 
{ 
    Node left; 
    Node right; 
    int info; 
    public Node(int info) 
    { 
     this.info = info; 
    } 
} 
public class NewBST 
{ 
    public Node root; 

    public NewBST() 
    { } 
    // ADD 
    public boolean add(int info){ 
     if(root == null) 
     { 
     root = new Node(info); 
     return true; 
     } 
     else 
     return addRec(info, root); 
    } 
    public boolean addRec(int info, Node n) 
    { 
     if(info <= n.info) 
     { 
     if(n.left == null) 
     { 
      n.left = new Node(info); 
      return true; 
     } 
     else 
     { 
      return addRec(info, n.left); 
     } 
     } 
     if(info > n.info) 
     { 
     if(n.right == null) 
     { 
      n.right = new Node(info); 
      return true; 
     } 
     else 
     { 
      return addRec(info, n.right); 
     } 
     } 
     return true; 
    } 
    // CONTAINS 
    public boolean contains(int v) 
    { 
     return contains(v, root); 
    } 
    public boolean contains(int v, Node n) 
    { 
     if(n== null){ 
     return false; 
     } 
     else if(v == n.info){ 
     return true; 
     } 
     else if(v <n.info){ 
     return contains(v,n.left); 
     } 
     else{ 
     return contains(v, n.right); 
     } 
     //return true; 
    } 
// MIN 
    public int min(Node n) 
    { 
     if(n.left != null) 
     return min(n.left); 
     return n.info; 
    } 

    //HEIGHT 
    public int height(Node n) 
    { 
     //fix this code! 
     if(n==null){ 
     return 0; 
     } 
     return 1+ Math.max(height(n.left), height(n.right)); 
    } 
    public int height() 
    { 
     return height(root); 
    } 

    // DISPLAY 
    public void display(int n){ 
     if(n == 0) 
     { 
     infix(root); 
     System.out.println(); 
     } 
     else if(n == 1) 
     { 
     postfix(root); 
     System.out.println(); 
     } 
     else if(n == 2) 
     { 
     prefix(root); 
     System.out.println(); 
     } 
    } 
    // TRAVERSE 
    public void prefix(Node n) 
    { 
    if(n!=null) 
     System.out.print(n.info +" "); 
     prefix(n.left); 
     prefix(n.right); 
    } 

    public void postfix(Node n) 
    { 
    if(n!=null){ 
     postfix(n.left); 
     postfix(n.right); 
     System.out.print(n.info + " "); 
    } 
    } 

    public void infix(Node n) 
    { 
    if(n!=null){ 
     infix(n.left); 
     System.out.print(n.info + " "); 
      infix(n.right); 
    } 
    } 


    public void infix(Node n, ArrayList<Integer> list) 
    { 
    if(n!=null){ 
     infix(n.left,list); 
     list.add(n.info); 
     infix(n.right,list); 
    } 
    } 
//BALANCE 
    public void balance() 
    { 
    ArrayList<Integer> list= new ArrayList<Integer>(); 
    NewBST bst= new NewBST(); 
    infix(root, list); 

    balRec(list, 0, list.size()-1,bst); 

    } 

    public void balRec(ArrayList<Integer> list, int low, int high,NewBST bst){ 
     if(high<low){ 
     return; 
     } 
    int mid= (low + high)/2; 
    bst.add(list.get(mid)); 
    balRec(list, low, mid-1,bst); 
    balRec(list,mid+1, high,bst); 
    } 

    //MAIN 
    public static void main(String[] args) 
    { 
     Scanner inp = new Scanner(System.in); 
     ArrayList<Integer> store = new ArrayList<Integer>(); 
     NewBST bst = new NewBST(); 
     int nCount = 0; 
     while(nCount < 32) 
     { 
     int t = (int)(Math.random() * 36); 
     if(!bst.contains(t)) 
     { 
      bst.add(t); 
      store.add(t); 
      nCount++; 
     } 
     } 
     System.out.print("Height of tree = " + bst.height()); 
     bst.balance(); 
     System.out.println(); 
     System.out.println("Height of tree = " + bst.height()); 
     bst.display(0); 

    } 
} 

Ich bin nicht sicher, ob der Code selbst ist mein Binärbaum richtig balanciert. Ich habe Stunden damit verbracht, das zu debuggen, und ich war nicht in der Lage, eine Lösung zu finden. Jede Hilfe wird sehr geschätzt.

Danke,

Answer 1

Zuerst lassen Sie mich zum Auswuchten eines binären Suchbaum, der eine in der Höhe Schema erklären. Ein höhenbalancierter binärer Baum ist als ein binärer Baum definiert, in dem der Unterschied zwischen der Höhe der zwei Unterbäume (links und rechts) nie mehr als eins ist.

Ihr Problem ist, dass Sie die gleiche Höhe erhalten, auch nachdem Sie den Baum ausgeglichen haben. Ich sehe einen kleinen Fehler in Ihrem Code. Nach dem Abgleich müssen Sie dem Wurzelknoten den neuen Wert zuweisen. Dies ist notwendig, um die Höhe eines ausgeglichenen Binärbaums zu berechnen. Also, fügen Sie folgende zu Ihrem Balance-Methode Code:

public void balance(){ 
    ArrayList<Integer> list= new ArrayList<Integer>(); 
    NewBST bst= new NewBST(); 
    infix(root, list); 

    balRec(list, 0, list.size()-1,bst); 
    root= bst.root;  
} 

Ich hoffe, dies hilft.