, поэтому я строю avl-дерево, но у меня возникают проблемы с поддержанием баланса, так как я выполняю повороты, он отлично работает на одиночных оборотах, но при двойных поворотах получаются все значения коэффициента баланса.также я не могу использовать высоту поддеревьев, чтобы вычислить баланс, если кто-нибудь может мне помочь с этим, было бы здорово
это мой метод вставки, он вызывает вызовы вращающихся методов, а затем обновляет баланс
private StringAVLNode insert(String str, StringAVLNode t) {
if(t==null){
t=new StringAVLNode(str);
}else if(t.getItem()==str) {
}else if(str.compareTo(t.getItem())<0){
int OldBalance;
if(t.getLeft()!=null){
OldBalance=t.getLeft().getBalance();
}else {
OldBalance=282;
}
t.setLeft(insert(str,t.getLeft()));
int newBalance=t.getLeft().getBalance();
if((OldBalance==0&& newBalance!=0)|| OldBalance==282){
t.setBalance(t.getBalance()-1);
if(t.getBalance()==-2){//either ll or lr
if(t.getLeft().getBalance()<0){//ll
t=rotateRight(t);
t.setBalance(0);
if(t.getRight()!=null) {
t.getRight().setBalance(0);
}
if(t.getLeft()!=null){
t.getLeft().setBalance(0);
}
}else {//lr
System.out.println("lr insert");
t.setLeft(rotateLeft(t.getLeft()));
t=rotateRight(t);
t.getLeft().setBalance(t.getLeft().getBalance()*-1);
if(t.getLeft().getLeft()==null&&t.getLeft().getRight()==null){
t.getLeft().setBalance(0);
}
t.getRight().setBalance(0);
t.setBalance(0);
}
System.out.println("rotate");
}
}
}else {
int OldBalance;
if(t.getRight()!=null){
OldBalance=t.getRight().getBalance();
}else {
OldBalance=282;
}
t.setRight(insert(str,t.getRight()));
int newBalance=t.getRight().getBalance();
if((OldBalance==0&& newBalance!=0)|| OldBalance==282){
t.setBalance(t.getBalance()+1);
if(t.getBalance()==2){//either rr or rl
System.out.println("rotate");
if(t.getRight().getBalance()>0){//rr
t=rotateLeft(t);
t.setBalance(0);
if(t.getRight()!=null) {
t.getRight().setBalance(0);
}
if(t.getLeft()!=null){
t.getLeft().setBalance(0);
}
}else {//rl
System.out.println("rl insert");
t.setRight(rotateRight(t.getRight()));
t=rotateLeft(t);
t.getRight().setBalance(t.getRight().getBalance()*-1);
if(t.getRight().getLeft()==null&&t.getRight().getRight()==null){
t.getRight().setBalance(0);
}
t.getLeft().setBalance(0);
t.setBalance(0);
}
}
}
}
return t;
}