無法平衡AVL樹中的根節點

Question

你好，我似乎在重新平衡AVL樹時遇到了問題。它平衡除根節點之外的其他所有內容。我不知道它爲什麼不平衡根節點。當我傳遞值如50,40,30,20和10.我得到50,30,20,10和40.50不應該是根，正確的根值應該是40. 以下是我的代碼：

public void insert(T data){ 

    AVLNode<T> newNode = new AVLNode<T>(data); 
    if(isEmpty()){ 
     root = newNode; 
    } 
    else{ 
     insert(root, newNode); 
    } 

} 

private void insert(AVLNode<T> root, AVLNode<T> newNode){ 

if(newNode.getData().compareTo(root.getData())<0){ 
     if(root.getLeftChild()!=null){ 
     AVLNode<T> leftNodes = root.getLeftChild(); 
     insert(leftNodes, newNode); 
     root.setLeftChild(rebalance(leftNodes)); 
     } 
     else{ 
      root.setLeftChild(newNode); 
     } 
    } 
    else if(newNode.getData().compareTo(root.getData())>0){ 
     if(root.getRightChild()!=null){ 
     AVLNode<T> rightNodes = root.getRightChild(); 
     insert(rightNodes, newNode); 
     root.setRightChild(rebalance(rightNodes)); 
    } 
     else{ 
      root.setRightChild(newNode); 
     } 
    } 
    else{ 
      root.setData(newNode.getData()); 
    } 
    updateHeight(root); 
} 

//re-balances the tree. 
private AVLNode<T> rebalance(AVLNode<T> root){ 
    int difference = balance(root); 
    if (difference > 1){ 
     if(balance(root.getLeftChild())>0){ 
      root = rotateRight(root); 
     } 
     else{ 
      root = rotateLeftRight(root); 
     } 
    } 
    else if(difference < -1){ 
     if(balance(root.getRightChild())<0){ 
      root = rotateLeft(root); 
     } 
     else{ 
      root = rotateRightLeft(root); 
     } 
    } 
    return root; 
} 

//updates the height of the tree. 
public void updateHeight(AVLNode<T> root){ 
    if((root.getLeftChild()==null) && (root.getRightChild()!=null)){ 
     root.setHeight(root.getRightChild().getHeight()+1); 
    } 
    else if((root.getLeftChild() !=null)&&(root.getRightChild()==null)){ 
     root.setHeight(root.getLeftChild().getHeight()+1); 
    } 
    else 
     root.setHeight(Math.max(getHeight(root.getLeftChild()), getHeight(root.getRightChild()))+1); 
} 

private int balance(AVLNode<T> root) { 
    return getHeight(root.getLeftChild())-getHeight(root.getRightChild()); 
} 

//single left left rotation of the tree 
private AVLNode<T> rotateLeft(AVLNode<T> root){ 
    AVLNode<T> NodeA = root.getRightChild(); 
    root.setRightChild(NodeA.getLeftChild()); 
    NodeA.setLeftChild(root); 
    root.setHeight(Math.max(getHeight(root.getLeftChild()), getHeight(root.getRightChild()))+1); //updates the height 
    NodeA.setHeight(Math.max(getHeight(NodeA.getLeftChild()), getHeight(NodeA.getRightChild()))+1); 
    return NodeA; 
} 
//single right right rotation of the tree 
private AVLNode<T> rotateRight(AVLNode<T> root){ 
    AVLNode<T> NodeA = root.getLeftChild(); 
    root.setLeftChild(NodeA.getRightChild()); 
    NodeA.setRightChild(root); 
    root.setHeight(Math.max(getHeight(root.getLeftChild()), getHeight(root.getRightChild()))+1); //updates the height of the AVL tree 
    NodeA.setHeight(Math.max(getHeight(NodeA.getLeftChild()), getHeight(NodeA.getRightChild()))+1); 
    return NodeA; 
} 
//a double rotation. Left right rotation 
private AVLNode<T> rotateLeftRight(AVLNode<T> root){ 
    AVLNode<T> nodeA = root.getLeftChild(); 
    root.setLeftChild(rotateLeft(nodeA)); 
    return rotateRight(root); 
} 
//a right left rotation 
private AVLNode<T> rotateRightLeft(AVLNode<T> root){ 
    AVLNode<T> nodeA = root.getRightChild(); 
    root.setRightChild(rotateRight(nodeA)); 
    return rotateLeft(root); 
} 

Answer 1

在您的插入方法，你應該只考慮調用

updateHeight(root); 

在方法結束前添加

rebalance(root); 

。然後確保在此之前刪除對再平衡的呼叫。因此，例如，改變

root.setLeftChild(rebalance(leftNodes)); 

到

root.setLeftChild(leftNodes); 

假設你的代碼的其餘部分工作正常，這應該是修復。然後，每個被視爲本地根的節點都將具有調用它們的平衡方法，包括樹的絕對根。