平衡二叉树中，平衡的意思就是当节点数量固定的时候，左右子树的高度越接近，这棵二叉树就越平衡，相应的高度也就越低。最理想的平衡状态其实就是完全二叉树和满二叉树，它们的高度是最小的。
平衡二叉搜索树，英文名称Balanced Binary Search Tree，经典常见的平衡二叉树有AVL树和红黑树。一般也称它们为自平衡的二叉搜索树。
AVL树中，为了判断其平衡状态，定义了“平衡因子”，它表示某节点的左右子树的高度差。
AVL树的特点是：1、每个节点的平衡因子只可能是1或0或-1（即，绝对值<=1，如果超过1，称之为“失衡”。）也即是每个节点的左右子树高度差不超过1；2、搜索、添加、删除的时间复杂度是O(logN)；3、父节点、非祖先节点，都不可能失衡；4、失衡最坏的情况，可能会导致所有祖先节点都失衡。
要维护平衡状态，必须先找到最初的失衡节点，以及造成失衡的原因。所谓最初的失衡节点，指的是位于二叉搜索树最下方、接近叶子节点的那个失衡节点，一旦解决了这个失衡节点的失衡状态，其祖先节点的失衡状态也就解决了。
区分出造成一棵已经平衡的二叉搜索树失衡的原因，或者说找出新节点最后经过的添加路径（这里所说的最后的路径指的是从失衡节点开始算），总的来说有四种情况：
- 添加路径是右右，从失衡节点g开始，向右先找到右子节点p，再由p向右找到p的右子节点n，给n节点（或其子树）添加了一个节点，造成了失衡；
- 添加路径是左左，从失衡节点g开始，向左先找到左子节点p，再由p向左找到p的左子节点n，给n节点（或其子树）添加了一个节点，造成了失衡；
- 添加路径是左右，从失衡节点g开始，向左找到左子节点p，再由p向右找到p的右子节点n，给节点n（或其子树）添加了一个节点，造成了失衡；
- 添加路径是右左，从失衡节点g开始，向右找到右子节点p，再由p向左找到p的左子节点n，给节点n（或其子树）添加了一个节点，造成了失衡。
还需要理解以下两种操作，是用来将失衡的AVL树再调整为平衡状态的操作：左旋和右旋。
-
左旋：用来解决“右右”原因造成的失衡。具体操作就是，将失衡节点的右子树往左拉，右子节点变成父节点，并把晋升之后多余的左子树出让给降级节点的右子节点。可以结合下图进行理解；左旋.png
-
右旋：用来解决“左左”原因造成的失衡。具体操作就是，将失衡节点的左子树往右拉，左子节点变成父节点，并把晋升之后多余的右子节点出让给降级节点的左子节点。右旋.png
由“左右”原因造成的失衡，以及由“右左”原因造成的失衡，都可以用左旋和右旋来解决：
先左旋后右旋.png
先右旋后左旋.png
