TP5-Ejercicio7-ClaseArbol

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;
    protected boolean verbose;
    protected int contar;

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

    public boolean setVerbose(boolean verbose) {
        this.verbose = verbose;
        return this.verbose;
    }
    public int setContar(int contar){
        this.contar = contar;
        return this.contar;
    }
    public int getContar() {
        return this.contar;
    }


    @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 < 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();
    }



    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,contar);

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

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

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

        if (item.compareTo(root.item) < 0) {
            root.left = addAVL(root.left, item, change,cont); // agrega elementos por la izquierda
            if (change[0]) { // consulta si cambió el balance
                switch (root.balance) {
                    case 1:
                        root.balance = 0;
                        change[0] = false; // se ajusta el balance
                        break;
                    case 0:
                        root.balance = -1;
                        break;
                    case -1:
                        n1 = root.left;
                        if (n1.balance == -1) {
                            root = leftleftRotation(root, n1); // rotación doble
                        } else {
                            root = leftrightRotation(root, n1); // rotación simple
                        }
                        change[0] = false; // se ajusta el balance
                        contar=contar+1;
                        break;
                }
            }
            return root;
        }

        if (item.compareTo(root.item) > 0) {
            root.right = addAVL(root.right, item, change,cont); // agrega elementos por la derecha
            if (change[0]) { // consulta si cambió el balance
                switch (root.balance) {
                    case -1:
                        root.balance = 0;
                        change[0] = false; // se ajusta el balance
                        break;
                    case 0:
                        root.balance = 1;
                        break;
                    case 1:
                        n1 = root.right;
                        if (n1.balance == 1) {
                            root = rightrightRotation(root, n1); // rotación simple
                        } else {
                            root = rightleftRotation(root, n1); // rotación doble
                        }
                        change[0] = false; // se ajusta el balance
                        contar=contar+1;
                        break;
                }
            }
            return root;
        }
        throw new RuntimeException(" ");
    }

    //Rotaciones
    private AVLNode<ELEMENT> leftleftRotation(AVLNode<ELEMENT> n, AVLNode<ELEMENT> n1) {
        if (this.verbose) {
            System.out.print(" con Rotación Simple:Izquierda Izquierda (LL)\n");
        }

        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(" con Rotación Doble: Izquierda Derecha (LR)\n");
        }

        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(" con Rotación Simple: Derecha Derecha (RR)\n");
        }

        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(" con Rotación Doble: Derecha Izquierda (RL)\n");
        }

        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;
    }


}