public class AVLTree<E> extends BST<E> {
  /** Tworzenie pustego drzewa AVL z naturalnym komparatorem */
  public AVLTree() { // Automatycznie wywoływana jest metoda super() 
  }

  /** Tworzenie drzewa BST z określonym komparatorem */
  public AVLTree(java.util.Comparator<E> c) {
    super(c);
  }

  /** Tworzenie drzewa AVL na podstawie tablicy obiektów */
  public AVLTree(E[] objects) {
    super(objects);
  }

  @Override /** Przesłanianie metody createNewNode, aby tworzyła węzły AVLTreeNode */
  protected AVLTreeNode<E> createNewNode(E e) {
    return new AVLTreeNode<E>(e);
  }

  @Override /** Wstawianie elementu i — w razie potrzeby — wyważanie drzewa */
  public boolean insert(E e) {
    boolean successful = super.insert(e);
    if (!successful)
      return false; // e znajduje się już w drzewie
    else {
      balancePath(e); // Wyważanie od elementu e do korzenia (gdy jest to konieczne)
    }

    return true; // Element e został wstawiony
  }

  /** Aktualizowanie wysokości danego węzła */
  private void updateHeight(AVLTreeNode<E> node) {
    if (node.left == null && node.right == null) // Węzeł jest liściem
      node.height = 0;
    else if (node.left == null) // Węzeł nie ma lewego poddrzewa
      node.height = 1 + ((AVLTreeNode<E>)(node.right)).height;
    else if (node.right == null) // Węzeł nie ma prawego poddrzewa
      node.height = 1 + ((AVLTreeNode<E>)(node.left)).height;
    else
      node.height = 1 +
        Math.max(((AVLTreeNode<E>)(node.right)).height,
        ((AVLTreeNode<E>)(node.left)).height);
  }

  /** Wyważanie węzłów na ścieżce od podanego węzła
    * do korzenia (gdy jest to konieczne)
   */
  private void balancePath(E e) {
    java.util.ArrayList<TreeNode<E>> path = path(e);
    for (int i = path.size() - 1; i >= 0; i--) {
      AVLTreeNode<E> A = (AVLTreeNode<E>)(path.get(i));
      updateHeight(A);
      AVLTreeNode<E> parentOfA = (A == root) ? null :
        (AVLTreeNode<E>)(path.get(i - 1));

      switch (balanceFactor(A)) {
        case -2:
          if (balanceFactor((AVLTreeNode<E>)A.left) <= 0) {
            balanceLL(A, parentOfA); // Rotacja lewo-lewo
          }
          else {
            balanceLR(A, parentOfA); // Rotacja lewo-prawo
          }
          break;
        case +2:
          if (balanceFactor((AVLTreeNode<E>)A.right) >= 0) {
            balanceRR(A, parentOfA); // Rotacja prawo-prawo
          }
          else {
            balanceRL(A, parentOfA); // Rotacja prawo-lewo
          }
      }
    }
  }

  /** Zwraca współczynnik wyważenia dla węzła */
  private int balanceFactor(AVLTreeNode<E> node) {
    if (node.right == null) // Węzeł nie ma prawego poddrzewa
      return -node.height;
    else if (node.left == null) // Węzeł nie ma lewego poddrzewa
      return +node.height;
    else
      return ((AVLTreeNode<E>)node.right).height -
        ((AVLTreeNode<E>)node.left).height;
  }

  /** Rotacja lewo-lewo (rysunek 26.3) */
  private void balanceLL(TreeNode<E> A, TreeNode<E> parentOfA) {
    TreeNode<E> B = A.left; // A wyższy lewostronnie, B jest wyższy lewostronnie

    if (A == root) {
      root = B;
    }
    else {
      if (parentOfA.left == A) {
        parentOfA.left = B;
      }
      else {
        parentOfA.right = B;
      }
    }

    A.left = B.right; // Ustawianie T2 jako lewego poddrzewa węzła A
    B.right = A; // Ustawianie węzła A jako prawego dziecka węzła B
    updateHeight((AVLTreeNode<E>)A);
    updateHeight((AVLTreeNode<E>)B);
  }

  /** Rotacja lewo-prawo (rysunek 26.5) */
  private void balanceLR(TreeNode<E> A, TreeNode<E> parentOfA) {
    TreeNode<E> B = A.left; // A jest wyższy lewostronnie
    TreeNode<E> C = B.right; // B jest wyższy prawostronnie

    if (A == root) {
      root = C;
    }
    else {
      if (parentOfA.left == A) {
        parentOfA.left = C;
      }
      else {
        parentOfA.right = C;
      }
    }

    A.left = C.right; // Ustawianie T3 jako lewego poddrzewa węzła A
    B.right = C.left; // Ustawianie T2 jako prawego poddrzewa węzła B
    C.left = B;
    C.right = A;

    // Aktualizowanie wysokości
    updateHeight((AVLTreeNode<E>)A);
    updateHeight((AVLTreeNode<E>)B);
    updateHeight((AVLTreeNode<E>)C);
  }

  /** Rotacja prawo-prawo (rysunek 26.4) */
  private void balanceRR(TreeNode<E> A, TreeNode<E> parentOfA) {
    TreeNode<E> B = A.right; // A i B są wyższe prawostronnie

    if (A == root) {
      root = B;
    }
    else {
      if (parentOfA.left == A) {
        parentOfA.left = B;
      }
      else {
        parentOfA.right = B;
      }
    }

    A.right = B.left; // T2 ustawiane jako prawe poddrzewo węzła A
    B.left = A;
    updateHeight((AVLTreeNode<E>)A);
    updateHeight((AVLTreeNode<E>)B);
  }

  /** Rotacja prawo-lewo (rysunek 26.6) */
  private void balanceRL(TreeNode<E> A, TreeNode<E> parentOfA) {
    TreeNode<E> B = A.right; // A jest wyższy prawostronnie
    TreeNode<E> C = B.left; // B jest wyższy lewostronnie

    if (A == root) {
      root = C;
    }
    else {
      if (parentOfA.left == A) {
        parentOfA.left = C;
      }
      else {
        parentOfA.right = C;
      }
    }

    A.right = C.left; // Ustawianie T2 jako prawego poddrzewa węzła A
    B.left = C.right; // Ustawianie T3 jako lewego poddrzewa węzła B
    C.left = A;
    C.right = B;

    // Aktualizowanie wysokości
    updateHeight((AVLTreeNode<E>)A);
    updateHeight((AVLTreeNode<E>)B);
    updateHeight((AVLTreeNode<E>)C);
  }

  @Override /** Usuwa element z drzewa binarnego.
   * Zwraca true po udanym usunięciu elementu.
   * Zwraca false, jeśli elementu nie ma w drzewie */
  public boolean delete(E element) {
    if (root == null)
      return false; // Elementu nie ma w drzewie

    // Znajdowanie usuwanego węzła i jego rodzica
    TreeNode<E> parent = null;
    TreeNode<E> current = root;
    while (current != null) {
      if (c.compare(element, current.element) < 0) {
        parent = current;
        current = current.left;
      }
      else if (c.compare(element, current.element) > 0) {
        parent = current;
        current = current.right;
      }
      else
        break; // Element znajduje się w drzewie wskazywanym przez current
    }

    if (current == null)
      return false; // Elementu nie ma w drzewie

    // Przypadek 1. Węzeł current nie ma lewych dzieci (rysunek 23.6)
    if (current.left == null) {
      // Łączenie rodzica z prawym dzieckiem węzła current
      if (parent == null) {
        root = current.right;
      }
      else {
        if (c.compare(element, parent.element) < 0)
          parent.left = current.right;
        else
          parent.right = current.right;

        // Wyważanie drzewa, jeśli jest to konieczne
        balancePath(parent.element);
      }
    }
    else {
      // Przypadek 2. Węzeł current ma lewe dziecko.
      // Należy znaleźć największy węzeł lewego poddrzewa
      // węzła current i rodzica tego największego węzła
      TreeNode<E> parentOfRightMost = current;
      TreeNode<E> rightMost = current.left;

      while (rightMost.right != null) {
        parentOfRightMost = rightMost;
        rightMost = rightMost.right; // Przechodzenie w prawo
      }

      // Zastępowanie elementu z węzła current elementem z węzła rightMost
      current.element = rightMost.element;

      // Usuwanie węzła rightMost
      if (parentOfRightMost.right == rightMost)
        parentOfRightMost.right = rightMost.left;
      else
        // Przypadek specjalny: parentOfRightMost to current
        parentOfRightMost.left = rightMost.left;

      // Wyważanie drzewa, jeśli jest to konieczne
      balancePath(parentOfRightMost.element);
    }

    size--;
    return true; // Element został wstawiony
  }

  /** AVLTreeNode to typ TreeNode z polem height */
  protected static class AVLTreeNode<E> extends BST.TreeNode<E> {
    protected int height = 0; // Nowe pole

    public AVLTreeNode(E o) {
      super(o);
    }
  }
}
