我在旋转树和返回旋转的树时遇到问题。几乎在将新树插入到我的 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);
}
小唯快跑啊
相关分类