AVL 树（以发明者 Adelson-Velsky 和 Landis 命名）是一种自平衡二叉搜索树 (BST)。 自平衡将其方法的时间复杂度提高到 O(log n)。 正如我们所见，BST 的最坏情况时间复杂度最接近线性 Ο(n)。

保持任何左右节点之间的高度差最多为 1 使得树高度等于 log n。

任何插入或删除都可能需要通过节点旋转来重新平衡树。

像所有树一样，主要属性是根：

class AVLTree {
  var root: AVLNode?
}

class AVLNode {
  var left: AVLNode?
  var right: AVLNode?
  var value: Int
  var height: Int = 0
  
  init(value: Int) {
    self.value = value
  }
}

AVLTree 节点的节点类似于二叉树的节点，但我们添加了“高度”属性。

让我们深入研究我们感兴趣的三个主要功能，搜索、插入和删除。

func search(value: Int) -> AVLNode? {
  var current = root
  while let node = current {
    if (node.value == value) {
      return node
    }
    current = value < node.value ? node.left : node.right
  }
  return nil
}

搜索就像二叉树一样简单； 我们遍历根直到找到值并返回节点，如果找不到则返回 nil。 注意这个时间； 我们采用了迭代方法，而不是递归方法。

func insert(value: Int) {
  root = insert(node: root, value: value)
}

让我们插入根并用新的根替换它；我们需要处理 2 个边缘情况，根为 nil，或者我们需要重新平衡它。

func insert(node: AVLNode?, value: Int) -> AVLNode {
  guard var node = node else {
    return AVLNode(value: value)
  }
  if (value < node.value) {
    node.left = insert(node: node.left, value: value)
  } else {
    node.right = insert(node: node.right, value: value)
  }
  return rebalance(node: &node)
}

如果当前给定节点为 nil，我们创建一个新节点并返回它。如果新值小于当前节点，则从当前节点的左节点插入并替换，否则，从当前节点的右节点插入并替换。最后，重新平衡当前节点并将其返回。

如您所见，它非常简单；所有的魔法都发生在“重新平衡”方法中，我们将在本文中很快看到，但让我们先看看 remove 方法。

func remove(value: Int) {
  root = remove(node: &root, value: value)
}

让我们从根开始删除并用新的根替换它；我们需要处理 2 个边缘情况，根为 nil，或者我们需要重新平衡它。

func remove(node: inout AVLNode?, value: Int) -> AVLNode? {
  guard let current = node else {
    return nil
  }
  if (value < current.value) {
    node?.left = remove(node: ¤t.left, value: value)
  } else if (value > current.value) {
    node?.right = remove(node: ¤t.right, value: value)
  } else {
    if current.left == nil {
      node = current.right
    } else if current.right == nil {
      node = current.left
    } else {
      let minimumChild = getMinimumChild(node: current.right!)
      node?.value = minimumChild.value;
      node?.right = remove(node: ¤t.right, value: current.value);
    }
  }
  if var newNode = node {
    node = rebalance(node: &newNode)
  }
  return node;
}

如果当前给定节点为 nil，则返回 nil。

如果给定值小于当前节点，则从当前的左节点中移除并替换它；否则，从当前的右节点中删除并替换它。

现在，我们在找到给定值的情况下。如果当前的左节点为nil，则返回右孩子；如果右边的为 nil，则返回左边的。

最有趣的情况是如果两个孩子都不为零，我们需要移除当前节点，但我们需要保持平衡以遵循 AVLTree 要求。左侧的所有节点都必须小于当前节点值，右侧的节点必须大于当前节点值。为此，我们将用右子树中的最小值替换当前节点值并将其从中删除。

然后，如果给定节点不是 nil，让我们重新平衡它。

最后返回给定的节点。

现在我们已经了解了所有必需的方法，让我们了解所有辅助方法。

func height(node: AVLNode?) -> Int {
  guard let node = node else {
    return -1
  }
  return node.height
}

如果节点不为零，则返回节点的高度（已计算）； 否则，返回-1。

func getBalance(node: AVLNode?) -> Int {
  guard let node = node else {
    return 0
  }
  return height(node: node.right) - height(node: node.left)
}

为了获得一个节点的平衡，我们需要返回它的右节点高度和它的左节点高度之间的差值，如果该节点是 nil，我们需要返回 1 或 0。

func updateHeight(node: AVLNode?) {
  guard let node = node else {
    return
  }
  node.height = 1 + max(height(node: node.left), height(node: node.right))
}

为了更新节点的高度，我们将其两个子节点的最大高度加 1。

func getMinimumChild(node: AVLNode) -> AVLNode {
  var current: AVLNode = node
  while let left = current.left {
    current = left
  }
  return current
}

从 AVL 或 BST 子树中获取最小节点，返回其最左叶。

func rebalance(node: inout AVLNode) -> AVLNode {
  updateHeight(node: node)
  let balance = getBalance(node: node)
  if balance > 1 { // more nodes on the right
    guard let right = node.right else {
      return node // impossible case
    }
    if (height(node: right.right) > height(node: right.left)) {
      return rotateLeft(node: node) // more on the right right
    } else {
      node.right = rotateRight(node: right)
      return rotateLeft(node: node) // more on the right left
    }
  } else if balance < -1 { // more nodes on the left
    guard let left = node.left else {
      return node // impossible case
    }
    if (height(node: left.left) > height(node: left.right)) {
      return rotateRight(node: node) // more on the left left
    } else {
      node.left = rotateLeft(node: left)
      return rotateRight(node: node) // more on the left right
    }
  }
  return node
}

要重新平衡一个节点，首先，让我们更新它的高度并获得它的平衡； 如果它的平衡为-1、0或1，则树已经平衡； 没事做。 如果大于 1，则右侧的节点多于左侧的节点，如果小于 -1，则左侧的节点多于右侧的节点。 在这些情况下，我们需要旋转节点来重新创建平衡。

有四种类型的旋转：

- 向左旋转：

右节点的高度大于左节点的高度，右节点的高度大于右左节点的高度。

在这种情况下，我们只需要应用左旋转（逆时针，见箭头）。

- 左右旋转：

右节点的高度大于左节点的高度，右节点的高度小于右左节点的高度。

在这种情况下，我们需要应用两次旋转（见箭头），首先是右旋转，然后是左旋转。

- 右旋：

左侧节点的高度大于右侧节点的高度，并且左侧节点的高度大于左侧节点的高度。

在这种情况下，我们需要应用右旋转（顺时针，见箭头）。

- 左右旋转：

左侧节点的高度大于右侧节点的高度，并且左侧节点的高度小于左侧节点的高度。

在这种情况下，我们需要应用两次旋转（见箭头），首先是左旋转，然后是右旋转。

让我们看看这些旋转函数：

func rotateRight(node: AVLNode) -> AVLNode {
  guard let left = node.left else {
    return node // node.left is the rotating point
  }
  let right = left.right
  left.right = node
  node.left = right
  updateHeight(node: node)
  updateHeight(node: left)
  return left
}

这种右旋转将给定节点与其左子节点交换。

func rotateLeft(node: AVLNode) -> AVLNode {
  guard let right = node.right else {
    return node // node.right is the rotating point
  }
  let left = right.left
  right.left = node
  node.right = left
  updateHeight(node: node)
  updateHeight(node: right)
  return right
}

这个左旋转将给定节点与其右子节点交换。

这种 AVLTree 或自平衡二叉搜索树看起来相当复杂，但一旦我们了解了旋转逻辑以及平衡的工作原理，它就会变得更加清晰。

时间复杂度：

• 插入：O(log n)，由于平衡属性，
• 移除：O(log n)，由于平衡的属性，
• 搜索：O(log n)，这要归功于平衡的属性。

如何使用 AVL 树：

let tree = AVLTree()
tree.insert(value: 21)
tree.insert(value: 7)
tree.insert(value: 6)
tree.insert(value: 5)
tree.insert(value: 2)
tree.remove(value: 6)
let node5 = tree.search(value: 5) // return the node containing 5
let node8 = tree.search(value: 8) // return nil

关注七爪网，获取更多APP/小程序/网站源码资源！