@Override
    public void insert(T key) {
        Node<T> cursor = null; // y
        Node<T> current = root; // x
        Node<T> newNode = new Node<T>(key, null); // z
        while (current != null && current.getValue() != null) {
            cursor = current;
            try {
                if (newNode.getValue().compareTo(current.getValue()) < 0) {
                    current = (Node<T>) current.getLeftChild();
                } else if (newNode.getValue().compareTo(current.getValue()) > 0) {
                    current = (Node<T>) current.getRightChild();
                }
            } catch (NullPointerException ex) {
                break;
            }
        }

        newNode.setParent(cursor);
        if (cursor == null) {
            root = newNode;
        } else if (newNode.getValue().compareTo(cursor.getValue()) < 0) {
            cursor.setLeftChild(newNode);
            newNode.setParent(cursor);
            reBalance((Node<T>) cursor.getLeftChild());
        } else if (newNode.getValue().compareTo(cursor.getValue()) > 0) {
            cursor.setRightChild(newNode);
            newNode.setParent(cursor);
            reBalance((Node<T>) cursor.getRightChild());
        }

    }