Home iOS & Swift Books Data Structures & Algorithms in Swift

16
AVL Trees Written by Kelvin Lau

Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as scrambled text.

You can unlock the rest of this book, and our entire catalogue of books and videos, with a raywenderlich.com Professional subscription.

In the previous chapter, you learned about the O(log n) performance characteristics of the binary search tree. However, you also learned that unbalanced trees can deteriorate the performance of the tree, all the way down to O(n). In 1962, Georgy Adelson-Velsky and Evgenii Landis came up with the first self-balancing binary search tree: The AVL Tree. In this chapter, you’ll dig deeper into how the balance of a binary search tree can impact performance and implement the AVL tree from scratch!

Understanding balance

A balanced tree is the key to optimizing the performance of the binary search tree. In this section, you’ll learn about the three main states of balance.

Perfect balance

The ideal form of a binary search tree is the perfectly balanced state. In technical terms, this means every level of the tree is filled with nodes, from top to bottom.

Derdopjpm joyivfaw hpei

“Good-enough” balance

Although achieving perfect balance is ideal, it is rarely possible. A perfectly balanced tree must contain the exact number of nodes to fill every level to the bottom, so it can only be perfect with a particular number of elements.

Fowotpuv blue

Unbalanced

Finally, there’s the unbalanced state. Binary search trees in this state suffer from various levels of performance loss, depending on the degree of imbalance.

Ezrizuhtij csuen

Implementation

Inside the starter project for this chapter is an implementation of the binary search tree as created in the previous chapter. The only difference is that all references to the binary search tree are renamed to AVL tree.

Measuring balance

To keep a binary tree balanced, you’ll need a way to measure the balance of the tree. The AVL tree achieves this with a height property in each node. In tree-speak, the height of a node is the longest distance from the current node to a leaf node:

1 0 0 2 3 2
Qitid lacdup punn kaoqfsw

public var height = 0
public var balanceFactor: Int {
  leftHeight - rightHeight
}

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

public var rightHeight: Int {
  rightChild?.height ?? -1
}
79 8 6 -1 9 9 5 0 57 28 92 Gihufwo (Yosb) Nuixkf (Qafmy)
ESG fyei rakt yasozqa riskapm eqd ciozkkb

68 8 -6 6 -9 7 6 3 5 3 6 9 64 77 98 55 Sifejgu (Xogh) Hoezhg (Juppf)
Ezwawatluw skoa

Rotations

The procedures used to balance a binary search tree are known as rotations. There are four rotations in total for the four different ways that a tree can become unbalanced. These are known as left rotation, left-right rotation, right rotation and right-left rotation.

Left rotation

The imbalance caused by inserting 40 into the tree can be solved by a left rotation. A generic left rotation of node x looks like this:

Azkuj jesufuex Seduyi joxubiav I T B R J C V W E B X J J S
Pitf gafokeiy axwwean ig wama b

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
}
Ujvok mexp nafivu ad 28 3 2 0 0 55 18 57 15 7 62 Vameda yemk vasopo az 07 4 -8 -7 1 7 63 92 68 97 95

Right rotation

Right rotation is the symmetrical opposite of left rotation. When a series of left children is causing an imbalance, it’s time for a right rotation.

Ruzele fuxnx jayeyo uc v G W U B W W L Xiyizo yelsy gilova uc p S F W A J D S
Yeqfr dipokuag ukrdaej ef bumu b

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
}

Right-left rotation

You may have noticed that the left and right rotations balance nodes that are all left children or all right children. Consider the case in which 36 is inserted into the original example tree.

0 32 -7 02 5 72 4 72 3 11
Odqemved 96 ot neqq kfufs ut 45

Dovn qoyisuam or 10 0 90 1 76 5 15 9 08 5 18 Sekmn hexive ob 57 6 80 -7 49 6 39 -2 35 6 88 Farehe rozoxuinv 1 20 -8 00 1 93 0 39 3 24
Jhi wafhm-xabm codikauq

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

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

Left-right rotation

Left-right rotation is the symmetrical opposite of the right-left rotation. Here’s an example:

Meskd wiquso es 54 5 03 4 58 6 05 3 32 7 68 Vineki rosigiudn 8 1 -5 6 7 08 87 70 22 00 Miyn qilita or 49 9 4 3 1 29 69 87 50 18 5
Cno hafr-higmg zeheraoh

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

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

Balance

The next task is to design a method that uses balanceFactor to decide whether a node requires balancing or not. Write the following method below leftRightRotate:

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

  switch node.balanceFactor {
  case 2:
    // ...
  case -2:
    // ...
  default:
    return node
  }
}
16 3 4 2 0 8 80 1 -8 9 0 7
Mirfk gurivo og nuzp-xifqm jereru?

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
  }
}

Revisiting insertion

You’ve already done the majority of the work. The remainder is fairly straightforward. Update insert(from:value:) to the following:

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
}
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

Revisiting remove

Retrofitting the remove operation for self-balancing is just as easy as fixing insert. In AVLTree, find remove and replace the final return statement with the following:

let balancedNode = balanced(node)
balancedNode.height = max(balancedNode.leftHeight, balancedNode.rightHeight) + 1
return balancedNode
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

Key points

  • A self-balancing tree avoids performance degradation by performing a balancing procedure whenever you add or remove elements in the tree.
  • AVL trees preserve balance by readjusting parts of the tree when the tree is no longer balanced.
  • Balance is achieved by four types of tree rotations on node insertion and removal.

Where to go from here?

While AVL trees were the first self-balancing implementations of a BST, others, such as the red-black tree and splay tree, have since joined the party. If you’re interested, you check those out in the raywenderlich.com Swift Algorithm Club. Find them at at: https://github.com/raywenderlich/swift-algorithm-club/tree/master/Red-Black%20Tree and https://github.com/raywenderlich/swift-algorithm-club/tree/master/Splay%20Tree respectively.

Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.

Have feedback to share about the online reading experience? If you have feedback about the UI, UX, highlighting, or other features of our online readers, you can send them to the design team with the form below:

© 2021 Razeware LLC

You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a raywenderlich.com Professional subscription.

Unlock Now

To highlight or take notes, you’ll need to own this book in a subscription or purchased by itself.