Balancieren einer BST mit Gewichten

Question

Ich baue eine rekursive Java-Methode, um einen binären Suchbaum (mit Ints, aber entworfene generische) mit Gewichten in jedem Knoten zu balancieren. Für meine Zwecke, das Gewicht eines Knotens als die Zahl der Kinder + 1.

2 
/ \ 
1 3 

The weight of the root is 3, and the weight of both leaves is 1. 

Am Ende des Ausgleichs definiert wird, sollte der Wert an einem beliebigen Knoten an allen Knoten in der der Median der Werte Teilbaum, der an diesem Knoten verwurzelt ist.

Hier ist mein Code:

public void weightBalance (BinarySearchTree<AnyType> t) { 

    // Base case 
    if (t.getRoot().left == null && t.getRoot().right == null) { 
     return; 
    } 

    // Get median of tree 
    AnyType median = t.getMedian(); 

    // Create new BST with median as root 
    BinarySearchTree<AnyType> newTree = new BinarySearchTree<AnyType>(); 
    newTree.insert(median); 

    // Insert all values except median into new BST 
    ArrayList<AnyType> stack = new ArrayList<AnyType>(); 
    inorderTraverse(t.getRoot(), stack); 
    Iterator<AnyType> itr = stack.iterator(); 
    while (itr.hasNext()) { 
     AnyType temp = itr.next(); 
     if (temp != median) { // Comparing values or reference? 
      newTree.insert(temp); 
     } 
    } 

    // Replace old BST with new BST 
    t = newTree; // t is a copy of the reference, is this the problem? 

    // Recurse through children 
    // Tree constructor for reference: 
    // public BinarySearchTree (BinaryNode<AnyType> t) { 
    // root = t; 
    // } 

    if (t.getRoot().left != null) { 
     weightBalance(new BinarySearchTree(t.getRoot().left)); 
    } 
    if (t.getRoot().right != null) { 
     weightBalance(new BinarySearchTree(t.getRoot().right)); 
    } 
} 

Ich versuche, den Baum an seinem Platz zu ändern, ohne etwas zurückkehrt, aber der Code nicht den Baum ändern. Ich wissen, Ich bin messing by pass by Referenz übergeben und Weitergabe von Wert, aber ich kann nicht herausfinden, wo - kann jemand helfen? Ich habe ein paar Stunden Debugging verbracht, aber ich werde wirklich verwirrt, wenn ich die Rekursion debugge.

Answer 1

Balancing-Algorithmen sind ziemlich häufig und gut dokumentiert, z. TreeMap ist ein BST und Sie können es als Quelle sehen. Ich habe noch nie gesehen, dass eine Kopie von Daten verwendet wird. Ich bezweifle, dass Sie einen Stapel erstellen oder einen neuen Baum erstellen müssen, nur um ihn auszugleichen.

Das normale Verhalten ist, Knoten, links oder rechts, oder eine komplexere Kombination von beiden zu drehen. Dies reduziert die damit verbundene Arbeit und erzeugt keinen Müll.