AVL-Baum Balancing

Question

ich an einer Aufgabe arbeite, die mich fragt einen AVL-Baum zu implementieren. Ich bin mir ziemlich sicher, dass ich die Dreh Methoden richtig, aber ich habe Probleme, herauszufinden, wann sie verwenden.

Zum Beispiel sagt die Erklärung in dem Buch, dass ich den gleichen Weg klettern sollte ich den Knoten / Element ging einzufügen. Allerdings kann ich keine Abstammungszeiger haben.

Aktuelle Code:

public BinaryNode<T> insert(BinaryNode<T> node) {
    if (this.getElement().compareTo(node.getElement()) > 0) {
        if (this.getLeftChild() != null) {
            BinaryNode<T> b = this.getLeftChild().insert(node);

            if(!this.isBalanced()) {
                this.balance();
            }

            return b;
        } else {
            this.setLeftChild(node);
        }

    } else if (this.getElement().compareTo(node.getElement()) < 0) {
        if (this.getRightChild() != null) {
            return this.getRightChild().insert(node);
        } else {
            this.setRightChild(node);
        }
    }

    return this;
}

Was will ich hier zu tun ist, auf den Baum klettern zurück, aber es kann nur den Ausgleich überprüfen, nachdem er den Knoten einfügt. Daher sind diese in der else-Klausel zu sein.

Ich habe auch versucht die Balance Code setzen, wo R Samuel Klatchko vorgeschlagen, aber kontrolliert das Gleichgewicht auf jedem Einsatz. Zum Beispiel: Wenn ein 7-Einsätze, 9, 5, 3 und 1 nacheinander, erhalte ich eine Null-Zeiger-Ausnahme bei dem Versuch, 1 einfügen

.

EDIT: Ein Grund für die oben kann etwas mit der Art und Weise zu tun, ich die Höhe tat. Es funktioniert gut mit einer einzigen Rotation nach rechts, wenn ich die Höhe jedes Mal mit der Höhe (), aber das bricht das O (log (n)) Zeit eines AVL-Baum zu berechnen.

Alle Gedanken auf, wie dies zu erreichen?

Answer 1

Sie Code erklimmt den gleichen Weg bis Sie nach unten ging. Betrachten Sie diesen Code ein:

if (this.getLeftChild() != null) {
    return this.getLeftChild().insert(node);
} 

und ändern Sie es leicht:

if (this.getLeftChild() != null) {
    boolean b = this.getLeftChild().insert(node);
    // do something here
    return b;
} 

Wie der Code aus den rekursiven Aufrufen zurückgibt, jede Rückkehr bringt Sie zurück zum übergeordneten. Durch die nicht unmittelbar den Wert des rekursiven Aufruf Rückkehr, haben Sie die Möglichkeit, Ihre Rebalancing zu tun.

Update für die neuesten Code

Vergessen Sie nicht wieder im Gleichgewicht, wenn Sie auf der rechten Seite eingefügt haben.

Answer 2

Sie könnten versuchen, den übergeordneten Zeiger in die insert Methode übergeben, oder könnten Sie insert in einem iterativen Verfahren umwandeln und einen expliziten Stapel halten, auf dem Sie den Weg hinunter den Baum aufzunehmen.

Durch die Art und Weise, um zu entscheiden, welche Rotation zu verwenden, können Sie nur wissen, dass ein Knoten unausgewogen ist, müssen Sie wissen, ob der tiefere Unterbaum auf dem rechten oder auf der linken Seite. Dies bedeutet, dass Ihre einfache isBalanced Methode nicht ganz ausreicht. Es ist auch ineffizient, und die AVL-Baum der O (log n) Komplexität blasen, weil man die Höhen jedes Mal berechnen.