Métodos dúvida Roteiro 12

AVLTree>>>>>>>>>>>>>>>>>>>>>>>>

 @Override
    public void insert(T value) {
        recursiveInsert(this.root, value);
    };

    private void recursiveInsert(BSTNode<T> node, T element) {
        if (node.isEmpty()) {
            // cria um node sentinela cujo apontador pai é o node dado
            BSTNode<T> nil = new BSTNode<T>();
            nil.setParent(node);

            node.setData(element);
            node.setLeft(nil);
            node.setRight(nil);

        } else {
            if (element.compareTo(node.getData()) < 0) recursiveInsert((BSTNode<T>) node.getLeft(), element);
            else if (element.compareTo(node.getData()) >= 0) recursiveInsert((BSTNode<T>) node.getRight(), element);

            rebalance(node);
        }
    }

 //AUXILIARY
    protected int calculateBalance(BSTNode<T> node) {
        return height((BSTNode<T>) node.getLeft()) - height((BSTNode<T>) node.getRight());
    }

    //AUXILIARY
    protected void rebalance(BSTNode<T> node) {
        int balance = calculateBalance(node);

        // se o nó pesa pra esquerda
        if (balance > 1) {
            int leftBalance = calculateBalance((BSTNode<T>) node.getLeft());

            if (leftBalance >= 0) rightRotation(node);

            else if (leftBalance < 0) {
                leftRotation((BSTNode<T>) node.getLeft());
                rightRotation(node);
            }

        // se o nó pesa pra direita
        } else if (balance < 1) {
            int rightBalance = calculateBalance((BSTNode<T>) node.getRight());

            if (rightBalance <= 0) leftRotation(node);

            else if (rightBalance > 0) {
                rightRotation((BSTNode<T>) node.getRight());
                leftRotation(node);
            }
        }
    }



BST>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

/**
     * This method is already implemented using recursion. You must understand how it work and
     * use similar idea with the other methods.
     */
    @Override
    public int size() {
        return size(root);
    }
    private int size(BSTNode<T> node){
        int result = 0;
        //base case means doing nothing (return 0)
        if(!node.isEmpty()){ //inductive case
            result = 1 + size((BSTNode<T>)node.getLeft()) + size((BSTNode<T>)node.getRight());
        }
        return result;
    }