数据结构：查找（4）|| 平衡二叉树
在介绍平衡二叉树之前，应该先了解平衡因子的概念，平衡因子定义为左子树深度减去右子树深度，这个值的绝对值越大，非常容易理解它就对应着越不平衡的情况。一棵平衡的二叉树的平衡因子只能是1，0，-1
如何构建一棵平衡二叉树呢？
对一棵平衡的二叉树进行插入操作，插入后，可能导致不平衡，对不平衡的二叉树应该进行旋转操作，将其旋转为平衡二叉树。平衡二叉树应该具有二叉树的性质的同时满足平衡条件。
如何进行旋转操作？
旋转操作实际上是对不平衡部分进行再调整的过程。
是对二叉树的局部重排。
书上将旋转操作划分为4种情况，并分别用了几个看不懂的图和介绍来试图让我们搞懂，我重新画了一个图，介绍在插入C结点后需要进行局部调整时如何进行旋转。
如图黄色框区域，需要进行局部调整
局部调整由排列组合，共有以下四种情况
有了以上的理论基础我们就可以写出
在平衡二叉树上插入新元素e的递归算法
①（创建新树，递归出口1）若原二叉树为空树，则插入结点为根节点，树的深度加1
②（查找存在，递归出口2）若e的关键字和根节点的关键字相同，停止插入
③（查找不存在，执行插入，递归出口3）插入
③.① 插入过程，需要更新结点的平衡因子，深度出现异常进行旋转
④（递归入口）进入左子树或右子树，在左/右子树插入C
有了以上的讲解，写出想要的代码就不是什么难事啦~
挖坑：
接下来一周，将尽量完成B树、键树、哈希表
考试周期间对数据结构进行系统复习时，将补上图、内外排序部分的内容