Équilibrage d'arbre AVL

Question

Je travaille sur une affectation qui me demande d'implémenter un arbre AVL. Je suis sûr que j'ai les méthodes de rotation correctes, mais j'ai 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 descendu pour insérer le nœud/l'élément. Cependant, je ne peux pas avoir de pointeurs parent.

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, ceci étant dans la clause else.

J'ai également essayé de mettre le code de la balance où R Samuel Klatchko a suggéré, mais j'ai vérifié la balance sur chaque insert. Par exemple: Si l'on insère consécutivement 7, 9, 5, 3 et 1, j'obtiens une exception de pointeur nul lorsque j'essaie d'insérer 1.

EDIT: Une des raisons de ce qui précède peut être liée à la façon dont je faisait la hauteur. Cela fonctionne bien avec une seule rotation à droite si je calcule la hauteur à chaque fois avec height() mais cela casse le temps O (log (n)) d'un arbre AVL.

Des idées sur la façon d'accomplir cela?

Answer 1

Votre code grimpe le même chemin que vous êtes descendu. Considérez ce code:

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

et modifier légèrement:

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

Comme le code retourne des appels récursifs, chaque retour vous ramène au parent. En ne renvoyant pas 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 passer le pointeur parent dans la méthode insert, ou vous pouvez convertir insert en une méthode itérative et conserver une pile explicite sur laquelle vous enregistrez le chemin dans l'arborescence. A propos, pour choisir quelle rotation utiliser, vous pouvez juste savoir qu'un nœud est déséquilibré, vous devez savoir si le sous-arbre plus profond est à droite ou à gauche. Cela signifie que votre méthode simple isBalanced n'est pas assez. Il est également inefficace et va faire exploser la complexité O (log n) de l'arbre AVL, car vous calculez les hauteurs à chaque fois.