public void insert(K key, D data) {

        TreeNode<K, D> parent = NIL;
        TreeNode<K, D> pointer = getRoot();

        //find insertion point
        while (!isNil(pointer)) {
            parent = pointer;
            int cmp = this.comparator.compare(key, pointer.getKey());
            if (cmp < 0) {
                pointer = pointer.left;
            } else if (cmp > 0) {
                pointer = pointer.right;
            } else {
                //throw exception when duplicate key is entered
                throw new IllegalArgumentException("Entry is key " + key + " already present in tree.");
            }
        }
        //create new node
        TreeNode<K, D> newNode = new TreeNode<K, D>(key, data, parent, NIL);
        if (isNil(parent)) { //tree was empty
            this.root = newNode;
        } else {
            if (this.comparator.compare(key, parent.getKey()) < 0) {
                parent.left = newNode;
            } else {
                parent.right = newNode;
            }
        }
        insertFix(newNode);
    }