protected void insertFix(TreeNode<K, D> nd) {
        while (nd.parent.color == RED) {
            if (nd.parent == nd.parent.parent.left) {
                TreeNode<K, D> nd2 = nd.parent.parent.right;
                if (nd2.color == RED) {
                    nd.parent.color = BLACK;
                    nd2.color = BLACK;
                    nd.parent.parent.color = RED;
                    nd = nd.parent.parent;
                } else {
                    if (nd == nd.parent.right) {
                        nd = nd.parent;
                        leftRotate(nd);
                    }
                    nd.parent.color = BLACK;
                    nd.parent.parent.color = RED;
                    rightRotate(nd.parent.parent);
                }
            } else {
                TreeNode<K, D> nd2 = nd.parent.parent.left;
                if (nd2.color == RED) {
                    nd.parent.color = BLACK;
                    nd2.color = BLACK;
                    nd.parent.parent.color = RED;
                    nd = nd.parent.parent;
                } else {
                    if (nd == nd.parent.left) {
                        nd = nd.parent;
                        rightRotate(nd);
                    }
                    nd.parent.color = BLACK;
                    nd.parent.parent.color = RED;
                    leftRotate(nd.parent.parent);
                }
            }
        }
        getRoot().setColor(BLACK);
    }