文章目录
1.AVL树概念
二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查
找元素相当于在顺序表中搜索元素，效率低下,
所以在此基础上提出解决办法：
当向二叉搜索树中插入新节结点时，如果能保证每个节点的左右子树高度之差的绝对值不超过1即可降低树的高度，从而减少平均搜索长度
AVL树又称平衡二叉搜索树
2. AVL树性质
AVL树的性质：
1.它的左右子树都是AVL树
2.左右子树高度之差(平衡因子)的绝对值不超过1(1/0/-1)
平衡因子=右子树高度-左子树高度
3.AVL树的实现
在实现结构与插入功能时，与二叉搜索树有很多相似的地方 ：二叉搜索树
所以一部分关于二叉搜索树的地方就不详细说了
与二叉搜索树定义结构不同的是，多了一个父节点parent以及平衡因子bf
insert
insert的实现前半部分与二叉搜索树的insert实现大部分相同
parent的右子树连接新节点为例，出while循环后，需要反向链接父节点，而此时的父节点就为刚才记录cur前一个节点的parent
插入情况分析
1.
若新增节点作为parent的右子树即cur==parent->right
parent的平衡因子+1 即 parent->bf++
若新增节点作为parent的左子树即cur==parent->left
parent的平衡因子 -1 即 parent->bf–
3.
若新增节点作为parent的左子树即cur==parent->left
parent的平衡因子-1 即 parent->bf–
若parent的平衡因子等于1或者-1 即第一种与第二种情况，说明parent所在子树变了，需要继续向上更新爷爷节点
为什么需要继续更新？
说明插入前parent的平衡因子为0，插入前左右高度相等，现在一边高1，高度变了
若parent的平衡因子等于2或者-2 ， 说明parent所在子树不平衡，需要以旋转的方式处理子树
若parent的平衡因子等于0， parent所在子树高度不变，就不需要向上更新，插入结束了
为什么插入结束了呢？
插入前parent的平衡因子是-1或者1，插入前一边高一边低，插入节点到矮的那边，高度不变
更新平衡因子
文章出处登录后可见！
