protected void rightRotate(TreeNode<K, D> nd) {
        TreeNode<K, D> nd2 = nd.left;
        if (isNil(nd2)) {
            return; // do nothing
        }
        //turn nd2's right subtree into nd's left subtree
        nd.left = nd2.right;
        if (!isNil(nd2.right)) {
            nd2.right.parent = nd;
        }
        //link nd's parent to nd2
        TreeNode<K, D> px = nd.parent;
        nd2.parent = px;
        if (isNil(px)) {
            this.root = nd2;
        } else {
            if (nd == px.left) {
                px.left = nd2;
            } else {
                px.right = nd2;
            }
        }
        //put nd on nd2's right
        nd2.right = nd;
        nd.parent = nd2;
    }