AVLTree java rotations 无法正常工作.我只是想实现左轮换，然后从那里开始

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);
}

///这是BST类

import java.util.*;
public class BinaryTree <T extends Comparable<T>> extends Tree<Comparable<T>>{
public BinaryTree<T> left;
public BinaryTree<T> right;
int size;
int height;
public BinaryTree(T item){
super(item);
this.item = item;
this.left = null;
this.right= null; 
}
public BinaryTree<T> find(T item){
if(this.item.compareTo(item)==0){
return this;
}
if(this.item.compareTo(item)<0){
if(this.left != null){
if(this.left.item.compareTo(item) == 0){
return this.left;
}
else{
return this.left.find(item);
}
}     
}
else{
if(this.right != null){
if(this.right.item.compareTo(item) == 0){
return this.right;
}
else{  
return this.right.find(item);
}
}   
}
return null;      
}
public BinaryTree<T> insert(T item){
if(this.item.compareTo(item) < 0){
if(this.left != null){     
this.left.insert(item);
}
else{
this.left = new BinaryTree<T>(item);
}
return this.left;
}
else{
if(this.right != null){
this.right.insert(item);
}
else{
this.right = new BinaryTree<T>(item);
}
return this.right;
} 

}

第4部分 测量

public int size(){
return size(this);
}
public int size(BinaryTree<T> point){
if(point == null){
return 0;
}
else{
return (size(point.left)+1+size(point.right));
}
}
/*
*public int height() {
height = 1;
if (left != null) {
height += left.height;
}
if (right != null) {
height += right.height;
}
return height;
}
*
* */
public int height(){
return height(this);
}
public int height(BinaryTree<T> point) {
if(point == null){
return 0;
}
return (Math.max(height(point.right), height(point.left))+1);
}
//Part 3
public ArrayList<T> nlr(){
return nlr(this);
}
private ArrayList<T> nlr(BinaryTree<T> point){
ArrayList arr = new ArrayList();
if (point == null){
return arr;
}
arr.add(point.item);
arr.addAll(nlr(point.left));
arr.addAll(nlr(point.right));
return arr;
}
public ArrayList<T> lnr(){
return lnr(this);
}
private ArrayList<T> lnr(BinaryTree<T> point){
ArrayList arr = new ArrayList();
if (point == null){
return arr;
}
arr.addAll(lnr(point.left));
arr.add(point.item);
arr.addAll(lnr(point.right));
return arr;
}
public ArrayList<T> lrn(){
return lrn(this);
}
private ArrayList<T> lrn(BinaryTree<T> point){
ArrayList arr = new ArrayList();
if (point == null){
return arr;
}
arr.addAll(lrn(point.left));
arr.addAll(lrn(point.right));
arr.add(point.item);
return arr;
}
public ArrayList<T> bfs(){
return bfs(this);
}
private ArrayList<T> bfs(BinaryTree<T> input){
Queue<BinaryTree> queue = new LinkedList<BinaryTree>();
ArrayList arr = new ArrayList();
queue.add(input);
while(!queue.isEmpty()){
input = queue.remove();
arr.add(input.item);
if(input.left != null){
queue.add(input.left);
}
if(input.right != null){
queue.add(input.right);
}
}
return arr;
}
public BinaryTree<T> rotateLeft(){
return null;
}
public BinaryTree<T> rotateRight(){
return null;
}

}

Answer 1

我注意到这次旋转的一件事。 对于向左旋转，您向上旋转右子树以获得正确的旋转

//rotation
temp.left = x; 
//this is making the right child now the left child of the parent.
temp.right = x.parent.right;  
//this is making the same right sub tree copied to the left 
//which needs to be rotated the child of the right side as well which it 
//should already be.(does nothing)
x.right = an;  
//making this a right child(without check if there is a node) of the right 
//subtree.
//So this is in actuality not doing a correct rotation for an AVL tree.

请将上面的代码替换为：

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

temp1.right = x.left;  
//make the left node of the right subtree the new right node of the parent
x.left = temp1;
//make the current parent the left child of the right subtree(rotation).
x.parent = temp1.parent;
//make the parent of the right subtree point to the parent of the parent
//keeping tree integrity.
temp1.parent = x;
//make the parent pointer to what used to be the right child.   
//this completes a single left rotation for an AVL tree.
return x;
//the node that is now the parent node of the rotated subtree 
//or the new root node. if the rotation happened at the top.

请检查 https://en.wikipedia.org/wiki/AVL_tree 以获取完整说明以及 AVL 树如何与所有旋转配合使用单次和双次旋转的代码片段的旋转。

Answer 2

问题是搜索功能BinaryTree<T> find(T item)是在父类BinaryTree中实现的，而这个类，因为它应该对子类AVLTree没有任何了解。

find()方法返回一个BinaryTree，所以即使你构造了一个AVLTree的实例，当你调用find()时，你也会得到一个BinaryTree。

假设AVLTree<T> insert(T item)实现正确，树节点正在正确组装，因此您可以简单地将调用find()的结果类型转换为AVLTree