算法：AVL树算法

如果二叉搜索树的输入以排序(升序或降序)方式出现怎么办？它会看起来像这样 -

BST不平衡

据观察，BST的最坏情况性能最接近线性搜索算法，即Ο(n)。在实时数据中，我们无法预测数据模式及其频率。因此，需要平衡现有的BST。

以他们的发明者 Adelson ， Velski 和 Landis 命名， AVL树 是高度平衡二元搜索树。AVL树检查左侧和右侧子树的高度，并确保差异不大于1.这种差异称为 平衡因子 。

在这里，我们看到第一棵树是平衡的，接下来的两棵树是不平衡的 -

不平衡的AVL树

在第二个树中， C 的左子树具有高度2，右子树具有高度0，因此差异为2.在第三个树中， A 的右子树具有高度2而左侧缺失，因此它为0 ，差异又是2。AVL树允许差异(平衡因子)仅为1。

_ **BalanceFactor**_ = height(left-sutree) − height(right-sutree)

如果左子树和右子树的高度差异大于1，则使用一些旋转技术来平衡树。

AVL轮换

为了平衡自身，AVL树可以执行以下四种旋转 -

前两个旋转是单旋转，接下来的两个旋转是双旋转。要拥有一棵不平衡的树，我们至少需要一棵高度为2的树。通过这棵简单的树，让我们逐一理解它们。

如果树变得不平衡，当一个节点插入到右子树的右子树中时，我们执行一个左旋转 -

在我们的示例中，节点 A 变得不平衡，因为节点插入到A右子树的右子树中。我们通过使 A 为B的左子树来执行左旋转。

如果节点插入左子树的左子树中，则AVL树可能变得不平衡。然后树需要正确的旋转。

如图所示，通过执行右旋转，不平衡节点成为其左孩子的右孩子。

双旋转是已经解释的旋转版本的略微复杂版本。为了更好地理解它们，我们应该注意旋转时执行的每个动作。我们先来看看如何进行左右旋转。左右旋转是左旋转然后右旋转的组合。

州	行动
	已将节点插入左子树的右子树中。这使得 C 成为不平衡节点。这些场景导致AVL树执行左右旋转。
	我们首先在 C 的左子树上执行左旋转。这使得 A 成为 B 的左子树。
	节点 C 仍然是不平衡的，但是现在，这是因为左子树的左子树。
	我们现在将右旋转树，使 B 成为此子树的新根节点。 C 现在成为其左子树的右子树。
	树现在平衡了。

第二种类型的双旋转是右 - 左旋转。它是右旋转然后左旋转的组合。

州	行动
	已将节点插入右子树的左子树中。这使得 A 是一个平衡因子为2的不平衡节点。
	首先，我们沿着 C 节点执行正确的旋转，使 C 成为其自己的左子树 B 的右子树。现在， B 成为 A 的正确子树。
	由于右子树的右子树并且需要左旋转，节点 A 仍然是不平衡的。
	通过使 B 成为子树的新根节点来执行左旋转。 A 成为其右子树 B 的左子树。
	树现在平衡了。

算法：生成树的数据结构和算法：生成树是图G的子集，其具有覆盖有最小可能边数的所有顶点。因此，生成树没有循环，也无法断开连接。通过这个定义，我们可以得出结论，每个连通和无向图G都至少有一个生成树。断开连接的图形没有任何生成树，因为它不能跨越所 ...

下一章：算法：生成树的算法

州	行动
	已将节点插入左子树的右子树中。这使得 C 成为不平衡节点。这些场景导致AVL树执行左右旋转。
	我们首先在 C 的左子树上执行左旋转。这使得 A 成为 B 的左子树。
	节点 C 仍然是不平衡的，但是现在，这是因为左子树的左子树。
	我们现在将右旋转树，使 B 成为此子树的新根节点。 C 现在成为其左子树的右子树。
	树现在平衡了。

州	行动
	已将节点插入右子树的左子树中。这使得 A 是一个平衡因子为2的不平衡节点。
	首先，我们沿着 C 节点执行正确的旋转，使 C 成为其自己的左子树 B 的右子树。现在， B 成为 A 的正确子树。
	由于右子树的右子树并且需要左旋转，节点 A 仍然是不平衡的。
	通过使 B 成为子树的新根节点来执行左旋转。 A 成为其右子树 B 的左子树。
	树现在平衡了。