[5 / 1 / ?]

AVL Tree Implementation in Java

No.667639 ViewReplyOriginalReport
Hello,

I am struggling with implementing an AVL tree structure in Java. I think I have narrowed down the errors on the following functions:

public int balanceFactor() {
boolean l0 = this.left == null;
boolean r0 = this.right == null;
if (r0 && l0) {
return 0;
}
if (r0) {
return - this.left.depth();
}
if (l0) {
return this.right.depth();
}
return this.right.depth() - this.left.depth();
}
public void checkBalance() {
if (this.balanceFactor() < -1 || this.balanceFactor() > 1) {
this.rebalance();
}
if (this.parent != null) {
this.parent.checkBalance();
}
}
public void rebalance() {
if (this.balanceFactor() < -1) {
if (this.left.balanceFactor() > 0) {
this.left.rotateRight();
}
this.rotateLeft();
}
else if (this.balanceFactor() > 1) {
if (this.right.balanceFactor() < 0) {
this.right.rotateLeft();
}
this.rotateRight();
}
}
public void rotateLeft() {
if (this.left.right != null) {
this.left.right.parent = this;
}
if (this.parent != null) {
if (this.parent.left == this) {
this.parent.left = this.left;
}
else {
this.parent.right = this.left;
}
}
this.left.parent = this.parent;
this.parent = this.left;
this.left = this.left.right;
this.parent.right = this;
}