平衡二叉搜索树（Balanced Binary Search Tree）VS二叉搜索树(Binary Search Tree)
- 二叉搜索树BST在插入时如果插入的key一直比之前存在的key大（或小）的话会退化成链表，如果节点的个数为n,那么相关的操作就是O(n),而不是是O(lgn)。
- 平衡二叉搜索树（BBST）要解决的问题就是BBST插入删除操作可能导致左右子树不平衡的问题。通过插入删除调整算法将树的高度h控制在O(lgn)级别。
什么是AVL树
AVL树是平衡二叉搜索树的一种。
AVL树的平衡因子（Balance Factor简称BF）的绝对值<=1;
节点平衡因子的定义为节点左子树的高度减去右子树的高度。
AVL树及BF
为什么AVL树是平衡的
也就是说为什么AVL的树高为O(lgn)。
假设N(h) 为高度为h的AVL树需要的最小节点数
若树高为1的话，一个节点就够了 即N(1)=1
若树高为2的话，最少需要2个节点N(2)=2
N(3)至少需要一个根节点一个树高为1的子树和一个树高为2的子树构成=1+1+2=4。
进而N(h)=N(h-1)+N(h-2)+1
则N(h)-1=N(h-1)+N(h-2),这个和斐波拉契数列很像N(h)=F(h+2)-1<=n(n为AVL树的节点数，N(h) 表示的是最小节点数，当然<=n) ,斐波拉契数列是指数级别的，两边取对数得出结论：
n个节点构成的AVL树的高度 h<=O(lgn).
