AVL树是最先发明的自平衡二叉查找树。AVL树得名于它的发明者 G.M. Adelson-Velsky 和 E.M. Landis，他们在 1962 年的论文 "An algorithm for the organization of information" 中发表了它。
AVL树是带平衡条件的二叉查找树：
(1 ) 左子树和右子树的深度之差的绝对值不超过1;
(2) 左子树和右子树也是平衡二叉树。
若将二叉树上结点的平衡因子(Balance Factor, BF)定义为该结点左子树和右子树的深度之
差，则平衡二叉树上所有结点的平衡因子只可能是 -1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1 , 则该二叉树就是不平衡的。
在AVL中任何节点的两个儿子子树的高度最大差别为1，所以它也被称为高度平衡树，n个结点的AVL树最大深度约1.44log2n。得益于这个特征，它的深度和 log~2~n 是同数量级的（其中n为结点数）。 由此，其查找的时间复杂度是O(log~2~n)。
5.1.2、AVL树的平衡调整方法
插入结点时， 首先按照二叉排序树处理， 若插入结点后破坏了平衡二叉树的特性， 需对平衡二叉树进行调整。 调整方法是：找到离插入结点最近且平衡因子绝对值超过1的祖先结点， 以该结点为根的子树称为最小不平衡子树， 可将重新平衡的范围局限千这棵子树。
在平衡调整的过程中，有一个关键点是旋转。
这里有一个具体例子：
(1) 空树和1个结点⑬的树显然都是平衡的二叉树。在插入24之后仍是平衡的， 只是根结点的平衡因子BF由0变为-1, 如图18(a) -（c）所示。
(2) 在继续插入37之后， 由千结点 ⑬ 的BF值由 -1 变成 -2, 由此出现了不平衡的现象。此时好比一根扁担出现一头重一头轻的现象， 若能将扁担的支撑点由 ⑬ 改至 ㉔ ， 扁担的两头就平衡了。此，可以对树做一个向左逆时针 ＂ 旋转 ＂ 的操作，令结点 ㉔为根，而结点 ⑬ 为它的左子树，此时，结点⑬ 和 ㉔ 的平衡因子都为0, 而且仍保持二叉排序树的特性，如图18(d)~ (e)所示。
(3) 在继续插入90和53之后，结点 ㊲ 的BF值由-1变成-2, 排序树中出现了新的不平衡现象，需进行调整。但此时由于是结点邸插在结点 (90) 的左子树上，因此不能如上做简单调整。离插入结点最近的最小不平衡子树是以结点 ㊲为根的子树。这时，必须以 (53) 作为根结点，而使 ㊲ 成为它的左子树的根，(90) 成为它的右子树的根。这好比对树做了两次 “旋转” 操作，先向右顺时针旋转，后向左逆时针旋转（见图18 (f)~(h)), 使二叉排序树由不平衡转化为平衡。
一般情况下，假设最小不平衡子树的根结点为 A, 则失去平衡后进行调整的规律可归纳为下列4种情况。
(1) LL 型：由于在 A 左子树根结点的左子树上插入结点，A 的平衡因子由 1 增至 2, 致使以A为根的子树失去平衡，则需进行一次向右的顺时针旋转操作，如图21所示。
图22所示为两个LL型调整的实例。
(2) RR 型：由千在 A 的右子树根结点的右子树上插入结点， A 的平衡因子由 -1 变为 -2,致使以 A 为根结点的子树失去平衡，则需进行一次向左的逆时针旋转操作，如图23所示。
图24所示为两个RR型调整的实例。
