平衡二叉树

    /** From CLR */
    private void rotateLeft(TreeMapEntry<K,V> p) {
        if (p != null) {
            //  获取要旋转节点的右子树节点（即r为上图的Y节点）
            TreeMapEntry<K,V> r = p.right;
            //  将右子树节点的左子树拼接到要旋转节点的右子树上（即将b拼接到Pivot节点的右子树上）
            p.right = r.left;
            //  如果右子树节点的左子树节点不为空的话，则更新该节点的父节点(即将b的父节点指向Pivot节点)
            if (r.left != null)
                r.left.parent = p;
            //  修改右子树节点父节点指向要旋转节点的父节点(将Y节点的Parent指向P节点)
            r.parent = p.parent;
            //  如果要旋转的节点原来没有Parent的话，那就意味着它是根节点，则更新根节点
            if (p.parent == null)
                root = r;
            else if (p.parent.left == p)
            //  如果旋转节点是Parent的左子树的话，则将旋转节点的右子树节点更新到Parent的左子树上(即将P的左子树从原来的指向pivot更新为Y)
                p.parent.left = r;
            else
            //  如果是右子树的话，则将旋转节点的右子树节点更新到Parent的右子树上
                p.parent.right = r;
            //  将旋转节点更新到该节点原右子树的左子树上(即将pivot拼接到Y的左子树上)
            r.left = p;
            //  更新旋转节点的父节点为该节点原右子树(将Pivot节点的parent更新成Y节点)
            p.parent = r;
        }
    }

    /** From CLR */
    /** 与左旋逻辑一致，替换即可  **/
    private void rotateRight(TreeMapEntry<K,V> p) {
        if (p != null) {
            TreeMapEntry<K,V> l = p.left;
            p.left = l.right;
            if (l.right != null) l.right.parent = p;
            l.parent = p.parent;
            if (p.parent == null)
                root = l;
            else if (p.parent.right == p)
                p.parent.right = l;
            else p.parent.left = l;
            l.right = p;
            p.parent = l;
        }
    }