平衡二叉树（AVL树）
二叉搜索树对于数列{1,2,3,4,5,6}，左子树全部为空，从形式上看更像是一个单链表
不能够发挥二叉搜索树的优势，为了解决这个问题，引入平衡二叉树（AVL树）
平衡二叉树基本介绍：
- 平衡二叉树也叫平衡二叉搜索树，又被称为AVL树，是对二叉搜索树的优化，可以保证查询效率较高
- 具有以下特点，它是一颗空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一颗平衡二叉树。平衡二叉树的实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。
应用案例-单旋转（左旋转）
要求：给你一个数列，创建出对应的平衡二叉树，数列{4，3，6，5，7，8}
问题：当插入8时，rightHeight() - leftHeight() > 1 成立，此时，不再是一颗AVL树了
怎么处理--因为右子树比左子树高，所以要进行左旋转
左旋转思路：
- 创建一个新的节点
newNode，值等于当前根节点的值（4这个值）- 把新节点的左子树设置为当前节点的左子树
newNode.left = left（newNode4指向3）- 把新节点的右子树设置为当前节点的右子树的左子树
newNode.right = right.left(newNode4指向5)- 把当前节点的值换成右子节点的值
value = right.value（根节点4的值换成6）- 把当前节点的右子树设置成右子树的右子树
right = right.right（根节点6指向7）- 把当前节点的左子树设置为新节点
left =newLeft（根节点6指向4）
应用案例-单旋转（右旋转）
要求：给你一个数列，创建出对应的平衡二叉树，数列{10，12，8，9，7，6}
问题：当插入6时，leftHeight() - rightHeight() > 1 成立，此时，不再是一颗AVL树了
怎么处理--因为左子树比右子树高，所以要进行右旋转
右旋转思路：
- 创建一个新节点
newNode，值等于当前根节点的值（10这个值）- 把新节点的右子树设置为当前节点的右子树
newNode.right = right(newNode10指向12)- 把新节点的右子树设置为当前节点的左子树的右子树
newNode.left = left.right(newNode10指向9)- 把当前节点的值换为左子节点的值
value = left.value(根节点10的值换成8)- 把当前节点的左子树设置为左子树的左子树
left = left.left（根节点8指向7）- 把当前节点的右子树设置为新节点
right = newNode（根节点8指向10）
应用案例-双旋转
前面的两个数列，进行单旋转（即一次旋转）就可以将非平衡二叉树转成平衡二叉树，但是在某些情况下，单旋转不能完成平衡二叉树的转换，比如数列{10，11，7，6，8，9}
问题分析：
当符合右旋转的条件时
如果它的左子树的右子树高度大于它的左子树的高度
先对当前这个节点的左节点进行左旋转
再对当前节点进行右旋转的操作即可
如有疑问，可以通过公众号【Java与大数据学习】联系我
