在AVL樹中刪除

Question

正如你知道刪除節點後avl應該如何平衡，我會明白的。爲了開始，我考慮刪除沒有孩子的節點。

例如樹：

 10 
    / \ 
    5  17 
/\ /\ 
    2 9 12 20 
    \   \ 
    3   50 

比方說deletevalue（12）;

然後樹應該刪除後：

 10 
    / \ 
    5  17 
/\  \ 
    2 9  20 
    \   \ 
    3   50 

現在，我們看到的樹節點17平衡，因爲公式，其平衡因子=身高（左子樹[左樹爲空，因此-1 ]） - height（right subtree）= -2

所以我們通過檢查右對齊或右對齊情況來平衡樹。

If BalanceFactor(17's right) = -1 
    perform SingleLeftRotation(17); 
else if BalanceFactor(17's right) = -1 
    perform DoubleRightLeftRotation(17); 

類似的情況是，如果17的平衡因子是2，即它保持高，那麼它的各自的旋轉。 //高爐（17）= 2

If BalanceFactor(17's left) = 1 
    perform SingleLeftRotation(17); 
else if BalanceFactor(17's left) = -1 
    perform DoubleLeftRightRotation(17); 

平衡後，樹應該成爲這樣的：

  10 
    / \ 
    5  20 
/\ /\ 
    2 9 17 50 
    \   
    3 

這是刪除我設計。

從主要功能，我稱之爲

bool deletevalue(WA value) 
{ 
    AvLNode<WA> *temp = search(root, value); //calling search function to find node which has user-specified data & stored its address in temp pointer 
    if(temp!=0) //if temp node is not null then 
    { 
     if(temp->left==0 && temp->right==0) //if temp node don't have any children 
     { deletewithNochild(root, value); } //call to respective function 
     else if((temp->left!=0 && temp->right==0) || (temp->left==0 && temp->right!=0)) //if temp node has any 1 child, left or right 
     { deletewithOneChild(temp); } //call to respective function 
     else if(temp->left!=0 && temp->right!=0) //if temp node has 2 children 
     { deletewith2Child(temp);  } //call to respective function 

     return true; //for prompting respective output message 
    } 
    else 
     return false; //for prompting respective output message 
} 

是我們需要的節點沒有孩子的話，下面的函數envoked。

void deletewithNochild(AvLNode<WA> *temp, WA value) //temp is node which is to be deleted 
{ 
    if(value == root->key) //if temp is root node then 
    { 
     delete root; //free memory of root node 
     root = 0; //nullify root 
    } 
    else //if temp is some other node 
    { 
     if (value < temp->key) 
     { 
      deletewithNochild(temp->left, value); 
     } 
     else if (value > temp->key) 
     { 
      deletewithNochild(temp->right, value); 
     } 
     else if (value == temp->key) 
     { 
      AvLNode<WA> *father = findfather(temp, root); //calling findfather func to find father of temp node & store its address in father node pointer 

      if(father->left==temp) //if temp is left child of its father 
      { 
       delete temp; //free memory of temp node 
       father->left=0; //nullify father's left 
      } 
      else if(father->right==temp) //if temp is right child of its father 
      { 
       delete temp; //free memory of temp node 
       father->right=0;//nullify father's right 
      } 
      return; 
     } 
     cout<<"\nBalancing"; 
     if (balancefactor(temp) == 2) //if temp is left higher, ie. temp's Balance Factor = 2, then 
     { 
      cout<<"\t2 "; 
      if (balancefactor(temp->left) == 1) //if temp's left node has Balance Factor 1 then 
      { 
       SingleRightRotation(temp); //send temp node for rotation because temp is unbalance 
      } 
      else if (balancefactor(temp->left) == -1) //if temp's left node has Balance Factor -1, then 
      { 
       DoubleLeftRightRotation(temp); //send temp for double rotation because temp is unbalance 
      } 
     } 
     else if (balancefactor(temp) == -2) //if temp is right higher, ie. temp's Balance Factor = -2, then 
     { 
      cout<<"\t-2 "; 
      if (balancefactor(temp->right) == -1) //if temp's left node has Balance Factor -1 then 
      { 
       SingleLeftRotation(temp); //send temp node for rotation because temp is unbalance 
      } 
      else if (balancefactor(temp->right) == 1) //if temp's right node has Balance Factor 1, then 
      { 
       DoubleRightLeftRotation(temp); //send temp for double rotation because temp is unbalance 
      } 
     } 

    } 
} 

這裏是節點的節點&平衡因子高度的兩個實用功能

int heightofnode(AvLNode<WA> *temp) const 
{ 
    return temp==NULL ? -1 : temp->height; 
} 


int balancefactor(AvLNode<WA> *temp) const 
{ 
    return (heightofnode(temp->left) - heightofnode(temp->right)); 
} 

我的輸出，當我刪除12成爲 （廣度優先斯格特） - >> [ 10] [9] [17]

請幫助我，是否有任何遞歸問題？我再次幹運行&但不能理解。刪除必須通過遞歸完成，否則平衡樹將是一個更大的地獄。 預先感謝您給予時間。 :-)

Answer 1

爲什麼deletewithNochild（）調用任何其他的delete *方法？如果deletewithNochild被調用，您將在要刪除的節點上。只需將其刪除，向上移至父母，然後檢查父母的平衡因子並在需要時進行旋轉。對每個節點的父節點重新進行重新平衡，直到到達根節點。

如果有幫助，我已經實施了AVL tree in Java，如果你想參考。