Заполнение моего AVLTree занимает очень много времени

Question

В настоящее время требуется приблизительно 28 секунд для заполнения моего AVLTree 11000 объектов, что слишком медленно, и когда я пытаюсь заполнить дерево 250000 объектами, программа никогда не завершает свой запуск.

В настоящее времяЯ не совсем уверен, что заставляет его работать так медленно.Может быть, я использую слишком много рекурсии?И если да, то как я могу использовать меньше?

public class AVLTree<K, V> implements AVLTreeI<K, V> {

    class Node<K, V> {

        K key;
        V value;
        Node<K, V> leftChild;
        Node<K, V> rightChild;
        Node<K, V> parent;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
            leftChild = rightChild = parent = null;
        }
    }

    private Node<K, V> root;
    private int currentSize;

    public AVLTree() {
        root = null;
        currentSize = 0;
    }

    public void add(K key, V value) {
        Node<K, V> node = new Node<K, V>(key, value);

        if (root == null) {
            root = node;
            currentSize++;
            return;
        }

        add(root, node);
    }

    private void add(Node<K, V> parent, Node<K, V> newNode) {
        if (((Comparable<K>) newNode.key).compareTo(parent.key) > 0) {
            if (parent.rightChild == null) {
                parent.rightChild = newNode;
                newNode.parent = parent;
                currentSize++;
            } else {
                add(parent.rightChild, newNode);
            }
        } else {
            if (parent.leftChild == null) {
                parent.leftChild = newNode;
                newNode.parent = parent;
                currentSize++;
            } else {
                add(parent.leftChild, newNode);
            }
        }

        checkBalance(newNode);
    }

    public int height() {
        if (root == null) {
            return 0;
        }

        return height(root) - 1;
    }

    private int height(Node<K, V> node) {
        if (node == null) {
            return 0;
        }

        int leftHeight = height(node.leftChild) + 1;
        int rightHeight = height(node.rightChild) + 1;

        if (leftHeight > rightHeight) {
            return leftHeight;
        }

        return rightHeight;
    }

    public void checkBalance(Node<K, V> node) {
        if ((height(node.leftChild) - height(node.rightChild) > 1)
                || (height(node.leftChild) - height(node.rightChild) < -1)) {
            rotate(node);
        }

        if (node.parent == null) {
            return;
        }

        checkBalance(node.parent);
    }

    public void rotate(Node<K, V> node) {
        if (height(node.leftChild) - height(node.rightChild) > 1) {
            if (height(node.leftChild.leftChild)
                    > height(node.leftChild.rightChild)) {
                node = rightRotate(node);
            } else {
                node = leftRightRotate(node);
            }
        } else {
            if (height(node.rightChild.rightChild)
                    > height(node.rightChild.leftChild)) {
                node = leftRotate(node);
            } else {
                node = rightLeftRotate(node);
            }
        }

        if (node.parent == null) {
            root = node;
        }
    }

    public Node<K, V> leftRotate(Node<K, V> node) {
        Node<K, V> tmp = node.rightChild;
        Node<K, V> rightLeftChild = null;

        if (tmp.leftChild != null) {
            rightLeftChild = node.rightChild.leftChild;
        }

        node.rightChild = tmp.leftChild;
        tmp.leftChild = node;

        if (rightLeftChild != null) {
            tmp.leftChild.rightChild = rightLeftChild;
            tmp.leftChild.rightChild.parent = tmp.leftChild;
        }

        tmp.parent = node.parent;
        tmp.leftChild.parent = tmp;

        if (tmp.parent != null) {
            if (tmp.parent.leftChild == node) {
                tmp.parent.leftChild = tmp;
            }

            if (tmp.parent.rightChild == node) {
                tmp.parent.rightChild = tmp;
            }
        }

        return tmp;
    }

    public Node<K, V> rightRotate(Node<K, V> node) {
        Node<K, V> tmp = node.leftChild;
        Node<K, V> leftRightChild = null;

        if (tmp.rightChild != null) {
            leftRightChild = node.leftChild.rightChild;
        }

        node.leftChild = tmp.rightChild;
        tmp.rightChild = node;

        if (leftRightChild != null) {
            tmp.rightChild.leftChild = leftRightChild;
            tmp.rightChild.leftChild.parent = tmp.rightChild;
        }

        tmp.parent = node.parent;
        tmp.rightChild.parent = tmp;

        if (tmp.parent != null) {
            if (tmp.parent.leftChild == node) {
                tmp.parent.leftChild = tmp;
            }

            if (tmp.parent.rightChild == node) {
                tmp.parent.rightChild = tmp;
            }
        }

        return tmp;
    }

    public Node<K, V> rightLeftRotate(Node<K, V> node) {
        node.rightChild = rightRotate(node.rightChild);
        return leftRotate(node);
    }

    public Node<K, V> leftRightRotate(Node<K, V> node) {
        node.leftChild = leftRotate(node.leftChild);
        return rightRotate(node);
    }
}