大二那会根本没蹋下心来看，觉得天书一般，连旋转都没搞明白。

今天仔细看了书，发现真的一点不难啊，鄙视自己……

首先是概念：

平衡二叉树是为了解决前面二叉排序树不均衡的问题，而加入了一种平衡机制。所以，平衡二叉树是一种特殊的二叉排序树(BST)！

AVL树查找的平均和最差复杂度都是O(logn) ！！！(BST的最坏是O(n))

AVL树的插入复杂度是O(logn)。

平衡二叉树（简称AVL树）：对任意一个结点，它的左子树和又子树都是平衡二叉树（左子树都小于结点[......]

继续阅读