Fork me on GitHub

【译】Swift算法俱乐部-AVL树

本文是对 Swift Algorithm Club 翻译的一篇文章。
Swift Algorithm Clubraywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目,目前在GitHub上有18000+⭐️,我初略统计了一下,大概有一百左右个的算法和数据结构,基本上常见的都包含了,是iOSer学习算法和数据结构不错的资源。
🐙andyRon/swift-algorithm-club-cn是我对Swift Algorithm Club,边学习边翻译的项目。由于能力有限,如发现错误或翻译不妥,请指正,欢迎pull request。也欢迎有兴趣、有时间的小伙伴一起参与翻译和学习🤓。当然也欢迎加⭐️,🤩🤩🤩🤨🤪。
本文的翻译原文和代码可以查看🐙swift-algorithm-club-cn/AVL Tree


AVL树(AVL Tree)

AVL树是二叉搜索树的自平衡形式,其中子树的高度最多只相差1。

当二叉树的左右子树包含大致相同数量的节点时,称树是 平衡的。 这就是使树搜索速度非常快的原因。 但是如果二元搜索树不平衡,搜索会变得非常慢。

这是一个不平衡树的例子:

Unbalanced tree

所有的子节点都在左侧分支,没有一个在右侧分支。 这与链表基本相同。 因此,搜索需要 O(n) 时间,而不是您期望从二叉搜索树获得的更快的 O(log n)

该树的平衡版本如下所示:

Balanced tree

使二进制搜索树平衡的一种方法是以完全随机的顺序插入节点。 但这并不能保证成功,也不总是切实可行。

另一种解决方案是使用自平衡二叉树。 插入或删除节点后,此类型的数据结构会调整树以使其保持平衡。 这种树的高度保证为 log(n),其中 n 是节点的数量。 在平衡树上,所有插入,移除和搜索操作仅需 O(logn) 时间。 这意味着快速。;-)

介绍AVL树

AVL树通过向左或向右“旋转”树来修复任何不平衡。

如果AVL树中的节点在“高度”上的差异最大为1,则认为它是平衡的。如果树的所有节点都是平衡的,则树本身是平衡的。

节点的height是获取该节点最低叶子所需的步数。 例如,在下面的树中,从A到E需要三个步,因此A的高度为3。B的高度为2,C的高度为1,其他的高度为0,因为它们是叶节点。

Node height

如上所述,在AVL树中,如果节点的左右子树具有相同的高度,则节点是平衡的。 当然不必是完全相同的高度,但差异不能大于1。这些都是平衡树的例子:

Balanced trees

以下是不平衡的树,因为左子树的高度与右子树相比太大了:

Unbalanced trees

左右子树的高度之间的差异称为平衡因子(balance factor)。 计算方法如下:

balance factor = abs(height(left subtree) - height(right subtree))

如果在插入或删除后平衡因子变得大于1,那么我们需要重新平衡AVL树的这一部分。 这是通过旋转完成的。

译注: abs是绝对值的意思。

旋转

每个树节点在变量中跟踪其当前平衡因子。 插入新节点后,我们需要更新其父节点的平衡因子。 如果该平衡因子大于1,我们“旋转”该树的一部分以恢复平衡。

Rotation0

对于旋转,我们使用术语:

  • Root - 将要旋转的子树的父节点;
  • Pivot - 旋转后将成为父节点(基本上位于 Root 位置)的节点;
  • RotationSubtree - 旋转侧的Pivot的子树
  • OppositeSubtree - 与旋转侧相对的Pivot的子树

让我们举一个使用(顺时针方向)旋转来平衡不平衡树的示例:

Rotation1 Rotation2 Rotation3

旋转步骤可以通过以下方式描述:

  1. RotationSubtree指定为Root的新OppositeSubtree;
  2. Root指定为Pivot的新RotationSubtree;
  3. 检查最终结果

用伪代码,上面的算法可以写成如下:

1
2
3
Root.OS = Pivot.RS
Pivot.RS = Root
Root = Pivot

这是一个恒定时间操作 - O(1) 插入永远不需要超过2次旋转。 删除可能需要最多 log(n) 轮换。

代码

AVLTree.swift中的大多数代码只是常规二叉搜索树的东西。 您可以在二叉搜索树找到大部分实现。 例如,搜索树是完全相同的。 AVL树唯一不同的是插入和删除节点。

注意: 如果你对二叉搜索树的常规操作有点模糊,我建议你看这边。 这会使AVL树更容易理解。

有趣的位在balance()方法中,在插入或删除节点后调用。

扩展阅读

AVL树的维基百科

AVL树是第一个自平衡二叉树。 最近,红黑树似乎更受欢迎。

作者:Mike Taghavi, Matthijs Hollemans
翻译:Andy Ron

坚持原创技术分享,您的支持将鼓励我继续创作!
  • 本文标题: 【译】Swift算法俱乐部-AVL树
  • 本文作者: AndyRon
  • 发布时间: 2018年12月09日 - 10:58
  • 最后更新: 2019年01月11日 - 10:12
  • 本文链接: http://andyron.com/2018/Swift算法俱乐部-AVL树.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处!