性质
|H(left) - H(right) | <= 1
所有树（包括子树）的高度差不超过1
优点
由于对每个节点的左右子树的树高做了限制，所以整棵树不会退化成一个链表
思考
- 高度为H的BS树，包含的节点数量的范围？
最大：
, 最小：H
- 高度为H的AVL树，所包含的节点数量在什么范围内？
low(h)：高度为h的AVL树的最少节点数量
low(h - 1) + low(h - 2) + 1 (
) 
size(h) 
AVL树最坏情况，遍历次数也是O(logN)级别，但二叉排序树会有O(N)级别，AVL树能提高下限；
若有收获，就点个赞吧
0 人点赞
