C++中的AVL樹重新平衡

Question

我正在研究AVL樹。我想我已經擁有了所有的旋轉功能。我有一個rotateleft，rotateright，rotateleftright和rotaterightleft功能。它們都以節點爲參數。我不知道要傳遞給這些參數的節點。你可以看看我的AVL樹重新平衡函數，並告訴我是否正確，以及我需要傳遞給每個函數。到目前爲止，我有根或頂級節點，但我認爲我錯了。我怎麼知道我需要傳遞給這些函數？

下面是函數：

void BinaryTree::rebalance(Node *N) 
{ 
    int count = 1; 
    if((N->getLeft()->getHeight()) > (N->getRight()->getHeight() + 1)) 
    { 
     if(N->getLeft()->getLeft()->getHeight() > N->getLeft()->getRight()->getHeight()) 
     { 
      rotateRight(root); 
      recalculate(root, count); 

     } 

     else 
     { 
      rotateLeftRight(root); 
       recalculate(root, count); 
     } 
    } 
    else if(N->getRight()->getHeight()> N->getLeft()->getHeight() + 1) 
    { 
     if(N->getRight()->getRight()->getHeight() > N->getRight()->getLeft()->getHeight()) 
     { 
      rotateLeft(root); 
       recalculate(root, count); 
     } 

     else 
     { 
      rotateRightLeft(root); 
      recalculate(root, count); 
     } 
    } 
} 

這裏是我的旋轉，左右改變

Node* BinaryTree::rotateLeftRight(Node *N) 
{ 
    Node *newNode = new Node();//declares a new Node 
    newNode = N->getLeft();//sets the node 

    N->setLeft(rotateLeft(newNode->getLeft());//sets the left subtree 
    recalculate(root);//recalculates the height 
    root->setHeight(NULL);//sets the height of the root node 
    return rotateRight(N);//retuns the tree rotated right 
} 

，這裏是我的左右旋轉功能：

Node* BinaryTree::rotateLeft(Node *N) 
{ 
    Node *newNode = new Node();//declares a new node 
    newNode = N->getRight();//sets the new node to the right child of N 
    N->setRight(newNode->getLeft());//sets the right of N equal to new nodes left child 
    newNode->setLeft(N);//sets the left child of the new node to N 

    return newNode;//retuns the newNode 
} 

如果我有樹50 20 10和15我通過什麼傳遞給這些函數來重新平衡樹？

Answer 1

有在你的代碼的一些錯誤，你沒有在你的另一個問題提交一個做的，那是你不檢查你的代碼無參指針：

• 你不檢查如果N是NULL在方法的開頭

• 你不低於（並在其對稱的兄弟姐妹），如果左邊和右邊節點是線檢查NULL

  if((N->getLeft()->getHeight()) > (N->getRight()->getHeight() + 1)) 
  

關於算法本身，它取決於旋轉函數的行爲。在wikipedia entry中描述的算法解釋說，嵌套if（rotateLeftRight和rotateRightLeft方法）中的第二種情況應執行2次旋轉。如果你的旋轉函數符合那個描述，你應該沒問題。

recalculate的情況在另外一個問題中已經得到了解決，但在這種情況下，您實際上不需要重新計算整個子樹的高度，因爲您在該問題的評論中正確告訴了我。唯一改變的節點是那些孩子已經改變的節點。您應該在每個特定的旋轉方法中執行該計算，因爲每個案例都準確描述哪些節點會更新。