AVL Tree Doppelrotationsfehler

Question

Ich arbeite an einem Projekt für die Schule, das die Implementierung eines AVL-Baums mit einer iterativen Einfügefunktion beinhaltet und ich habe ein Problem.

Ich bin nicht 100% sicher, was ich nicht mache, aber mein Programm gibt nicht die richtige Ausgabe. Hier

ist, was ich für meine Insert-Funktion habe:

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

Dies ist meine Funktion, die ich gekommen bin, mit so weit nach oben, für mein Projekt i mit der Balance-Funktion zur Verfügung gestellt wurde, und updateHeight die ich bieten sich hier:

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; 

Und für das Update Höhe:

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

Bas Meine Aufgabe war es, die Funktionen Einfügen und Löschen zu implementieren. Mein Eingang für den avl Baum ist in dieser Reihenfolge:

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

und meine Ausgabe ist dies:

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

wenn es sein sollte:

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

gehen wir zurück zu meiner Insert-Funktion, was ich glaube, das Problem ist, dass ich richtig bin nicht die Höhen Aktualisierung jedes Mal, wenn ich einen Knoten einzufügen. Das Programm behandelt einfache Drehungen, aber doppelte Drehungen funktionieren nicht. Jede und jede Hilfe würde geschätzt werden.

Answer 1

Sie müssen überprüfen und balancieren alle die Baumebenen über dem Punkt einer Knoteneinfügung.