16.`AVL`树¶

在上一章中，你了解了二进制搜索树的O(log n)性能特点。然而，你还了解到，不平衡的树会使树的性能恶化，一直到O(n)。1962年，Georgy Adelson-Velsky和Evgenii Landis想出了第一个自我平衡的二进制搜索树。即AVL Tree。在这一章中，你将深入研究二进制搜索树的平衡性如何影响性能，并从头开始实现AVL树!

了解平衡¶

平衡树是优化二进制搜索树性能的关键。在本节中，你将了解到平衡的三种主要状态。

完美的平衡¶

二元搜索树的理想形式是perfectly balanced状态。在技术术语中，这意味着树的每一层都充满了节点，从上到下。

该树不仅完全对称，而且底层的节点也完全被填满。这就是完全平衡的要求。

"足够好的"平衡¶

虽然实现完美平衡是最理想的，但它很少可能。一棵完全平衡的树必须包含确切数量的节点来填充每一层到底部，所以它只能用特定数量的元素来实现完美。

例如，一棵有1、3或7个节点的树可以是完美平衡的，但一棵有2、4、5或6个节点的树不可能是完美平衡的，因为树的最后一层将不会被填满。

平衡树的定义是，树的每一层都必须被填满，除了最底层。在大多数二叉树的情况下，这是你能做的最好的事情。

不平衡¶

最后，还有一种unbalanced状态。在这种状态下的二进制搜索树会有不同程度的性能损失，这取决于不平衡的程度。

保持树的平衡使find、insert和remove操作的时间复杂度为O(log n)。AVL树通过在树变得不平衡时调整树的结构来保持平衡。你会在本章中了解到这是如何进行的。

实施¶

在本章的启动项目中，有一个二进制搜索树的实现，正如前一章中所创建的那样。唯一的区别是，所有对二进制搜索树的引用都被重命名为AVL树。

二进制搜索树和AVL树有很多相同的实现；事实上，你要添加的只是平衡组件。打开启动项目，开始。

测量平衡¶

为了保持二叉树的平衡，你需要一种方法来测量树的平衡。AVL树通过每个节点的height属性来实现这一点。用树的语言来说，节点的height是指从当前节点到叶子节点的longest距离：

打开本章的启动Playground，在编译后的源文件夹中为AVLNode添加以下属性。

public var height = 0

你将使用一个节点的子节点的相对高度来确定一个特定的节点是否平衡。每个节点的左右子节点的高度必须最多相差1，这个数字被称为balance factor。

在AVLNode的height属性下面写上以下内容：

public var balanceFactor: Int {
  leftHeight - rightHeight
}

public var leftHeight: Int {
  leftChild?.height ?? -1
}

public var rightHeight: Int {
  rightChild?.height ?? -1
}

balanceFactor计算左和右孩子的高度差。如果某个孩子是nil，它的高度就被认为是-1。

下面是一个AVL树的例子：

图中显示的是一棵平衡树--除了最下面的一层外，所有层次都被填满。节点右边的数字代表每个节点的height，左边的数字代表balanceFactor。

这是一个插入了40的更新图：

在树中插入40会使它变成一棵不平衡的树。注意balanceFactor的变化。balanceFactor为2或2或更极端的东西表示一个不平衡的树。通过每次插入或删除后的检查，你可以保证它永远不会超过2的幅度。

尽管不止一个节点可能有不好的平衡因子，但你只需要对包含无效平衡因子的最底层节点执行平衡程序：包含25的节点。

这就是旋转的作用。

旋转¶

用来平衡二进制搜索树的程序被称为rotations。总共有四种旋转方式，用于平衡树的四种不同方式。这些被称为left旋转、left-right旋转、right旋转和right-left旋转。

左旋¶

在树中插入40引起的不平衡可以通过left rotation来解决。节点x的一般左旋看起来像这样：

在讨论具体细节之前，从这个前后对比中可以得到两个启示：

这些节点的顺序内遍历保持不变。
旋转后树的深度减少了一级。

在AVLTree中添加以下方法，就在insert(from:value:)下面：

private func leftRotate(_ node: AVLNode<Element>)
  -> AVLNode<Element> {

  // 1
  let pivot = node.rightChild!
  // 2
  node.rightChild = pivot.leftChild
  // 3
  pivot.leftChild = node
  // 4
  node.height = max(node.leftHeight, node.rightHeight) + 1
  pivot.height = max(pivot.leftHeight, pivot.rightHeight) + 1
  // 5
  return pivot
}

以下是进行左旋所需的步骤：

选择右边的子节点作为pivot。这个节点将取代被旋转的节点作为子树的根（它将向上移动一级）。
被旋转的节点将成为支点的左侧子节点（它向下移动一级）。这意味着当前枢轴的左端子节点必须被移到其他地方。在前面图片中显示的一般例子中，这是节点b。因为b比y小，但比x大，它可以取代y成为x的右子。所以你把旋转节点的rightChild更新为枢轴的leftChild。
枢轴的leftChild现在可以被设置为旋转的节点。
你更新旋转节点和枢轴的高度。
最后，你返回支点，这样它就可以在树中取代旋转的节点。

下面是前面例子中25的左旋转前后的效果：

右旋¶

右旋转是与左旋转对称的反面。当一系列左边的孩子造成不平衡的时候，就是右旋转的时候了。

节点x的一般右旋转看起来像这样：

要实现这一点，请在leftRotate之后添加以下代码：

private func rightRotate(_ node: AVLNode<Element>)
  -> AVLNode<Element> {

  let pivot = node.leftChild!
  node.leftChild = pivot.rightChild
  pivot.rightChild = node
  node.height = max(node.leftHeight, node.rightHeight) + 1
  pivot.height = max(pivot.leftHeight, pivot.rightHeight) + 1
  return pivot
}

这个算法与leftRotate的实现几乎相同，只是对左和右子的引用被交换了。

左右旋转¶

你可能已经注意到，左旋和右旋会平衡那些全部为左子节点或全部为右子节点的结点。考虑一下36被插入到原始示例树中的情况。

右-左旋转：

在这种情况下，做左旋转不会产生一个平衡的树。处理这种情况的方法是，在做左旋之前*先对右边的孩子进行右旋。下面是这个程序的样子：

你对37进行右旋转。
现在，节点25、36和37都是右边的子节点；你可以应用左旋转来平衡树。

在rightRotate之后添加以下代码：

private func rightLeftRotate(_ node: AVLNode<Element>)
  -> AVLNode<Element> {

  guard let rightChild = node.rightChild else {
    return node
  }
  node.rightChild = rightRotate(rightChild)
  return leftRotate(node)
}

先不要担心什么时候打这个电话。一会儿你就会知道了。你首先需要处理最后一种情况，左右旋转。

左-右旋转¶

左-右旋转是与右-左旋转对称的。这里有一个例子：

你对节点10施加一个左旋转。
现在，节点25、15和10都是左边的子节点；你可以应用右旋转来平衡树。

在rightLeftRotate之后添加以下代码：

private func leftRightRotate(_ node: AVLNode<Element>)
  -> AVLNode<Element> {

  guard let leftChild = node.leftChild else {
    return node
  }
  node.leftChild = leftRotate(leftChild)
  return rightRotate(node)
}

旋转就到此为止。接下来，你要弄清楚何时在正确的位置应用这些旋转。

平衡¶

下一个任务是设计一个方法，使用balanceFactor来决定一个节点是否需要平衡。在leftRightRotate下面写一个方法：

private func balanced(_ node: AVLNode<Element>)
  -> AVLNode<Element> {

  switch node.balanceFactor {
  case 2:
    // ...
  case -2:
    // ...
  default:
    return node
  }
}

有三种情况需要考虑。

balanceFactor为2，表明左边的孩子比右边的孩子"更重"（包含更多的节点）。这意味着你要使用右旋或左旋的方式。
balanceFactor为-2，表明右边的孩子比左边的孩子更重。这意味着你要使用左或右-左旋转。
默认情况下，表明特定节点是平衡的。这里除了返回节点，没有什么可做的。

平衡因子（balanceFactor）的符号可以用来确定是否需要单旋转或双旋转：

将balanced函数更新为以下内容：

private func balanced(_ node: AVLNode<Element>)
  -> AVLNode<Element> {

  switch node.balanceFactor {
  case 2:
    if let leftChild = node.leftChild,
           leftChild.balanceFactor == -1 {
      return leftRightRotate(node)
    } else {
      return rightRotate(node)
    }
  case -2:
    if let rightChild = node.rightChild,
           rightChild.balanceFactor == 1 {
      return rightLeftRotate(node)
    } else {
      return leftRotate(node)
    }
  default:
    return node
  }
}

balanced检查balanceFactor以确定适当的行动方案。剩下的就是在适当的地方调用balance。

重新审视插入的问题¶

你已经完成了大部分的工作。剩下的部分就相当简单了。将insert(from:value:)更新为以下内容：

private func insert(from node: AVLNode<Element>?,
                    value: Element) -> AVLNode<Element> {
  guard let node = node else {
    return AVLNode(value: value)
  }
  if value < node.value {
    node.leftChild = insert(from: node.leftChild, value: value)
  } else {
    node.rightChild = insert(from: node.rightChild, value: value)
  }
  let balancedNode = balanced(node)
  balancedNode.height = max(balancedNode.leftHeight, balancedNode.rightHeight) + 1
  return balancedNode
}

在插入后不直接返回node，而是将其传入balanced。传递它可以确保调用堆栈中的每个节点都被检查出平衡问题。你还可以更新节点的高度。

这就是它的全部内容! 进入Playground页面并测试它。将以下内容添加到Playground中：

example(of: "repeated insertions in sequence") {
  var tree = AVLTree<Int>()
  for i in 0..<15 {
    tree.insert(i)
  }
  print(tree)
}

你应该在控制台看到以下输出：

---Example of: repeated insertions in sequence---
  ┌──14
 ┌──13
 │ └──12
┌──11
│ │ ┌──10
│ └──9
│  └──8
7
│  ┌──6
│ ┌──5
│ │ └──4
└──3
 │ ┌──2
 └──1
  └──0

花点时间欣赏一下这些节点的均匀分布。如果不应用旋转，这将成为一个长长的、不平衡的右翼儿童的链接。

重新审视`remove`¶

改造remove操作以实现自我平衡，就像修复insert一样简单。在AVLTree中，找到remove并将最后的return语句替换为以下内容：

let balancedNode = balanced(node)
balancedNode.height = max(balancedNode.leftHeight, balancedNode.rightHeight) + 1
return balancedNode

回到Playground页面，在文件的底部添加以下代码：

example(of: "removing a value") {
  var tree = AVLTree<Int>()
  tree.insert(15)
  tree.insert(10)
  tree.insert(16)
  tree.insert(18)
  print(tree)
  tree.remove(10)
  print(tree)
}

你应该看到以下控制台输出：

---Example of: removing a value---
 ┌──18
┌──16
│ └──nil
15
└──10

┌──18
16
└──15

移除10导致15的左转。请随意尝试一些你自己的测试案例。

呜呼! AVL树是你寻找终极二进制搜索树的高潮。自平衡特性保证了insert和remove操作的最佳性能，其时间复杂度为O(log n)。

关键点¶

自平衡树通过在树中添加或删除元素时执行平衡程序来避免性能下降。
AVL树通过在树不再平衡时重新调整树的一部分来保持平衡。
平衡是通过在节点插入和移除时的四种树的旋转来实现的。

从这里开始，要去哪里？¶

虽然AVL树是BST的第一个自我平衡的实现，但其他的，如红黑树和splay树，后来也加入了这个行列。如果你有兴趣，你可以在raywenderlich.com Swift算法俱乐部中查看这些算法。找到他们的地址：https://github.com/raywenderlich/swift-algorithm-club/tree/master/Red-Black%20Tree和https://github.com/raywenderlich/swift-algorithm-club/tree/master/Splay%20Tree分别。

16.AVL树¶