如果二叉搜索树的输入以排序(升序或降序)方式怎么办?然后看起来像这样-

Unbalanced BST

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

无涯教程网

AVL树以其发明者Adelson,Velski&Landis的名字命名,是高度平衡的二叉搜索树。AVL树检查左子树和右子树的高度,并确保差异不超过1。该差异称为“平衡因子”。

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

Unbalanced AVL Trees

在第二棵树中, 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树可能变得不平衡。然后,树需要右旋转。

右旋

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

左右旋

两次旋转是已经解释过的旋转形式的稍微复杂的版本。为了更好地理解它们,我们应注意旋转时执行的每个动作。让我们首先检查如何执行左右旋转。左右旋转是左旋转与右旋转的组合。

State Action
右旋 一个节点已插入到左子树的右子树中。这使C成为不平衡节点。这些方案使AVL树执行左右旋转。
左旋 我们首先在C的左子树上执行左旋转。这使A,B的左子树。
左旋 节点C仍然不平衡,但是现在是由于left-subtree的left-subtree。
右旋 现在,我们将树右旋转,使B成为该子树的新根节点。C现在成为其自己的左子树的右子树。
Balanced Avl Tree 现在树已平衡。

右旋-左旋

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

State Action
Left Subtree of Right Subtree 一个节点已插入到右子树的左子树中。这使A成为不平衡节点,平衡因子为2。
Subtree 右旋 首先,我们沿C节点执行右旋转,使C成为其自己的左子树B的右子树。现在,B成为A的右子树。
Right Unbalanced Tree 节点A仍然由于其右子树的右子树而处于不平衡状态,并且需要向左旋转。
左旋 通过使B成为子树的新根节点来执行左旋转。A成为其右子树B的左子树。
Balanced AVL Tree 现在树已平衡。

祝学习愉快!(内容编辑有误?请选中要编辑内容 -> 右键 -> 修改 -> 提交!)

技术教程推荐

深入浅出gRPC -〔李林锋〕

ZooKeeper实战与源码剖析 -〔么敬国〕

后端技术面试 38 讲 -〔李智慧〕

Python自动化办公实战课 -〔尹会生〕

陶辉的网络协议集训班02期 -〔陶辉〕

React Hooks 核心原理与实战 -〔王沛〕

Tony Bai · Go语言第一课 -〔Tony Bai〕

手把手带你搭建推荐系统 -〔黄鸿波〕

结构执行力 -〔李忠秋〕

好记忆不如烂笔头。留下您的足迹吧 :)