AVL 트리에서의 삭제

Question

노드를 삭제 한 후에 AVL이 어떻게 균형을 잡아야하는지 알다시피, 나는 지적 할 것이다. 시작하려면, 아이가없는 노드 삭제를 고려하십시오. 트리 예

는 :

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

는 (12)을 말하게 deletevalue;

이어서 트리 삭제 후 같아야

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

을 이제, 트리 때문에 식으로, 노드 (17)에서 균형을 참조 대차 인자 = 높이 (좌측 서브 트리 [좌측 트리 이렇게 널 -1 ]) - 높이 (오른쪽 하위 트리) = -2

그래서 오른쪽 대문자인지 오른쪽 대문자인지 확인하여 트리의 균형을 조정합니다.

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

17의 밸런스 계수가 2 인 경우, 즉 높게 유지 된 후, 각각의 회전이 유사하다. BF에 대한 // (17) = 균형 후

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

2, 트리이 될해야합니다

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

    } 
} 

노드의 노드 & BALANCE 계수 HEIGHT 두 유틸리티 함수이다

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

내 출력은 I 삭제할 때 12 (너비 우선 트래버스)를해진다 - >> [ 10] [9] [17]

재귀에 문제가 있습니까? 나는 다시 마른 runned했다 & 그러나 다시는 이해할 수 없다. 삭제는 재귀를 통해 이루어져야합니다. 그렇지 않으면 균형 잡힌 트리가 더 큰 지옥이됩니다. 시간을내어 미리 감사드립니다. :-)

Answer 1

왜 Nickild()는 다른 삭제 * 메소드를 호출합니까? deletewithNochild가 호출되면 삭제할 노드에 있습니다. 간단히 삭제하고, 상위로 이동하고, 부모 균형 계수를 확인하고 필요한 경우 회전하십시오. 루트에 도달 할 때까지 각 노드의 상위에 대해 재조정을 반복하십시오.

참조를 원할 경우 AVL tree in Java을 구현했습니다.