Устранение неполадок корневого узла в дереве 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

В вашем методе вставки, вы должны рассмотреть вопрос о добавлении

rebalance(root); 

Просто перед вызовом

updateHeight(root); 

в конце метода. Затем перед удалением обязательно удалите вызовы для перебалансировки. Так, например, изменить

root.setLeftChild(rebalance(leftNodes)); 

в

root.setLeftChild(leftNodes); 

Предполагая, что остальная часть кода работает нормально, это должно быть исправление. Тогда каждый из ваших узлов, которые когда-либо считаются локальным корнем, будет иметь метод балансировки, называемый на них, включая абсолютный корень дерева.