平衡二叉树

定义

它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

平衡二叉树

对于一般的二叉搜索树（Binary Search Tree），其期望高度（即为一棵平衡树时）为logn，其各操作的时间复杂度（O(logn)）同时也由此而决定。但是，在某些极端的情况下（如在插入的序列是有序的时），二叉搜索树将退化成近似链或链，此时，其操作的时间复杂度将退化成线性的，即O(n)

而平衡二叉树在插入的时候，通过左旋/右旋的方式来保证整颗二叉树的高度不会有太大的差别，从而保证高效的查询效率，时间复杂度保持在O(logN).

左旋

Pivot节点左旋

过程：

1. 将P节点所在右节点的左子树L接到P节点的右子树R（也就是将Y节点的b子树拼接到Pivot的右子树），修改左子树L的parent以及P节点的右子树指向
2. 将P节点所在右节点的Parent指向P节点的Parent（将Pivot节点的父节点拼接到Y节点）
3. 如果P为根节点的话，则替换根节点，如果P节点为父节点的左子树/右子树，则将父节点的左子树/右子树拼接原P节点的右子树R（将P节点的左子树指向Y）
4. 将原P节点的左子树拼接P节点，并且将P节点的父节点指向替换后的P节点（将Y的左子树拼接到Pivot，并且将Pivot的父节点拼接到Y）

左旋的代码:

    /** 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;
        }
    }

右旋

Pivot节点右旋

过程：

1. 将P节点所在左节点的右子树R接到P节点的左子树R（也就是将Y节点的c子树拼接到Pivot的左子树），修改右子树L的parent以及P节点的左子树指向
2. 将P节点所在左节点的Parent指向P节点的Parent（将Pivot节点的父节点拼接到Y节点）
3. 如果P为根节点的话，则替换根节点，如果P节点为父节点的左子树/右子树，则将父节点的左子树/右子树拼接原P节点的右子树R（将P的右子树指向Y）
4. 将原P节点的右子树拼接P节点，并且将P节点的父节点指向替换后的P节点（将Y的右子树拼接到Pivot，并且将Pivot的父节点拼接到Y）

    /** 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;
        }
    }

常见的不完全平衡二叉树

AVL树
红黑树