平衡二叉树

 1、平衡二叉树（AVL）：它或者是一颗空树，左子树和右子树的深度之差不超过，且他的左子树和右子树都是一颗平衡二叉树

2、平衡二叉树出现的原因：平衡二叉树就是在二叉排序树（BST）引入的，就是为了解决二叉排序树的不平衡性导致时间复杂度大大下降，AVL就保持住了BST的最好时间复杂度O（logn），所以每次插入和删除都要确保二叉树的平衡，很好的解决了二叉查找树退化成链表的问题，把插入查找删除的时间复杂度最好情况和最坏的情况都维持在了O（logn），但是频繁旋转会使插入和删除牺牲掉O(logn)左右的时间，相对二叉查找树来说，时间上稳定了很多。

3、平衡二叉树默认左孩子的值比双亲节点小，右孩子的值比双亲节点大（这句话也很重要）。由此在插入或者删除结点时，如何调整二叉树为平衡二叉树？这里就有四种情况

　　1、去判断每个结点的平衡因子，为2的结点要移动，如果一棵树有两个结点平衡因子都为2，移动下面的那个结点（这句话很重要）

　　LL：首先这个图的大小排序你能分辨出来吗：T1<Z<T2<X<T3<Y<T4（如果能分辨出来，以下内容你将会很好理解）

　　　　这是所谓的左左结构：x<y x>z 所以不平衡时把x放在中间，T3>X T3<Y 所以T3应该放在X的右边，Y的左边

　　LR：一样的道理z>x z<y 所以Z应该放在x、y的中间，T2>x T2<z; T3>zT3<y

　　RR:x放在y和z的中间，T3<x,T3>y

　　RL:  Z<X Z>Y 所以z放在xy中间, T2>Y,T2<Z; T3>Z,T3<X

4、那既然说完上面的四种调整结构了，如何使用呢，用插入元素（90,66,65,98,100,88,105,102,110,103）构造一颗平衡二叉树，构造过程如下

5、既然插入说了，此处相信大家删除结点在调整为平衡二叉树一定会了吧，就不一一举例了

感谢观看