# avl 树 - 概述

前面学习过二叉搜索树就知道，如果二叉搜索树长的不平衡，就会影响到它的查找效率

我们看如下图的 不平衡的 二叉树

比如我想查询 1 的元素，那我就需要从根节点开始一路向左找，才能找到 1 的元素。而它的比较次数是 O (n)

我们怎么解决这个问题呢？我们有个办法就是旋转让上面的二叉树重新变得左右平衡

也就是让 上面的二叉树 整体向右旋转一下

这时 就比 刚才的 二叉树 平衡了一些了， 此时在查询 1 元素效率就会好一点了，而且呢。旋转也不会破坏二叉搜索树的性质

那新的问题又来了：如果判断给的二叉搜索树 是不平衡的然后让 其二叉树重新变得平衡呢？

这时，可以通过如下规则来判断：

如果一个节点的左右孩子，高度差超过 1，则此节点失衡，才需要旋转

只有当 新增 或者 删除时可能会让一个平衡的二叉树变得不平衡，此时我们就需要进行旋转了。

AVL 树的定义：

• 二叉搜索树在插入和删除时，节点可能失衡
• 如果在插入和删除时通过旋转，始终让二叉搜索树保持平衡，称为自平衡的二叉搜索树
• AVL 是平衡二叉搜索树的实现之一

代码实现查看文章：点击查看 其中有讲 AVL 树的实现