平衡二叉树：AVL树（python）
要了解平衡二叉树，先要知道什么是平衡因子。
平衡因子
平衡因子：左子树深度 – 右子树深度
如下面2幅图平衡因子分别为 -1、0
AVL树
平衡二叉树中各个结点的平衡因子只能是 0， 1， -1。
构造平衡二叉排序树
在学习构造平衡二叉排序树之前，先看看“不平衡”的几种情况：
- LL（平衡因子为+2）
- LR（平衡因子为+2）
- RR（平衡因子为-2）
- RL（平衡因子为-2）
例：给定关键字的序列{13， 24， 37， 90， 53， 40}，建立平衡二叉排序树。（什么是二叉排序树，如何构造二叉排序树可以看我的另一篇博客数据结构之二叉排序树（Python实现建立、查找、删除））
失去平衡时先确定失去平衡的最小子树，这是关键，然后判断类型（ LL， LR，RL， RR），再平衡化处理。
平均查找长度ASL
高度为 h 的平衡二叉树的最少结点数：
故综上规律，
N
h
N_h
Nh表示高度为 h 的平衡二叉树的最少结点数：
平衡二叉排序树的平均查找性能 O(log n)