（十四）平衡二叉树

基本介绍

1. 平衡二叉树也叫平衡二叉搜索树（Self-balancing binary search tree）又被称为 AVL 树， 可以保证查询效率较高。
2. 具有以下特点：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。
   一般情况下，假设由于在二叉排序树上插入结点而失去平衡的最小子树根节点的指针为a（即a是离插入结点最近，且平衡因子绝对值超过1的祖先结点），则失去平衡后进行调整的规律4种
   （1）单向右旋平衡处理：由于在a的左子树根结点的左子树上插入结点，a的平衡因子由1增至2，使得以a为根的子树失去平衡，需要进行一次向右的顺时针旋转。
   （2）单向左旋平衡处理：由于在a的右子树根结点的右子树上插入结点，a的平衡因子由-1变为-2，使得以a为根的子树失去平衡，需要进行一次向左的逆时针旋转。
   （3）双向旋转（先左后右）平衡处理：由于在a的左子树根结点的右子树上插入结点，a的平衡因子由1增至2，使得以a为根的子树失去平衡，需要进行两次旋转（先左旋后右旋）。
   
   （4）双向旋转（先右后左）平衡处理：由于在a的右子树根结点的左子树上插入结点，a的平衡因子由-1变为-2，使得以a为根的子树失去平衡，需要进行两次旋转（先右旋后左旋）。