AVL樹雙旋轉錯誤

我正在學校的一個項目上工作，涉及使用迭代插入功能實現AVL樹，我遇到問題。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; 
}

巴斯我的任務是實現插入和刪除功能。我的AVL樹輸入是順序如下：

5，8，9，3，6，7，5

和我的輸出是這樣的：

當它應該是：

要回到我的插入功能，我相信這是問題是，我沒有正確更新我每次插入一個節點時的高度。該程序處理單旋轉就好，但雙旋轉是不起作用的。任何和所有的幫助，將不勝感激。

來源

2016-05-11 Geedubs123

您必須檢查和平衡全部樹節點上的節點插入點。

來源

2016-05-11 05:44:43 GMichael

好的，這很有道理，但我應該如何去做這件事，我應該從newNode開始，然後上升或嘗試從根部平衡並平衡整個樹？ – Geedubs123

我通常實現'insert'作爲遞歸函數，當它存在一個節點時，它重新平衡當前節點下面的整個子樹。 – GMichael

是的，無論我在網上看到它的所有遞歸實現。不幸的是，我的教授給了我們以非遞歸方式做這件事的要求。到目前爲止，我自己試圖做到這一點，因爲你說這是不成功的。但至少我有一個想法，我需要做下一步，謝謝。 – Geedubs123

AVL樹雙旋轉錯誤

回答

相關問題