AVL Árbol de equilibrio

Question

Estoy trabajando en una tarea que me pregunta para implementar un árbol AVL. Estoy bastante seguro de que tengo los métodos de rotación correcta, pero estoy teniendo problemas para averiguar cuándo usarlos.

Por ejemplo, la explicación en el libro dice que yo debería subir hasta el mismo camino que fui a insertar el / elemento de nodo. Sin embargo, no puedo tener ningún Consejos para los Padres.

Últimas código:

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

Lo que quiero hacer aquí es volver a subir al árbol, pero sólo puede comprobar el equilibrio después se inserta el nodo. Por lo tanto, siendo esta en la cláusula más.

También intentado poner el código de equilibrio en el que R Samuel Klatchko sugirió, pero comprobado el saldo de cada inserto. Por ejemplo: si uno inserciones 7, 9, 5, 3 y 1 consecutivamente, consigo una excepción de puntero nulo cuando se trata de insertar 1

.

EDIT: Una razón de lo anterior puede tener algo que ver con la forma en que estaba haciendo la altura. Funciona bien con una sola rotación derecha si puedo calcular la altura cada vez que con la altura (), sino que rompe el tiempo O (log (n)) de un árbol AVL.

¿Alguna idea sobre cómo lograr esto?

Answer 1

código está subiendo por el mismo camino que bajes. Considere este código:

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

y modificarlo ligeramente:

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

Como el código devuelve a las llamadas recursivas, cada retorno le trae de vuelta a los padres. Al no regresar inmediatamente el valor de la llamada recursiva, usted tiene la oportunidad de hacer su reequilibrio.

Actualización para el último código

No se olvide de volver a equilibrar cuando se ha insertado a la derecha.

Answer 2

Usted puede tratar de pasar el puntero del padre en el método insert, o se puede convertir en insert un método iterativo y mantener una pila explícita sobre el que se graba el camino por el árbol.

Por cierto, con el fin de elegir la rotación de usar, sólo puede saber que un nodo está desequilibrado, hay que saber si el subárbol más profundo está a la derecha oa la izquierda. Esto significa que su método isBalanced simple no es suficiente. También es ineficiente, y soplará O del árbol AVL (log n) complejidad, debido a calcular las alturas cada vez.