AVLTP5E8

//
//Created by Julio Tentor <jtentor@fi.unju.edu.ar>
//

//Código basado en el capítulo 14 de
//Joyanes Aguilar, Luis and Zahonero Martínez, Ignacio. 2008. Estructuras de datos en Java
//https://drive.google.com/file/d/0B7lAHg81F3X_c2g5c2txQ1g5TTQ/view

public class AVLTree<ELEMENT extends Comparable<ELEMENT>> {

 protected class AVLNode<ELEMENT> {
     public ELEMENT item;
     public AVLNode<ELEMENT> left;
     public AVLNode<ELEMENT> right;
     public int balance;

     public AVLNode() {
         this(null, null, null, 0);
     }
     public AVLNode(ELEMENT item) {
         this(item, null, null, 0);
     }
     public AVLNode(ELEMENT item, AVLNode<ELEMENT> left, AVLNode<ELEMENT> right, int balance) {
         this.item = item;
         this.left = left;
         this.right = right;
         this.balance = balance;
     }

     @Override
     public String toString() {
         return this.item.toString();
     }

     // Método para propósitos académicos
     public void Visit() {
         System.out.printf("%s ", this.item.toString());
     }
 }



 protected AVLNode<ELEMENT> root;
 // atributo para propositos académicos
 protected boolean verbose;
 public int countSimple = 0;
 public int countDoble = 0;

 public AVLTree() {
     this.root = null;
     this.verbose = false;
 }

 // método para propósitos académicos
 public boolean setVerbose(boolean verbose) {
     this.verbose = verbose;
     return this.verbose;
 }


 @Override
 public String toString() {
     return toString(this.root);
 }
 protected String toString(AVLNode<ELEMENT> root) {
     StringBuilder sb = new StringBuilder();
     if (root != null) {
         sb.append(root.item.toString());
         //sb.append("[" + root.balance.toString() + "]");
         sb.append((root.balance < 0) ? "[-]" : (root.balance == 0) ? "[.]" : "[+]" );
         if (root.left != null) {
             sb.append("(" + toString(root.left));
             if (root.right != null) {
                 sb.append(", " + toString(root.right));
             }
             sb.append(")");
         } else {
             if (root.right != null) {
                 sb.append("(, " + toString(root.right) + ")");
             }
         }
     }
     return sb.toString();
 }


 //region Métodos para recorrer el árbol
 public void PreOrder() {
     PreOrder(this.root);
 }
 protected void PreOrder(AVLNode<ELEMENT> root) {
     if (root != null) {
         root.Visit();
         PreOrder(root.left);
         PreOrder(root.right);
     }
 }

 public void InOrder() {
     InOrder(this.root);
 }
 protected void InOrder(AVLNode<ELEMENT> root) {
     if (root != null) {
         InOrder(root.left);
         root.Visit();
         InOrder(root.right);
     }
 }

 public void PostOrder() {
     PostOrder(this.root);
 }
 protected void PostOrder(AVLNode<ELEMENT> root) {
     if (root != null) {
         PostOrder(root.left);
         PostOrder(root.right);
         root.Visit();
     }
 }

 public void DescendingOrder() {
     DescendingOrder(this.root);
 }
 protected void DescendingOrder(AVLNode<ELEMENT> root) {
     if (root != null) {
         DescendingOrder(root.right);
         root.Visit();
         DescendingOrder(root.left);
     }
 }
 //endregion

 //region Métodos para contar elementos del árbol
 public int NodeCount() {
     return NodeCount(this.root);
 }
 protected int NodeCount(AVLNode<ELEMENT> root) {
     if (root != null) {
         return 1 + NodeCount(root.left) + NodeCount(root.right);
     }
     return 0;
 }


 public int LeafCount() { // numero de hojas
     return LeafCount(this.root);
 }
 protected int LeafCount(AVLNode<ELEMENT> root) {
     if (root != null) {
         if ( (root.left == null) && (root.right == null) ) {
             return 1;
         } else {
             return LeafCount(root.left) + LeafCount(root.right);
         }
     }
     return 0;
 }


 public int InternalCount() { // numero de nodos internos
     return InternalCount(this.root);
 }
 protected int InternalCount(AVLNode<ELEMENT> root) {
     if (root != null) {
         if ( (root.left == null) && (root.right == null) ) {
             return 0;
         } else {
             return 1 + InternalCount(root.left) + InternalCount(root.right);
         }
     }
     return 0;
 }


 public int MaxLevel() { //nivel maximo
     return MaxLevel(this.root);
 }
 protected int MaxLevel(AVLNode<ELEMENT> root) {
     if (root != null) {
         if ( (root.left != null) || (root.right != null) ) {
             int leftLevel = MaxLevel(root.left);
             int rightLevel = MaxLevel(root.right);
             return 1 + Math.max(leftLevel, rightLevel);
         }
         return 0;
     }
     return -1;
 }

 public int Height() { // altura del arbol
     return MaxLevel() + 1;
 }
 //endregion

 //region Métodos para buscar
 public boolean contains(ELEMENT item) {
     return contains(this.root, item);
 }
 private boolean contains(AVLNode<ELEMENT> root, ELEMENT item) {
     if (root == null) {
         return false;
     }
     if (item.compareTo(root.item) < 0) {
         return contains(root.left, item);
     }
     if (item.compareTo(root.item) > 0) {
         return contains(root.right, item);
     }
     return true;
 }
 //endregion

 //region Métodos para agregar elementos al árbol

 public void add(ELEMENT item) {
     if (this.verbose) {
         System.out.printf("Agrega %s", item.toString());
     }

     boolean[] change = { false };
     this.root = addAVL(this.root, item, change);

     if (this.verbose) {
         System.out.printf("\t %s\n", this.toString());
     }
 }

 private AVLNode<ELEMENT> addAVL(AVLNode<ELEMENT> root, ELEMENT item, boolean[] change) {
     AVLNode<ELEMENT> n1;

     if (root == null) {
         root = new AVLNode<ELEMENT>(item);
         change[0] = true; // cambia el balance
         return root;
     }

     if (item.compareTo(root.item) < 0) { // el nuevo elemento es menor
         root.left = addAVL(root.left, item, change); // agrega por la izquierda
         if (change[0]) { // cambió el balance?
             switch (root.balance) { // balance = hD - hI
                 case 1: // antes izquierda < derecha
                     root.balance = 0; // después izquierda == derecha
                     change[0] = false; // balance ajustado
                     break;
                 case 0: // antes izquierda == derecha
                     root.balance = -1; // después izquierda > derecha
                     break;
                 case -1: // antes izquierda > derecha
                     n1 = root.left;
                     if (n1.balance == -1) { // izquierda izquierda es mayor
                         root = leftleftRotation(root, n1); // LR rotación doble
                     } else {
                         root = leftrightRotation(root, n1); // LL rotación simple
                     }
                     change[0] = false; // balance ajustado
                     break;
             }
         }
         return root;
     }

     if (item.compareTo(root.item) > 0) { // el nuevo elemento es mayor
         root.right = addAVL(root.right, item, change); // agregar por la derecha
         if (change[0]) { // cambió el balance?
             switch (root.balance) { // balance = hD - hI
                 case -1: // antes izquierda > derecha
                     root.balance = 0; // ahora izquierda == derecha
                     change[0] = false; // balance ajustado
                     break;
                 case 0: // antes izquierda == derecha
                     root.balance = 1; // ahora izquierda < derecha
                     break;
                 case 1: // antes izquierda < derecha
                     n1 = root.right;
                     if (n1.balance == 1) { // derecha derecha es mayor
                         root = rightrightRotation(root, n1); // RR rotación simple
                     } else {
                         root = rightleftRotation(root, n1); // RL rotación doble
                     }
                     change[0] = false; // balance ajustado
                     break;
             }
         }
         return root;
     }
     throw new RuntimeException("Claves repetidas");
 }
 //endregion

 //region Rotaciones LL LR RR RL
 private AVLNode<ELEMENT> leftleftRotation(AVLNode<ELEMENT> n, AVLNode<ELEMENT> n1) {
     if (this.verbose) {
         System.out.print(" LL ");
         ++countSimple;
     }

     n.left = n1.right;
     n1.right = n;
     if (n1.balance == -1) {
         n.balance = 0;
         n1.balance = 0;
     } else {
         n.balance = -1;
         n1.balance = 1;
     }
     return n1;
 }

 private AVLNode<ELEMENT> leftrightRotation(AVLNode<ELEMENT> n, AVLNode<ELEMENT> n1) {
     if (this.verbose) {
         System.out.print(" LR ");
         ++countDoble;
     }

     AVLNode<ELEMENT> n2;
     n2 = n1.right;
     n.left = n2.right;
     n2.right = n;
     n1.right = n2.left;
     n2.left = n1;
     n1.balance = (n2.balance == 1) ? -1 : 0;
     n.balance = (n2.balance == -1) ? 1 : 0;
     n2.balance = 0;
     return n2;
 }

 private AVLNode<ELEMENT> rightrightRotation(AVLNode<ELEMENT> n, AVLNode<ELEMENT> n1) {
     if (this.verbose) {
         System.out.print(" RR ");
         ++countSimple;
     }

     n.right = n1.left;
     n1.left = n;
     if (n1.balance == 1) {
         n.balance = 0;
         n1.balance = 0;
     } else {
         n.balance = 1;
         n1.balance = -1;
     }
     return n1;
 }


 private AVLNode<ELEMENT> rightleftRotation(AVLNode<ELEMENT> n, AVLNode<ELEMENT> n1) {
     if (this.verbose) {
         System.out.print(" RL ");
         ++countDoble;
     }

     AVLNode<ELEMENT> n2;
     n2 = n1.left;
     n.right = n2.left;
     n2.left = n;
     n1.left = n2.right;
     n2.right = n1;
     n.balance = (n2.balance == 1) ? -1: 0;
     n1.balance = (n2.balance == -1) ? 1 : 0;
     n2.balance = 0;
     return n2;
 }
 //endregion

 //region Métodos para remover elementos

 public void remove(ELEMENT item) {
     if (this.verbose) {
         System.out.printf("Extrae %s", item.toString());
     }

     boolean[] change = { false };
     this.root = removeAVL(this.root, item, change);

     if (this.verbose) {
         System.out.printf("\t %s\n", this.toString());
     }
 }
 private AVLNode<ELEMENT> removeAVL(AVLNode<ELEMENT> root, ELEMENT item, boolean[] change) {

     if (root == null) {
         throw new RuntimeException("No existe");
     }

     if (item.compareTo(root.item) < 0) { // el elemento es menor
         root.left = removeAVL(root.left, item, change); // borrar por la izquierda
         if (change[0]) { // cambió el balance?
             root = leftBalance(root, change); // ajustar el balance izquierdo
         }
         return root;
     }

     if (item.compareTo(root.item) > 0) { // el elemento es mayor
         root.right = removeAVL(root.right, item, change); // borrar por la derecha
         if (change[0]) { // cambió el balance?
             root = rightBalance(root, change); // ajustar el balance derecho
         }
         return root;
     }


     AVLNode<ELEMENT> q;
     q = root;
     if (q.left == null) { // no hay izquierda
         root = q.right; // un descendiente por la derecha u hoja
         change[0] = true; // cambia el balance
     } else {
         if (q.right == null) { // no hay derecha
             root = q.left; // un descendiente por la izquierda
             change[0] = true; // cambia el balance
         } else { // dos descendientes !!!
             root.left = eldestOfMinors(root, root.left, change); // mayor de los menores
             if (change[0]) { // cambió el balance?
                 root = leftBalance(root, change); // ajustar el balance izquierdo
             }
             q = null; // eliminar el nodo
         }
     }
     return root;
 }

 private AVLNode<ELEMENT> eldestOfMinors(AVLNode<ELEMENT> n, AVLNode<ELEMENT> eldest, boolean[] change) {
     if (eldest.right != null) { // hay algo a la derecha
         eldest.right = eldestOfMinors(n, eldest.right, change); // busca el mayor de los menores
         if (change[0]) { // cambió el balance?
             eldest = rightBalance(eldest, change); // ajustar el balance derecho
         }
     } else {
         n.item = eldest.item;
         n = eldest;
         eldest = eldest.left;
         n = null;
         change[0] = true;
     }
     return eldest;
 }

 private AVLNode<ELEMENT> leftBalance(AVLNode<ELEMENT> n, boolean[] change) {
     AVLNode<ELEMENT> n1;
     switch (n.balance) { // balance = hD - hI
         case -1 : // antes izquierda > derecha
             n.balance = 0; // ahora izquierda == derecha
             break;
         case 0 : // antes izquierda == derecha
             n.balance = 1; // ahora izquierda < derecha
             change[0] = false; // balance ajustado
             break;
         case 1 : // antes izquierda < derecha
             n1 = n.right;
             if (n1.balance >= 0) {
                 if (n1.balance == 0) {
                     change[0] = false; // balance ajustado
                 }
                 n = rightrightRotation(n, n1);
             } else {
                 n = rightleftRotation(n, n1);
             }
             break;
     }
     return n;
 }

 private AVLNode<ELEMENT> rightBalance(AVLNode<ELEMENT> n, boolean[] change) {
     AVLNode<ELEMENT> n1;
     switch (n.balance) { // balance = hD - hI
         case -1 : // antes izquiera > derecha
             n1 = n.left;
             if (n1.balance <= 0) {
                 if (n1.balance == 0) {
                     change[0] = false; // balance ajustado
                 }
                 n = leftleftRotation(n, n1);
             } else {
                 n = leftrightRotation(n, n1);
             }
             break;
         case 0 : // antes izquierda == derecha
             n.balance = -1; // ahora izquierda > derecha
             change[0] = false; // balance ajustado
             break;
         case 1 : // antes izquierda < derecha
             n.balance = 0;
             break;
     }
     return n;
 }
 //endregion

}