AVL树

AVL树是最早被发明的 自平衡二叉查找树。在AVL树中,任一节点对应的两棵子树的最大高度差为1,因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是O(logn)

增加和删除元素的操作则可能需要借由一次或多次树旋转,以实现树的重新平衡

AVL树得名于它的发明者G. M. Adelson-Velsky和Evgenii Landis


操作:

失去平衡的树需要通过旋转来重新保持平衡,如下图,有4种情况

1.左左情况 - 通过右旋保持平衡

2.右右情况 - 通过左旋保持平衡 

3.左右情况 - 先通过左旋变成 左左情况,然后通过右旋保持平衡

4.右左情况 - 先通过右旋变成 右右情况,然后通过左旋保持平衡


实现步骤:

1.当遇到插入和删除操作时,判断树是否继续保持平衡

2.如果不平衡,判断属于上述哪种情况,然后通过旋转继续保持平衡


由于每次都要严格保持平衡,所以在有频繁删除和插入等操作时,性能影响比较大,红黑树的引进就是为了解决这一问题


参考:

wiki-AVL树

上一篇: 二叉查找树
下一篇: 红黑树
作者邮箱: 203328517@qq.com