AVL树是最早的一种平衡树，它以发明者的名字命名：Adelson-Velskii 和 Landis。在AVL树中每个节 点存储一个额外的数据：它的左子树和右子树的高度差。这个差值不会大于1，也就是说，节点的左子树的高 度和右子树的高度相差不会大于一层。

插入之后，检查新节点插入点所在的最低子树的根，如果他的子节点的高度相差大于1，执行一次或者两次旋 转使它们的高度相等。然后算法向上移动，检查上面的节点，必要时均衡高度。这个检测检查所有路径一直 向上，直到根为止。

AVL树查找的时间复杂度为O(logN)，因为树一定是平衡的。但是，由于插入(或者删除)一个节点时需要扫 描两趟树，一次向下查找插入点，一次向上平衡树，AVL树不如红黑树效率高，也不如红黑树常用。

![image-alter](/image/post/2021/07/23/01/xxx.jpg)

参考资料

• Java数据结构和算法
• Java数据结构和算法 - AVL树