У меня проблемы с вращением дерева и возвращением повернутого дерева.В значительной степени после вставки нового дерева в мой AVL я проверяю баланс, если он <-1, а высота родительского элемента <0, это правильный правый случай, и мне нужно реализовать левый поворот.Мне нужна помощь, чтобы понять, почему мое левое вращение не работает, и если оно работает, почему я не получаю взамен повернутое Дерево. </p>
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;
}
}