AVL albero di bilanciamento

Question

Sto lavorando su un incarico che mi chiede di implementare un albero AVL. Sono abbastanza sicuro di avere i metodi di rotazione corretta, ma sto avendo problemi a capire quando utilizzarle.

Ad esempio, la spiegazione nel libro dice che dovrei salire lo stesso percorso sono andato giù per inserire il nodo / elemento. Tuttavia, non posso avere tutti i puntatori genitore.

Ultimi codice:

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;
}

Quello che voglio fare è risalire l'albero, ma può solo controllare il bilanciamento DOPO inserisce il nodo. Quindi, questo essendo nella clausola else.

Inoltre ho provato a mettere il codice di equilibrio in cui R Samuel Klatchko suggerito, ma controllato il saldo ogni inserto. Ad esempio: Se uno inserti 7, 9, 5, 3, e 1 consecutivamente, ottengo un'eccezione puntatore nullo quando si tenta di inserire 1

.

EDIT: Una ragione di quanto sopra può avere qualcosa a che fare con il modo in cui stavo facendo l'altezza. Funziona bene con una sola rotazione a destra se calcolare l'altezza ogni volta con altezza (), ma che rompe la O (log (n)) di un albero AVL.

Qualche idea su come realizzare questo?

Answer 1

È il codice sta scalando la stessa via si è andato giù. Si consideri questo codice:

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

e modificarlo un po ':

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

Mentre il codice restituisce le chiamate ricorsive, ogni cambio si riporta al genitore. Con non immediatamente restituire il valore della chiamata ricorsiva, si ha la possibilità di fare la vostra riequilibrio.

Aggiornamento per ultimo codice

Non dimenticare di riequilibrare quando hai inserito a destra.

Answer 2

Si potrebbe provare a passare il puntatore del genitore nel metodo insert, oppure è possibile convertire insert in un metodo iterativo e mantenere uno stack esplicito su cui si registra il percorso verso il basso l'albero.

A proposito, al fine di scegliere quale la rotazione da usare, si può solo sapere che un nodo è sbilanciato, è necessario sapere se la sottostruttura più profondo è a destra oa sinistra. Ciò significa che il metodo di isBalanced semplice non è abbastanza. E 'anche inefficiente, e farà saltare O dell'albero AVL (log n) complessità, perché si calcola le altezze di volta in volta.