数据结构之AVL树

树的平衡，我们已经知道DWL算法，不过DWL算法需要从整体上平衡树，但是树的平衡也可以局部的进行，由Adel'son-Vel'skii-Landis提出了一种经典方法，称为AVL树。

1。概念：AVL树，或者说可适应树，是指树中每个节点的的平衡因子的绝对值不大于1，即只能为-1，0，1
平衡因子：节点的右子树的高度减去左子树的高度

2。AVL树的插入：从新插入节点到根的路径上，修改遇到的节点的平衡因子即可，对其他部分没影响
1）向右子女的右子树插入一个节点，单旋转就可以
2）向右子女的左子树插入一个节点，双旋转，先围绕父节点，再围绕祖父节点

3。AVL树的删除：从删除节点到根的路径上，任何不平衡因子的节点都需要修改，与插入不同，需要O(lgn)次旋转。

4。一个java实现：
http://www.koders.com/java/fid3B5247D34968077A6EFD4216589026D343559FF9.aspx?s=avl%2Btree