Java - ein Binary Tree Guthaben bei der "Brute Force"

Question

Ich versuche, eine Methode in Java zu schreiben, die einen binären Baum balanciert, wie folgt beschrieben:

... eine Inorder Traversal des Baumes schreiben an ein Array und verwenden Sie dann eine rekursive Methode (ähnlich wie bei der binären Suche), um das mittlere Element des Arrays als Root einzufügen und dann symmetrische linke und rechte Teilbäume zu erstellen.

Allerdings bin ich ratlos, wie das alles zusammen zu tun ist. Ich habe bisher verschiedene Ansätze ausprobiert, aber nichts hat funktioniert.

Ich habe auch bereits einen InOrder-Iterator, der eine ArrayList aller Elemente in der Struktur zurückgibt, so dass dies abgedeckt ist.

Dies ist, was ich zur Zeit bauen weg von:

public void rebalance() 
{ 
    Iterator<T> it = iteratorInOrder(); 
    List<T> list = new ArrayList<>(); 

    while (it.hasNext()) 
    { 
     list.add(it.next()); 
    } 
    balanceRecursive(); 
} 

private void balanceRecursive() 
{ 
    //something here 
} 

und dann das ich einfach am Ende des Add haben/entfernen Methoden Element:

if ((getHeight() - getMinHeight()) > 5) 
      rebalance(); 

Also, wie könnte Ich gehe darüber?

Answer 1

Sobald Sie die List von In-Order-Traversal haben, wird dies relativ einfach. die sublist Betrieb bedeutet, dass Sie Indizes nicht einmal brauchen um weitergeben müssen:

Node<T> buildBalancedTree(List<T> values) { 
    if (values.isEmpty()) { 
     return Node.NULL; 
    } else { 
     int middle = values.size()/2; 
     Node node = new Node(values.get(middle)); 
     node.setLeft(buildBalancedTree(values.subList(0, middle))); 
     node.setRight(buildBalancedTree(values.subList(middle + 1, values.size()))); 
     return node; 
    } 
} 

ich Sie unter der Annahme einer Node.NULL müssen leere Unterbäume nicht ‚null‘ darstellen, weil Sie sollten :-)

So wird Ihre Neubalance-Methode etwa wie folgt aussehen:

root = buildBalancedTree(root.getListOfValuesInOrder()); 

Answer 2

In einem symmetrischen Baum sollten sich der rechte und der linke Teilbaum um höchstens 1 Elementgröße unterscheiden. Bei einem sortierten Array - wie es von Ihrem Inorder-Traversal erzeugt wird - wird dies ziemlich einfach. Die Grundidee wäre, einen tatsächlichen Baum zu bauen, der demjenigen entspricht, der implizit von einer binären Suche durchlaufen wird. Beginnen Sie mit dem mittleren Element des Arrays als root, das mittlere Element des Subarrays links von der Mitte wird zum linken Kind, das gleiche Muster für das rechte Kind. Erstellen Sie die Teilbäume mit dem linken Kind als root entsprechend mit der linken Hälfte des Arrays, das gleiche für den rechten Teilbaum.

//lower and upper are the INCLUSIVE bounds of the sublist, from which the tree should be built 
Node<T> buildRecursively(int lower , int upper , List<T> elements){ 
    //no more nodes can be produced on this path 
    if(lower > upper) 
     return null; 

    //build node from the middle-element of the elements 
    int middle = (lower + upper)/2; 
    Node<T> result = new Node<>(elements.get(middle)); 

    //build left and right child for the according pieces of the array/list 
    result.setLeftChild(buildRecursively(lower , middle - 1 , elements); 
    result.setRightChild(buildRecursively(middle + 1 , upper , elements); 

    return result; 
} 

//build entire tree: 
Node<T> root = buildRecursively(0 , elements.size() - 1 , elements); 

Mit einem tatsächlichen Array dies würde wie folgt aussehen:

   sorted ascending---------> 
         4 
       2    6 
      1  3   5  7 
indices:  0 1 2  3 4 5 6 

Answer 3

1. Bauen Sie einen Knoten mit dem mittleren Feldelement als Wert.
2. Wenden Sie (rekursiv) (1) auf den linken Teil des Arrays an, und legen Sie den so konstruierten Knoten als linkes untergeordnetes Element des Stammknotens fest.
3. Wenden Sie (1) auf den rechten Teil des Arrays rekursiv an, und legen Sie den so konstruierten Knoten als das rechte Kind des Stammknotens fest.