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

        nd2.parent = nd.parent;
        if (isNil(nd.parent)) {
            this.root = nd2;
        } else {
            if (nd == nd.parent.left) {
                nd.parent.left = nd2;
            } else {
                nd.parent.right = nd2;
            }
        }
        //put nd on nd2's left
        nd2.setLeftChild(nd);
        nd.setParent(nd2);
    }