AVL arbre d'équilibrage

Question

Je travaille sur une mission qui me demande de mettre en œuvre un arbre AVL. Je suis sûr que j'ai les méthodes de rotation correcte, mais je vais avoir du mal à déterminer quand les utiliser.

Par exemple, l'explication dans le livre dit que je devrais monter le même chemin que je suis allé vers le bas pour insérer le noeud / élément. Cependant, je ne peux pas avoir des pointeurs parents.

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

Ce que je veux faire ici est remontons l'arbre, mais il ne peut vérifier l'équilibre après qu'il insère le nœud. Par conséquent, ce qui est dans la clause else.

J'ai aussi essayé de mettre le code de l'équilibre où R Samuel Klatchko suggéré, mais vérifié le solde de chaque pièce. Par exemple: Si l'on insère 7, 9, 5, 3 et 1 consécutivement, je reçois une exception de pointeur NULL lorsque vous essayez d'insérer 1

.

EDIT: L'une des raisons ci-dessus peut avoir quelque chose à voir avec la façon dont je faisais la hauteur. Il fonctionne très bien avec une seule rotation à droite si je calcule la hauteur à chaque fois avec la hauteur () mais qui brise le O (log (n)) d'un arbre AVL.

Toute réflexion sur la façon d'y arriver?

Answer 1

Code monte le même chemin que vous êtes allé vers le bas. Considérez ce code:

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

et le modifier légèrement:

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

Comme le code renvoie des appels récursifs, chaque retour vous ramène au parent. En ne retournant immédiatement la valeur de l'appel récursif, vous avez une chance de faire votre rééquilibrage.

Mise à jour pour le dernier code

Ne pas oublier de rééquilibrer lorsque vous avez inséré à droite.

Answer 2

Vous pouvez essayer de faire passer le pointeur de parent dans la méthode insert, ou vous pouvez convertir en insert une méthode itérative et de garder une pile explicite sur lequel vous enregistrez le chemin vers le bas de l'arbre.

Par ailleurs, afin de choisir la rotation à utiliser, vous pouvez simplement savoir qu'un noeud est déséquilibré, il faut savoir si le sous-arbre est plus profond à droite ou à gauche. Cela signifie que votre méthode de isBalanced simple n'est pas tout à fait suffisant. Il est aussi inefficace et soufflera l'arbre de AVL O (log n) complexité, parce que vous calculez les hauteurs à chaque fois.