AVLTree java 旋转无法正常工作。我只是想实现左旋转，然后从那里开始

Question

我在旋转树和返回旋转的树时遇到问题。几乎在将新树插入到我的 AVL 后，我检查平衡是否小于 -1 并且父高度小于 0，这是正确的情况，我需要实现向左旋转。我需要帮助理解为什么我的左旋转不起作用以及如果它起作用为什么我没有得到旋转的树的回报。

public class AVLTree < T extends Comparable < T >> extends BinaryTree < T> 

{

private int balance ;

private AVLTree < T> parent;

public AVLTree(T item){

  this(item,null);

}

public AVLTree(T item, AVLTree<T> parent){

  super(item);

  this.balance = 0;

  this.parent = parent;    

}

public AVLTree<T> insert(T item){

  updateHeight(this);   

  if(this.item.compareTo(item) < 0){

 if(this.left != null){     

        this.left.insert(item);

 }

  else{

    this.left= new AVLTree<T>(item, this);

  }

  return rotations((AVLTree<T>)this.left);

  }

  else{

 if(this.right != null){

        this.right.insert(item);

 }

 else{

    this.right = new AVLTree<T>(item, this);        

 }

 return rotations((AVLTree<T>)this.right);

  } 

}  

private AVLTree<T> rotateLeft(AVLTree<T> x){

AVLTree<T> temp = (AVLTree<T>)x.parent;

AVLTree<T> an = (AVLTree<T>)temp.left;          

//rotation

temp.left = x;

temp.right = x.parent.right;

x.right = an;

//update heights

updateHeight(x);

updateHeight(temp);

//return new root

return temp;

}

public AVLTree<T> rotations(AVLTree<T> input){

  int balance = getBalance(input);

//Right Right

if (balance < -1 && ph() < 0){

   return input =rotateLeft(input);

}

return input;

}

public void updateHeight(AVLTree<T> current){

  current.height = Math.max(height((AVLTree<T>)current.left), 

height((AVLTree<T>)current.right)) + 1;

}

public int getBalance(){

  return getBalance(this);

}

public int getBalance(AVLTree<T> current){

  return (current == null)? 0 : height((AVLTree<T>)current.right) -  

  height((AVLTree<T>)current.left);

}

public int ph(){

  return lbal()-rbal();

}

int lbal(){

  if(this.right== null){

     return 0;

  }   

  return (height(this.right));

}

int rbal(){

   if(this.left == null){

      return 0;

   }

  return height(this.left);

}

Answer 1

问题是搜索功能BinaryTree<T> find(T item)是在父类中实现的BinaryTree，而这个类应该对子类一无所知AVLTree。该find()方法返回 a&nbsp;BinaryTree，因此即使您构造了 的实例AVLTree，当您调用时，find()您也会得到 a&nbsp;BinaryTree。假设AVLTree<T> insert(T item)实现是正确的，树节点正在正确组装，因此您可以简单地将调用结果类型find()转换为AVLTree