如果二进制搜索树的输入以排序(升序或降序)方式出现，该怎么办？然后它看起来像这个 :
它是观察到BST的最坏情况表现最接近线性搜索算法，即Ο(n).在实时数据中，我们无法预测数据模式及其频率.因此，需要平衡现有的BST.
以他们的发明者 Adelson 命名， Velski & Landis ， AVL树是高度平衡二叉搜索树. AVL树检查左侧和右侧子树的高度，并确保差异不大于1.这种差异称为平衡因子.
这里我们看到第一棵树是平衡的，接下来的两棵树不平衡 :
在第二个树中， C 的左子树的高度为2，右子树的高度为0，因此差值为2.在第三个树中， A 的右子树的高度为2，左侧为低，因此为0，差值为2. AVL树允许差异(平衡因子)仅为1.
BalanceFactor = height(left-sutree) − height(right-sutree)
如果左子树和右子树的高度差异大于1，则使用一些旋转技术平衡树.
为了平衡自身，AVL树可以执行以下四种旋转 :
左转
右旋
左右旋转
左右旋转
前两个旋转是单旋转，接下来的两个旋转是双旋转.为了拥有一棵不平衡的树，我们至少需要一棵树高2.用这棵简单的树，我们逐一理解它们.
如果树变得不平衡，当一个节点插入到右子树的右子树中时，我们执行单个左旋转 :
在我们的示例中，当节点插入A右子树的右子树中时，节点 A 变得不平衡.我们通过使 A B的左子树来执行左旋转.
AVL树可能会变为如果节点插入左子树的左子树中，则不平衡.然后树需要正确旋转.
如图所示，通过执行正确的旋转，不平衡节点成为其左子节点的右子节点.
双旋转是稍微复杂的版本已解释的旋转版本.为了更好地理解它们，我们应该注意旋转时执行的每个动作.我们先来看看如何进行左右旋转.左右旋转是左旋转后右旋转的组合.
| State | Action |
|---|---|
 | 节点已插入左子树的右子树中.这使 C 成为不平衡节点.这些场景导致AVL树执行左右旋转. |
 | 我们首先在 C |
 | 节点 C 仍然是不平衡的，但是现在，这是因为左子树的左子树. |
 | 我们将现在右旋转树，使 B 成为此子树的新根节点. C 现在成为其左子树的右子树. |
 | 树现在已经平衡. |
第二种双旋转方式是右 - 左回转.它是右旋转后左旋转的组合.
| State | Action |
|---|---|
 | 已将一个节点插入到右子树的左子树中.这使得 A ，一个平衡因子为2的不平衡节点. |
 | 首先，我们执行正确的旋转 C 节点，使 C 成为其左子树 B 的右子树.现在， B 成为 A 的正确子树. |
 | 节点 A 仍然是不平衡的，因为它的右子树的右子树需要左旋. |
 | 左旋转是通过使 B 子树的新根节点来执行. A 成为其右子树的左子树 B . |
 | 树现在是平衡的. |
