AVL Tree Double erreur de rotation

Question

Je travaille sur un projet pour l'école qui implique la mise en œuvre d'un arbre AVL en utilisant une fonction d'insertion itérative et j'ai un problème.

Je ne suis pas sûr à 100% ce que je ne fais pas mais mon programme ne donne pas la bonne sortie.

Voici ce que j'ai pour ma fonction d'insertion:

bool AVLTree::insert(string ss, string na){ 

AVLNode* newNode = new AVLNode(ss, na); 
updateHeight(newNode); 

//Tree is empty, make the new Node the root of a new tree 
if(getRoot() == nullptr){ 
    root = newNode; 
    print(); 
    return true; 
} 
//Tree is not empty 
else{ 
    AVLNode* checkPoint; 
    checkPoint = root; 

    while(checkPoint != nullptr){ 

     //If the ssn is already in the tree 
     if(checkPoint->ssn.compare(newNode->ssn) == 0){ 
      return false; 
     } 
     else if(checkPoint->ssn.compare(newNode->ssn) > 0){ 
      if(checkPoint->left == nullptr){ 
       break; 
      } 
      checkPoint = checkPoint->left; 
     } 
     else{ 
      if(checkPoint->right == nullptr){ 
       break; 
      } 
      checkPoint = checkPoint->right; 
     } 
    } 

    if(newNode->ssn.compare(checkPoint->ssn) < 0){ 
     checkPoint->left = newNode; 
    } 
    else{ 
     checkPoint->right = newNode; 
    } 
    updateHeight(checkPoint); 
    balance(root); 
    print(); 
    return true; 
} 

Ceci est ma fonction que je suis venu avec à ce jour, pour mon projet m'a fourni la fonction de l'équilibre, et updateHeight que je fournir ici:

AVLNode* AVLTree::balance(AVLNode* node){ 
updateHeight(node); 
if (balanceFactor(node) == 2) { 
    if (balanceFactor(node->left) < 0) { 
     node->left = rotateLeft(node->left); // for left right case 
    } 

    AVLNode* temp = rotateRight(node); 
    updateHeight(temp); 
    return temp; 
} 

if (balanceFactor(node) == -2) { 
    if (balanceFactor(node->right) > 0) { 
     node->right = rotateRight(node->right); // for right left case 
    } 
    AVLNode* temp2 = rotateLeft(node); 
    updateHeight(temp2); 
    return temp2; 
} 
return node; 

Et pour la hauteur de mise à jour:

void AVLTree::updateHeight(AVLNode* node){ 
    int hl = height(node->left); 
    int hr = height(node->right); 
    node->height = (hl>hr ? hl : hr) + 1; 
} 

Bas En fait, ma tâche consistait à implémenter les fonctions d'insertion et de suppression. Mon entrée pour l'arbre AVL est dans cet ordre:

5, 8, 9, 3, 6, 7, 5

et ma sortie est la suivante:

 8 
    /\ 
    5 9 
/\ 
    3 6 
/ \ 
2  7 

quand il devrait être:

 6 
    / \ 
    3  8 
/\ /\ 
    2 5 7 9 

pour en revenir à ma fonction d'insertion, ce que je crois est le problème est que je ne suis pas mise à jour correctement les hauteurs à chaque fois insérer un nœud. Le programme gère très bien les rotations simples, mais les rotations doubles sont ce qui ne fonctionne pas. Toute aide serait appréciée.

Answer 1

Vous devez vérifier et équilibrer tous les niveaux au-dessus du point d'insertion d'un nœud.