平衡二叉树(AVL树)
平衡二叉树简介：
平衡树(Balance Tree，BT) 指的是，任意节点的子树的高度差都小于等于1。常见的符合平衡树的有，B树（多路平衡搜索树）、AVL树（二叉平衡搜索树）等。
具有以下特点:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1, 并且左右两个子树都是-棵平衡二叉树。
平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。可以保证查询效率高。
举例看下下面AVL树的特点吧：左右两个子树的高度差的绝对值不超过1
第三棵树的左子树高度是3，右子树高度是1,3-1=2,所以第三个不是AVL树
AVL树左旋
AVL树左旋图解
要求: 给你一个数列，创建出对应的平衡二叉树.数列 {4,3,6,5,7,8}
AVL树左旋步骤：
- 创建一个新的节点，值为当前节点的值
- 把新节点的的左子树设置为原节点的左子树：4-->指向3
- 把新节点的右子树设置为当前节点的右子树的左子树
- 把当前节点的值：4 换成当前右子节点的值：6
- 把当前节点的右子树设为右子树的右子树
- 把当前节点的左子树设为新的节点：6-->指向4