平衡二叉搜索树之AVL树

平衡二叉搜索树（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).