如果二叉搜索树的输入以排序(升序或降序)方式怎么办?然后看起来像这样-
可以看出,BST的最坏情况性能最接近线性搜索算法,即Ο(n),在实时数据中,我们无法预测数据模式及其频率。因此,需要平衡现有的BST。
AVL树以其发明者Adelson,Velski&Landis的名字命名,是高度平衡的二叉搜索树。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的左子树上执行左旋转。这使A,B的左子树。 | |
节点C仍然不平衡,但是现在是由于left-subtree的left-subtree。 | |
现在,我们将树右旋转,使B成为该子树的新根节点。C现在成为其自己的左子树的右子树。 | |
现在树已平衡。 |
第二种双旋转是右旋转。它是向右旋转然后是向左旋转的组合。
State | Action |
---|---|
一个节点已插入到右子树的左子树中。这使A成为不平衡节点,平衡因子为2。 | |
首先,我们沿C节点执行右旋转,使C成为其自己的左子树B的右子树。现在,B成为A的右子树。 | |
节点A仍然由于其右子树的右子树而处于不平衡状态,并且需要向左旋转。 | |
通过使B成为子树的新根节点来执行左旋转。A成为其右子树B的左子树。 | |
现在树已平衡。 |
祝学习愉快!(内容编辑有误?请选中要编辑内容 -> 右键 -> 修改 -> 提交!)
Tony Bai · Go语言第一课 -〔Tony Bai〕