Posted on 2007-02-20 12:57
dennis 阅读(1194)
评论(0) 编辑 收藏 所属分类:
数据结构与算法
树的平衡，我们已经知道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