JAVA AVL 삭제, 기존의 순환 코드를 사용하여 구현하는 방법은 무엇입니까?

Question

3 일이 지났지 만 여전히 문제를 해결할 수 없습니다. 내 문제는 삭제할 때마다 코드가 삭제 될 때마다 완벽하게 작동하지 않는다는 것입니다. 나는 "Java에서 데이터 구조"라는 D.S. Malik의 저서에서 나온이 기존 코드를 가지고있다. 내가 삭제 작업을 구현하고 싶어하지만 내가 기존 회전 코드를 사용하는 대부분의 시간을 실패, 전체 프로그램은 아래와 같습니다 : 책에서

public class AVL 
{ 
protected class AVLNode 
{ 
    public int info; 
    public int bfactor; 
    public AVLNode llink; 
    public AVLNode rlink; 
} 

protected AVLNode root; 
protected bool isTaller; 
private bool isDuplicate = false; 

private AVLNode rotateToLeft(AVLNode root) 
{ 
    AVLNode p; //reference variable to the root of the right subtree of root 
    if (root == null) 
     throw new Exception("Error in the tree."); 
    else if (root.rlink == null) 
     throw new Exception("Error in the tree: No right subtree to rotate."); 
    else 
    { 
     p = root.rlink; 
     root.rlink = p.llink; //the left subtree of p becomes the right subtree of root 
     p.llink = root; 
     root = p; //make p the new root node 
    } 

    return root; 
} 

private AVLNode rotateToRight(AVLNode root) 
{ 
    AVLNode p; //reference variable to the root of the left subtree of root 

    if (root == null) 
     throw new Exception("Error in the tree."); 
    else if (root.llink == null) 
     throw new Exception("Error in the tree: No left subtree to rotate."); 
    else 
    { 
     p = root.llink; 
     root.llink = p.rlink; //the right subtree of p becomes the left subtree of root 
     p.rlink = root; 
     root = p; //make p the new root node 
    } 

    return root; 
} 

private AVLNode balanceFromLeft(AVLNode root) 
{ 
    AVLNode p; 
    AVLNode w; 

    p = root.llink; //p points to the left subtree of root 

    switch (p.bfactor) 
    { 
     case -1: 
      root.bfactor = 0; 
      p.bfactor = 0; 
      root = rotateToRight(root); 
      break; 
     case 0: 
      throw new Exception("Error: Cannot balance from the left."); 
     case 1: 
      w = p.rlink; 
      if (w.bfactor == -1) 
      { 
       root.bfactor = 1; 
       p.bfactor = 0; 
      } 
      else if (w.bfactor == 0) 
      { 
       root.bfactor = 0; 
       p.bfactor = 0; 
      } 
      else if (w.bfactor == 1) 
      { 
       root.bfactor = 0; 
       p.bfactor = -1; 
      } 

      w.bfactor = 0; 
      p = rotateToLeft(p); 
      root.llink = p; 
      root = rotateToRight(root); 
      break; 
    } 

    return root; 
} 

private AVLNode balanceFromRight(AVLNode root) 
{ 
    AVLNode p; 
    AVLNode w; 

    p = root.rlink; //p points to the right subtree of root 

    switch (p.bfactor) 
    { 
     case -1: 
      w = p.llink; 
      if (w.bfactor == -1) 
      { 
       root.bfactor = 0; 
       p.bfactor = 1; 
      } 
      else if (w.bfactor == 0) 
      { 
       root.bfactor = 0; 
       p.bfactor = 0; 
      } 
      else if (w.bfactor == 1) 
      { 
       root.bfactor = -1; 
       p.bfactor = 0; 
      } 
      w.bfactor = 0; 
      p = rotateToRight(p); 
      root.rlink = p; 
      root = rotateToLeft(root); 
      break; 
     case 0: 
      throw new Exception("Error: Cannot balance from the right."); 
     case 1: 
      root.bfactor = 0; 
      p.bfactor = 0; 
      root = rotateToLeft(root); 
      break; 
    } 

    return root; 
} 

private AVLNode insertIntoAVL(AVLNode root, AVLNode newNode) 
{ 
    if (root == null) 
    { 
     root = newNode; 
     isTaller = true; 
    } 
    else if (root.info == newNode.info) 
     isDuplicate = true; 
    //throw new Exception("No duplicates are allowed."); 
    else if (root.info > newNode.info) //newNode goes in the left subtree 
    { 
     root.llink = insertIntoAVL(root.llink, newNode); 

     if (isTaller)    //after insertion, the subtree grew in height 
      switch (root.bfactor) 
      { 
       case -1: root = balanceFromLeft(root); 
        isTaller = false; 
        break; 
       case 0: root.bfactor = -1; 
        isTaller = true; 
        break; 
       case 1: root.bfactor = 0; 
        isTaller = false; 
        break; 
      } 
    } 
    else 
    { 
     root.rlink = insertIntoAVL(root.rlink, newNode); 

     if (isTaller)    //after insertion, the subtree grew in height 
      switch (root.bfactor) 
      { 
       case -1: root.bfactor = 0; 
        isTaller = false; 
        break; 
       case 0: root.bfactor = 1; 
        isTaller = true; 
        break; 
       case 1: root = balanceFromRight(root); 
        isTaller = false; 
        break; 
      } 
    } 

    return root; 
    } 
} 

나는 삭제 방법을 만들 수 있지만 모든 지시 사항을 준수 나는 그것이 실패했다.

편집 : 좋아, 그럼 이건 내 삭제 방법이지만 실제로 C#에서 AVL 애니메이션 앱을 개발하고 있기 때문에 C#에서는 실례가없는 메소드에 대한 추가 호출을 코딩했습니다. 관련없는 메소드 호출이 무시되면 무시됩니다.

public Node deleteFromAVL(Node parent, Node delNode) 
    { 
     if (parent == null) //not found 
     { 
      MessageBox.Show("Item not found."); 
      isShorter = false; 
     } 
     else if (parent.value.Equals(delNode.value)) //found 
     { 
      //the four cases of deletion 
      #region FOUR CASES OF DELETION 
      if (parent.left == null && parent.right == null) //leaf node 
      { 
       isShorter = true; 
       return null; 
      } 
      else if (parent.left == null) 
      { 
       isShorter = true; 
       tempNode = parent.right; 
       return tempNode; 
      } 
      else if (parent.right == null) 
      { 
       isShorter = true; 
       tempNode = parent.left; 
       return tempNode; 
      } 
      else 
      { 
       current = parent.left; 
       trailCurrent = null; 
       while (current.right != null) 
       { 
        trailCurrent = current; 
        current = current.right; 
       } 
       parent.value = current.value; 

       if (trailCurrent == null) 
       { 
        parent.left = current.left; //movement 
        if (parent.left != null) 
        { 
         parent.left.moveToParent(); //move to parent 
        } 
       } 
       else 
       { 
        trailCurrent.right = current.left; //movement 
        if (trailCurrent.right != null) 
        { 
         trailCurrent.right.parent = trailCurrent; 
        } 
       } 

       isShorter = true; 
      } 
      #endregion 
     } 
     else if (parent.value > delNode.value) // search left 
     { 
      parent.left = deleteFromAVL(parent.left, delNode); 
      //change balance factors 
      if (isShorter) 
      { 
       switch (parent.bfactor) 
       { 
        case -1: parent.bfactor = 0; 
         isShorter = true; 
         break; 
        case 0: parent.bfactor = 1; 
         isShorter = false; 
         break; 
        case 1: parent = balanceFromRight(parent); 
         isShorter = false; 
         break; 
       } 
      } 
     } 
     else//search right 
     { 
      parent.right = deleteFromAVL(parent.right, delNode); 
      //change balance factors 
      if (isShorter) 
      { 
       switch (parent.bfactor) 
       { 
        case -1: parent = balanceFromLeft(parent); 
         isShorter = false; 
         break; 
        case 0: parent.bfactor = -1; 
         isShorter = false; 
         break; 
        case 1: parent.bfactor = 0; 
         isShorter = true; 
         break; 
       } 
      } 

     } 
     return parent; 
    } 

Answer 1

나는 내 노드 제거에 대한 나의 구현만을 보여줄 것입니다.

private AVLNode<T> Remove(AVLNode<T> T, int x) 
{ 
    if(T == null){ //if the value does not exist just return null 
     return null; 
    }     
    if(x < T.item)//if the value is less than item 
    { 
     if(T.left == null)//if T.left = null return null x doesnt exist 
     { 
      return null; 
     } 
     else 
     { 
      T.left = Remove(T.left, x); //T.left exists recursive call Remove with T.left 
      T.height = Math.max(Height(T.left), Height(T.right))+1;//reset height 
      if(HeightCheck(T.right) - HeightCheck(T.left) == 2){ //check for imbalance 
       if(T.right.left.height > T.right.right.height){ //if the height of the subtree is imbalance 
        return T = DoubleRotateWithRightChild(T); //if after delete the right->left > right->right double rotate 
       }       
       else{ 
        return T = SingleRotateWithRightChild(T); //if after delete right->left < right->right single rotate 
       }             
      } 
     } 
    } 
    else 
    { 
     if(x > T.item){ //if X > item 
      if(T.right == null)\ 
      { //having an issue dealing with null pointers being passed so deal with it here 
       return null; //if T.right == null return null 
      } 
      else 
      { 
       T.right = Remove(T.right, x); //if T.right exists recursive call remove with T.right 
       T.height = Math.max(Height(T.left), Height(T.right))+1; //rest height 
       if(HeightCheck(T.left) - HeightCheck(T.right) == 2) 
       { //check for imbalace 
        if(T.left.left.height > T.left.right.height) 
        { 
         return T = DoubleRotateWithLeftChild(T); //if after delete left->left height > left->right height double rotate 
        }       
        else 
        { 
         return T = SingleRotateWithLeftChild(T); // if after delete left->left height < left->right height single rotate 
        }        
       } 
      } 
     } 
     else{ 
      if((T.right != null) && (T.left != null)){ //if x == T.item and both left and right exist 
       T.item = FindMax(T.left).item; //find the max item in the left sub tree or the right most value of the left subtree and set it as the new subtree root item 
       T.left = Remove(T.left, T.item); //remove the value you just made the new subtree root from the left subtree 
      } 
      else 
      { 
       if(T.left != null){ //if only one side exists return it. 
        return T.left; 
       }        
       else 
       { 
        return T.right; 
       }       
      } 
     } 
    } 
    return T; 
} 

내 구현으로 인해 사용자의 실수를 잘못 이해할 수 있습니다. 주로 이중 회전을 사용하지 않는 회전의 구현입니다. 이것은 올바른 아이에게 이중 회전입니다. 위의 코드에서 볼 때 언제 사용해야하는지 알 수 있습니다.

private AVLNode<T> DoubleRotateWithRightChild(AVLNode<T> T) 
{ 
    T.right = SingleRotateWithLeftChild(T.right); 
    return SingleRotateWithRightChild(T); 
}