BinaryTree

package br.uefs.ecomp.treeStock.util;

import java.util.Iterator;

/**
 * Classe que implementa uma Árvore AVL.
 *
 * @author Daniel Coelho de Andrade
 */
public class BinaryTree implements IBinaryTree {

    private Node root;

    /**
     * Adiciona um item na árvore chamando o método recursivo.
     *
     * @param item Item a ser adicionado.
     * @throws br.uefs.ecomp.treeStock.util.DadoDuplicadoException
     */
    @Override
    public void inserir(Comparable item) throws DadoDuplicadoException{
        this.root = this.insert(item, root);
    }

    /**
     * Insere um item na ávore.
     *
     * @param item Item a ser removido.
     * @param lRoot Raiz local.
     * @return A raiz da nova árvore.
     */
    private Node insert(Comparable item, Node lRoot) throws DadoDuplicadoException {
        if (lRoot == null) {
            lRoot = new Node(item);
        } else if(item.compareTo(lRoot.getData()) == 0 ){
            throw new DadoDuplicadoException("Dado duplicado");
        }
        else if (item.compareTo(lRoot.getData()) < 0) {
            lRoot.setLeftChild(this.insert(item, lRoot.getLeftChild()));

            int l = this.heigth(lRoot.getLeftChild());
            int r = this.heigth(lRoot.getRightChild());

            if (r - l == -2) {
                if (item.compareTo(lRoot.getData()) < 0) {
                    lRoot = this.rotateLeft(lRoot);
                } else {
                    lRoot = this.doubleRotateLeft(lRoot);
                }
            }
        } else if (item.compareTo(lRoot.getData()) > 0) {
            lRoot.setRightChild(this.insert(item, lRoot.getRightChild()));

            int r = this.heigth(lRoot.getRightChild());
            int l = this.heigth(lRoot.getLeftChild());

            if (r - l == 2) {
                if (item.compareTo(lRoot.getData()) > 0) {
                    lRoot = this.rotateRight(lRoot);
                } else {
                    lRoot = this.doubleRotateRight(lRoot);
                }
            }
        }
        //else ;

        //lRoot.setHeight(max(this.heigth(lRoot.getLeftChild()), this.heigth(lRoot.getRightChild())) + 1);
        return lRoot;
    }

    /**
     * Rotação à esquerda.
     */
    private Node rotateLeft(Node lRoot) {
        Node newRoot = lRoot.getLeftChild();
        lRoot.setLeftChild(newRoot.getRightChild());
        newRoot.setRightChild(lRoot);

        //lRoot.setHeight(this.max(this.heigth(lRoot.getLeftChild()), this.heigth(lRoot.getRightChild())) + 1);
        //newRoot.setHeight(this.max(this.heigth(newRoot.getLeftChild()), this.heigth(newRoot.getRightChild())) + 1);
        return newRoot;
    }

    /**
     * Rotação à direita.
     */
    private Node rotateRight(Node lRoot) {
        Node newRoot = lRoot.getRightChild();
        lRoot.setRightChild(newRoot.getLeftChild());
        newRoot.setLeftChild(lRoot);

        //lRoot.setHeight(this.max(this.heigth(lRoot.getLeftChild()), this.heigth(lRoot.getRightChild())) + 1);
        // newRoot.setHeight(this.max(this.heigth(newRoot.getLeftChild()), this.heigth(newRoot.getRightChild())));
        return newRoot;
    }

    /**
     * Rotação dupla à esquerda. Primeiro rotaciona o filho esquerdo com filho
     * direito, depois o nó lRoot com seu filho esquerdo
     */
    private Node doubleRotateLeft(Node lRoot) {
        lRoot.setLeftChild(this.rotateRight(lRoot.getLeftChild()));

        return this.rotateLeft(lRoot);
    }

    /**
     * Rotação dupla à direita. Primeiro rotaciona o filho direito com filho
     * esquerdo, depois o nó lRoot com seu filho direito
     */
    private Node doubleRotateRight(Node lRoot) {
        lRoot.setRightChild(this.rotateLeft(lRoot.getRightChild()));

        return this.rotateRight(lRoot);
    }

    /**
     * Procura um item na ávore.
     *
     * @param item Item a ser procurado.
     * @return O item procurado.
     * @throws br.uefs.ecomp.treeStock.util.DadoNaoEncontradoException
     */
    @Override
    public Object buscar(Comparable item) throws DadoNaoEncontradoException {
        Node current = root;

        while (current != null) {

            if (current.getData().compareTo(item) == 0) {
                //return current.getData();
                return current.getData();
            }
            if (current.getData().compareTo(item) < 0) {
                current = current.getRightChild();
            } else {
                current = current.getLeftChild();
            }
        }


            throw new DadoNaoEncontradoException("Elemento não existente");

    }

    /**
     * Procura e remove um elemento da árvore.
     *
     * @param item Item a ser removido.
     * @throws br.uefs.ecomp.treeStock.util.DadoNaoEncontradoException
     */
    @Override
    public void remover(Comparable item) throws DadoNaoEncontradoException {
        Node current = root;
        Node parent = current;

        if (root == null) {
            throw new DadoNaoEncontradoException();
        }

        //Procura o elemento a ser removido
        while (current.getData().compareTo(item) != 0) {
            if (current.getData().compareTo(item) < 0) {
                parent = current;
                current = current.getRightChild();
                //isLeftChild = false;
            } else {
                parent = current;
                current = current.getLeftChild();
                //isLeftChild = true;
            }

            if (current == null) {
                throw new DadoNaoEncontradoException("Elemento inexistente");
            }
        }

        //Nó a ser removido é uma folha.
        if (!current.hasLeftChild() && !current.hasRigthChild()) {
            if (current == root) {
                root = null;
            } else if (parent.getLeftChild() == current) {
                parent.setLeftChild(null);
            } else {
                parent.setRightChild(null);
            }
        } //Nó a ser removido só tem filho esquerdo
        else if (current.hasLeftChild() && !current.hasRigthChild()) {
            if (current == root) {
                root = current.getLeftChild();
            } else if (parent.getLeftChild() == current) {
                parent.setLeftChild(current.getLeftChild());
            } else {
                parent.setRightChild(current.getLeftChild());
            }
        } //Nó a ser removido só tem filho direito
        else if (!current.hasLeftChild() && current.hasRigthChild()) {
            if (current == root) {
                root = current.getRightChild();
            } else if (parent.getLeftChild() == current) {
                parent.setLeftChild(current.getRightChild());
            } else {
                parent.setRightChild(current.getRightChild());
            }
        } //Nó a ser removido tem filho direito e filho esquerdo
        else {
            Node sucessor = this.getSucessor(current);

            if (current == root) {
                root = sucessor;
            } else if (parent.getLeftChild() == current) {
                parent.setLeftChild(sucessor);
            } else {
                parent.setRightChild(sucessor);
            }

            sucessor.setLeftChild(current.getLeftChild());
        }
        this.searchAndBalanceInRoute(parent);
    }

    /**
     * Verifica o balanceamento dos ancestrais de um nó excluído. Se algum nó
     * estiver desbalaceado, o balanceia.
     *
     * @param lRoot Raiz local
     */
    private void searchAndBalanceInRoute(Node lRoot) {
        Node current = this.root;
        if (lRoot == null || current == null) {
            return;
        }

        current = this.getParent(lRoot);
        while (current != null) {

            int l = this.heigth(current.getLeftChild());
            int r = this.heigth(current.getRightChild());
            if (r - l == -2) {
                if (lRoot.getData().compareTo(current.getData()) < 0) {
                    current = this.rotateLeft(current);
                } else {
                    current = this.doubleRotateLeft(current);
                }
            } else if (r - l == 2) {
                if (lRoot.getData().compareTo(current.getData()) > 0) {
                    current = this.rotateRight(current);
                } else {
                    current = this.doubleRotateRight(current);
                }
            }
            current = this.getParent(current);
        }
    }

    /**
     * Procura o pai de um nó.
     *
     * @param child Nó que o pai deve ser buscado.
     * @return O pai do nó.
     */
    private Node getParent(Node child) {
        Node current = root;

        while (current != null) {

            if (current.getLeftChild() == child) {
                return current;
            } else if (current.getRightChild() == child) {
                return current;
            }

            if (current.getData().compareTo(child.getData()) < 0) {
                current = current.getRightChild();
            } else {
                current = current.getLeftChild();
            }
        }

        return null;
    }

    /**
     * Procura o sucessor de um nó que será excluido e rearranja os filhos do
     * sucessor e do nó que será excluído.
     *
     * @param delete Nó que será deletado.
     * @return O sucessor do nó que será excluído.
     */
    private Node getSucessor(Node delete) {
        Node sucessor = delete;
        Node sucessorParent = sucessor;
        Node current;

        if (sucessor == null) {
            return null;
        } else {
            current = sucessor.getRightChild();
        }

        while (current != null) {
            sucessorParent = sucessor;
            sucessor = current;
            current = current.getLeftChild();
        }

        if (sucessor != delete.getRightChild()) {
            sucessorParent.setLeftChild(sucessor.getRightChild());
            sucessor.setRightChild(delete.getRightChild());
        }

        return sucessor;
    }

    /**
     * Calcula a altura de um nó
     *
     * @param current Nó que a altura deve ser calculada.
     * @return A altura do nó.
     */
    private int heigth(Node current) {
        if (current == null) {
            return -1;
        }
        if (!current.hasLeftChild() && !current.hasRigthChild()) {
            return 0;
        } else if (current.hasRigthChild()) {
            return 1 + heigth(current.getRightChild());
        } else if (current.hasLeftChild()) {
            return 1 + heigth(current.getLeftChild());
        } else {
            return 1 + this.max(heigth(current.getLeftChild()), heigth(current.getRightChild()));
        }
    }

    /**
     * Calcula o maior número entre dois números.
     *
     * @param a Primeiro número.
     * @param b Segundo número.
     * @return O maior número
     */
    private int max(int a, int b) {
        return a > b ? a : b;
    }

    /**
     * Chama a função recursiva para a contagem dos nós.
     *
     * @return O número de nós da árvore.
     */
    public int countNodes() {
        return this.countNodes(root);
    }

    private int countNodes(Node localRoot) {
        int tam = 0;
        if (localRoot != null) {
            tam = 1 + this.countNodes(localRoot.getLeftChild()) + countNodes(localRoot.getRightChild());
        }
        return tam;
    }

    /**
     *
     * @return Um iterador.
     */
    @Override
    public Iterator iterator() {
        return new inOrderIterator(root);
    }

    public void debug() {
        this.debug(root);
    }

    private void debug(Node lRoot) {
        if (lRoot != null) {
            this.debug(lRoot.getLeftChild());
            System.out.println(this.heigth(lRoot.getRightChild()) - this.heigth(lRoot.getLeftChild()));
            this.debug(lRoot.getRightChild());
        }
    }

    @Override
    public boolean contains(Comparable o) {
        Node current = root;
        while (current != null) {

            if (current.getData().compareTo(o) == 0) {
                return true;
            }
            if (current.getData().compareTo(o) < 0) {
                current = current.getRightChild();
            } else {
                current = current.getLeftChild();
            }
        }
        return false;
    }

}