Ошибка двойного вращения AVL Tree

Question

Я работаю над проектом для школы, который предполагает реализацию дерева AVL с использованием итеративной функции вставки, и у меня возникла проблема.

Я не уверен на 100%, что я не делаю, но моя программа не дает правильного вывода.

Вот что у меня есть для моей вставки функции:

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

Это моя функция, что я придумал до сих пор, для моего проекта я была предусмотрена функция баланса, и updateHeight, которые я буду обеспечить здесь:

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; 

И для высоты обновления:

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

Bas В то же время моя задача заключалась в реализации функций вставки и удаления. Мой вход для дерева AVL в следующем порядке:

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

и мой выход является следующее:

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

, когда оно должно быть:

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

Возвращаясь к моей функции вставки, то, что я считаю, проблема в том, что я не правильно обновлять высоты каждый раз, когда я вставить узел. Программа обрабатывает одиночные вращения просто отлично, но двойное вращение - это то, что не работает. Любая помощь будет оценена по достоинству.

Answer 1

Вы должны проверить и сбалансировать все уровни деревьев над точкой ввода узла.