Balanceamento de árvore AVL

[lucianodouglasm2]

Olá estou tentando implementar o balanceamento de uma árvore AVL, e não estou conseguindo fazer. Segue à baixo o código parcial da minha implementação. Alguém pode me ajudar?

Código parcial da árvore AVL

@Override
public void add(final E element) {
  this.root = this.add(this.root, element);
}

private Node<E> add(final Node<E> node, final E element) {
  if (node == null) {
    return new Node<>(element);
  }
  final int compareTo = this.compareTo(node, element);
  Node<E> son = null;
  if (compareTo < 0) {
    son = this.add(node.getLeft(), element);
    son.setFather(node);
    node.setLeft(son);
  } else {
    if (compareTo > 0) {
      son = this.add(node.getRight(), element);
      son.setFather(node);
      node.setRight(son);
    }
  }
  return this.calculateBalancingFactor(node);
}

@Override
public void remove(final E element) {
  this.root = this.remove(this.root, element);
}

private Node<E> remove(final Node<E> node, final E element) {
  if (node == null) {
    return null;
  }
  final int compareTo = this.compareTo(node, element);
  if (compareTo == 0) {
    if (!node.hasSons()) {
      return null;
    }
    if (!node.hasRightSon()) {
      return node.getLeft();
    }
    if (!node.hasLeftSon()) {
      return node.getRight();
    }
    final E smallestElement = this.getSmallestElement(node.getRight());
    node.setElement(smallestElement);
    node.setRight(this.remove(node.getRight(), element));
  }
  if (compareTo < 0) {
    node.setLeft(this.remove(node.getLeft(), element));
  }
  if (compareTo > 0) {
    node.setRight(this.remove(node.getRight(), element));
  }
  return this.calculateBalancingFactor(node);
}

@Override
public void replace(final E oldElement, final E newElement) {
  final Node<E> node = this.getNode(this.root, oldElement);
  if (node != null) {
    node.setElement(newElement);
    if (node.hasFather()) {
      final Node<E> father = node.getFather();
      if (father.getLeft() == node) {
        father.setLeft(node);
      }
      if (father.getRight() == node) {
        father.setRight(node);
      }
    }
    if (node.hasLeftSon()) {
      node.getLeft().setFather(node);
    }
    if (node.hasRightSon()) {
      node.getRight().setFather(node);
    }
    this.root = this.calculateBalancingFactor(node);
  }
}

@Override
public void reverserSons(final E element) {
  final Node<E> father = this.getNode(this.root, element);
  if (father != null) {
    final Node<E> auxNode = father.getRight();
    father.setRight(father.getLeft());
    father.setLeft(auxNode);
    this.root = this.calculateBalancingFactor(father);
  }
}

private Node<E> calculateBalancingFactor(Node<E> node) {
  final Node<E> left = node.getLeft();
  final int leftHeight = this.getHeight(left);
  final Node<E> right = node.getRight();
  final int rightHeight = this.getHeight(right);
  int balancingFactor = leftHeight - rightHeight;
  if (balancingFactor < -2) {
    balancingFactor = -2;
  }
  if (balancingFactor > 2) {
    balancingFactor = 2;
  }
  node.setBalancingFactor(balancingFactor);
  return node;
}

@Override
public int getHeight(final E element) {
  final Node<E> node = this.getNode(this.root, element);
  return this.getHeight(node);
}

private int getHeight(final Node<E> node) {
  if (node == null) {
    return 0;
  }
  final int leftHeight = this.getHeight(node.getLeft());
  final int rightHeight = this.getHeight(node.getRight());
  return Math.max(leftHeight, rightHeight) + 1;
}

private Node<E> getNode(final Node<E> node, final E element) {
  if (node == null) {
    return null;
  }
  final int compareTo = this.compareTo(node, element);
  if (compareTo < 0) {
    return this.getNode(node.getLeft(), element);
  }
  if (compareTo > 0) {
    return this.getNode(node.getRight(), element);
  }
  return node;
}

private int compareTo(final Node<E> node, final E element) {
  return element.compareTo(node.getElement());
}

Código parcial do Nó

public class Node<E> {

  private Node<E> father;
  private E element;
  private Node<E> left;
  private Node<E> right;
  private int balancingFactor;

  public Node(final E element) {
    this.element = element;
  }

  public Node(final Node<E> father, final E element) {
    this(element);
    this.father = father;
  }

  public Node(final E element, final Node<E> left, final Node<E> right) {
    this(element);
    this.left = left;
    this.right = right;
  }

  public Node(final Node<E> father, final E element, final Node<E> left, final Node<E> right) {
    this(element, left, right);
    this.father = father;
  }

  public Node<E> getFather() {
    return father;
  }

  public void setFather(final Node<E> father) {
    this.father = father;
  }

  public E getElement() {
    return element;
  }

  public void setElement(final E element) {
    this.element = element;
  }

  public Node<E> getLeft() {
    return left;
  }

  public void setLeft(final Node<E> left) {
    this.left = left;
  }

  public Node<E> getRight() {
    return right;
  }

  public void setRight(final Node<E> right) {
    this.right = right;
  }

  public boolean hasSons() {
    return this.hasLeftSon() && this.hasRightSon();
  }

  public boolean hasFather() {
    return this.father != null;
  }

  public boolean hasLeftSon() {
    return this.left != null;
  }

  public boolean hasRightSon() {
    return this.right != null;
  }

  public int getBalancingFactor() {
    return balancingFactor;
  }

  public void setBalancingFactor(final int balancingFactor) {
    this.balancingFactor = balancingFactor;
  }

  @Override
  public String toString() {
    String toString = "Node: {";
    toString += "\n\tElement: " + this.element;
    if (this.hasFather()) {
      toString += ", \n\tFather: " + this.father.getElement();
    }
    if (this.hasLeftSon()) {
      toString += ", \n\tLeft: " + this.left.getElement();
    }
    if (this.hasRightSon()) {
      toString += ", \n\tRight: " + this.right.getElement();
    }
    toString += ", \n\tBalancing factor: " + this.balancingFactor;
    toString += "\n}";
    return toString;
  }

}