参考：AVL 树 1. 什么是 AVL 树 AVL 树，自平衡二叉查找树，名字来源于作者首字母大写。 在 AVL 树中，任一节点对应的两颗子树最大高度差为1，因此，AVL 树也称为高度平衡树。查找、删除、插入平均、最坏复杂度都是O(log n)，增加和删除元素的操作可能触发一次或多次树旋转。 2.