Árbol - AVLTree.java

//
// 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 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() {
        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() {
        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() {
        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() {
        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 ");
        }

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

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

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

        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

}