AVL树适度平衡的条件比较苛刻，因此AVL树是非常接近完全二叉树的一种BBST。其查询效率和红黑树等综合性能更加优秀的BBST相比，查询时，虽然渐进的时间复杂度都为O(logN)，但在常数倍率上看，效率要稍高一点点。

5.AVL树总结

　　AVL树作为最早被发明的自平衡二叉搜索树，其删除效率与随后被发明的红黑树相比，相差一个数量级(O(logN) vs O(1))。其主要原因是红黑树等BBST在"平衡"的定义上进一步放松了标准，全树结构不如AVL树那么紧凑，略为降低了查询效率，但换来了删除效率的巨大提升。

　　AVL树作为一种相对效率较低的BBST，其原理相较红黑树更简单。理解AVL树是理解更为强大、复杂的BBST的基础之一。

　　本系列博客的代码在我的 github上：https://github.com/1399852153/DataStructures?，存在许多不足之处，请多多指教。

（编辑：衡阳站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!