在说AVL树的概念之前，我们需要清楚二茬搜索树的概念。对于二叉搜索树，我们知道它可以降低查找速率，但是如果一个二叉搜索树退化成一棵只剩单支的搜索树，此时的查找速率就相当于顺序表中查找元素，效率变低，时间复杂度由原来的O（logN）变为O（N）。
此时就有了AVL（高度平衡二叉搜索树），从它的名字就能知道它也是一棵二叉搜索树，只是它在插入元素的时候，每插入一个新节点的时候就会调整整棵树的结构，从而来保证这课搜索树的平衡，即每一个节点的左右子树高度差的绝对值不超过1.
那么AVL树的概念就可以总结如下：
满足以下性质的二叉搜索树：
1、左右子树都是AVL树
2、左右子树的高度之差的绝对值不超过1
那么对于像这样的AVL树，如果它有n个节点，则它的高度可以保持在log(n),那么它的平均搜索时间复杂度也就是O(log(n)了。
================================================================
AVL树的插入1、平衡因子
AVL树也是一棵二叉搜索树，所以它的插入是和二叉搜索树的插入操作类似的，只是需要加上调整高度的操作，那么就需要在节点的那个结构体类型中加一个用来反应这个节点的左右孩子高度的变量，平衡因子bf。
定义bf的值等于节点右孩子的高度减去左孩子的高度。如果节点的左右孩子高度相等,则bf等于0；如果左孩子比右孩子高度大1，则bf取-1；如果右孩子高度比左孩子高度大1，则bf取1.那么如果不是上面的这三种情况，就不满足AVL树的定义了，即出现bf的绝对值大于1的时候就要进行高度调整了，所以就是当bf等与2或者-2的时候就要进行平衡化。
那么当给一棵本来就平衡的AVL树中插入一个新节点P的时候，从节点P到根节点的路径上，每个节点为根的子树的高度都可能增加1，即平衡因子发生改变，所以执行一次插入操作后，都需要沿路径向根节点回溯，修改各节点的平衡因子，而如果遇到了哪一个节点的bf变成2或-2的时候就要进行平衡化处理，即调整棵树的高度。
2、节点类型的结构体
我们已经知道在结构体中需要加一个变量 bf，而且我们在修改bf的时候是需要回溯的，所以如果我们还存放了每个节点的父节点就比较方便了，那么可以设计如下的节点结构体类型：
template<class K> struct AVLTreeNode { K _key; int _bf; AVLTreeNode<K, V>* _left; AVLTreeNode<K, V>* _right; AVLTreeNode<K, V>* _parent; AVLTreeNode(const K& key, const V& value) :_key(key), _bf(0), _left(NULL), _right(NULL), _parent(NULL) {} };
3、平衡化处理
在前面已经说了当更新到某个节点的平衡因子变成-2或者2的时候就需要进行平衡化处理，我们在AVL树中的平衡化处理采用的是旋转。对于平衡化处理中的旋转分为以下几种情况：
》左单旋：
》右单旋
》左右双旋
》右左双旋
下面是对于上述四种情况的图解：
》【左单旋】当前节点较高右子树的右侧插入一个新节点，该子树高度增加1导致节点平衡因子从1变为变为2而不平衡
》【右单旋】当前节点较高的左子树左侧插入一个新节点，该子树的高度增加1,导致该节点的平衡因子从-1变为-2而不平衡