目录
平衡二叉树
- 平衡二叉树是对二叉排序树的一种改进
- 二叉排序树：二叉树中的任何一个节点，它的左子树中所有的节点都比该节点要小，它的右子树中所有的节点都比该节点要大。（注意二叉排序树中应尽量避免重复的值，如果有重复的值，可以选择不插入，或者添加一个属性记录该值出现的次数，否则查找和删除的时候回出现麻烦）
- 对于排序二叉树而言，如果输入的数组是一个有序的数列，那么最后生成的二叉树的结构会产生不平衡的情况（即所有节点都在树的一边），例如根据数组{1,2,3,4,5,6}，创建一个二叉树，最终生成树的结构会如下图所示：
- 平衡二叉树的特点：
- 平衡二叉树的左右两个子树的高度差的绝对值不超过1
- 平衡二叉树的左右两个子树都是平衡二叉树
- 平衡二叉树同时也是一颗二叉排序树
AVL树的左旋转
- 当二叉树的右子树的高度大于左子树，并且高度差大于1时，需要对二叉树进行左旋转
- 基本思想：
- 将根节点node 1的右子节点node 2作为新的根节点
- 原来根节点node 1的右指针指向node 2原来的左子树
- 新的根节点node 2的左指针指向原来的根节点node 1
- 实际操作时，需要新建一个节点来作为中介（即下图中的newNode）
- 左旋转后，新二叉树左右子树的高度
- 新二叉树的左子树的高度：转换前node 2左子树的高度+1
- 新二叉树右子树的高度：转换前node 2右子树的高度
AVL树的右旋转
- 当二叉树的左子树的高度大于右子树的高度时，并且高度差大于1时，需要对二叉树进行右旋转
- 右旋转的思路和步骤与左旋转很相似，只不过将左右方向互换了一下
- 左旋转后，新二叉树左右子树的高度
- 新二叉树的左子树的高度：转换前node 2左子树的高度
- 新二叉树右子树的高度：转换前node 2右子树的高度+1
- 当构建二叉排序树时，每向二叉树中添加一个数，都要比较一下左右子树的高度，如果左子树高度大于右子树并且高度差大于1时，那么就对二叉树进行右旋转，反之就对二叉树进行左旋转
AVL树的双旋转
- 在某些情况下，单旋转不能完成二叉树的转换，比如数列{10,11,7,6,8,9}，按照上面的思路进行平衡二叉树的转换时，其左右子树的高度差仍然大于1，具体的原因如下：
- 由于二叉树的左子树的高度比右子树的高度大2，因此需要进行右旋转。旋转的实质其实就是将根节点node 1的左节点node 2的右子树挂在node 1的左节点上，然后node 2作为新的根节点，其右指针指向原来的根节点node 1。因此转换后，新二叉树左右子树的高度差为：（转换前node 2右子树的高度+1）- 转换前node 2左子树的高度。但是由于转换前node 2的右子树就比它的左子树高度大，因此转换后左右子树的高度差一定大于1。
- 解决方法：在每次添加元素，进行左旋转或右旋转调整二叉树时，添加一个条件：
- 如果需要进行左旋转，先判断右节点node 2的左子树的高度是否大于其右子树的高度，如果大于，则需要先对以node 2为根节点的子树进行右旋转，然后在进行左旋转
- 如果需要进行右旋转，先判断左节点node 2的右节点的高度是否大于其左节点的高度，如果大于，需要先对以node 2为根节点的子树进行左旋转，然后在进行右旋转