Home iOS & Swift Books Data Structures & Algorithms in Swift

14
Binary Search 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.

A binary search tree, or BST, is a data structure that facilitates fast lookup, insert and removal operations. Consider the following decision tree where picking a side forfeits all the possibilities of the other side, cutting the problem in half.

no yes no yes no yes no yes yes no Should I go the gym? Did I go yesterday? Did I go jogging yesterday? Am I still feeling sore? Did I run 5km? Go to the gym Go to the gym Go to sleep Rest for the day Break Go to the gym Did you slack off in the last session?

Once you make a decision and choose a branch, there is no looking back. You keep going until you make a final decision at a leaf node. Binary trees let you do the same thing. Specifically, a binary search tree imposes two rules on the binary tree you saw in the previous chapter:

  • The value of a left child must be less than the value of its parent.
  • Consequently, the value of a right child must be greater than or equal to the value of its parent.

Binary search trees use this property to save you from performing unnecessary checking. As a result, lookup, insert and removal have an average time complexity of O(log n), which is considerably faster than linear data structures such as arrays and linked lists.

In this chapter, you’ll learn about the benefits of the BST relative to an array and, as usual, implement the data structure from scratch.

Case study: array vs. BST

To illustrate the power of using a BST, you’ll look at some common operations and compare the performance of arrays against the binary search tree.

Consider the following two collections:

1 25 88 18 45 4 40 105 20 77 70 40 18 77 1 20 70 105 4 25 45 88

Lookup

There’s only one way to do element lookups for an unsorted array. You need to check every element in the array from the start:

8 52 90 40 50 0 07 983 25 55 76
Zuoljxetz quf 895

66 41 23 89 069 02 86 7 77 0 96
Zuijrheqs teq 810

Insertion

The performance benefits for the insertion operation follow a similar story. Assume you want to insert 0 into a collection:

4 04 75 02 83 6 07 450 03 86 58 0 8 17 63 22 14 0 96 919 82 75 50
Ojnubxuds 3 aj kiyveq etbax

50 53 23 96 238 31 13 1 37 7 40

Removal

Similar to insertion, removing an element in an array also triggers a shuffling of elements:

3 32 11 52 41 4 53 462 13 67 26 1 00 38 56 0 59 223 37 04 98 wapifi 63
Susuluhf 67 fgiv mwi aydon

10 70 85 55 912 74 95 2 87 6 59

Implementation

Open up the starter project for this chapter. In it, you’ll find the BinaryNode type that you created in the previous chapter. Create a new file named BinarySearchTree.swift and add the following inside the file:

public struct BinarySearchTree<Element: Comparable> {

  public private(set) var root: BinaryNode<Element>?

  public init() {}
}

extension BinarySearchTree: CustomStringConvertible {

  public var description: String {
    guard let root = root else { return "empty tree" }
    return String(describing: root)
  }
}

Inserting elements

Per the rules of the BST, nodes of the left child must contain values less than the current node. Nodes of the right child must contain values greater than or equal to the current node. You’ll implement the insert method while respecting these rules.

extension BinarySearchTree {

  public mutating func insert(_ value: Element) {
    root = insert(from: root, value: value)
  }

  private func insert(from node: BinaryNode<Element>?, value: Element)
      -> BinaryNode<Element> {
    // 1
    guard let node = node else {
      return BinaryNode(value: value)
    }
    // 2
    if value < node.value {
      node.leftChild = insert(from: node.leftChild, value: value)
    } else {
      node.rightChild = insert(from: node.rightChild, value: value)
    }
    // 3
    return node
  }
}
example(of: "building a BST") {
  var bst = BinarySearchTree<Int>()
  for i in 0..<5 {
    bst.insert(i)
  }
  print(bst)
}
---Example of: building a BST---
    ┌──4
  ┌──3
  │ └──nil
 ┌──2
 │ └──nil
┌──1
│ └──nil
0
└──nil
0 3 9 0 0 0 4 0 3 7 ruboghor ogqahikquk

7 8 1 0 2 2 3 1 1 4 infacurqoc fazukced 3 9 5

var exampleTree: BinarySearchTree<Int> {
  var bst = BinarySearchTree<Int>()
  bst.insert(3)
  bst.insert(1)
  bst.insert(4)
  bst.insert(0)
  bst.insert(2)
  bst.insert(5)
  return bst
}
example(of: "building a BST") {
  print(exampleTree)
}
---Example of: building a BST---
 ┌──5
┌──4
│ └──nil
3
│ ┌──2
└──1
 └──0

Finding elements

Finding an element in a BST requires you to traverse through its nodes. It’s possible to come up with a relatively simple implementation by using the existing traversal mechanisms that you learned about in the previous chapter.

extension BinarySearchTree {

  public func contains(_ value: Element) -> Bool {
    guard let root = root else {
      return false
    }
    var found = false
    root.traverseInOrder {
      if $0 == value {
        found = true
      }
    }
    return found
  }
}
example(of: "finding a node") {
  if exampleTree.contains(5) {
    print("Found 5!")
  } else {
    print("Couldn’t find 5")
  }
}
---Example of: finding a node---
Found 5!

Optimizing contains

You can rely on the rules of the BST to avoid needless comparisons. Back in BinarySearchTree.swift, update the contains method to the following:

public func contains(_ value: Element) -> Bool {
  // 1
  var current = root
  // 2
  while let node = current {
    // 3
    if node.value == value {
      return true
    }
    // 4
    if value < node.value {
      current = node.leftChild
    } else {
      current = node.rightChild
    }
  }
  return false
}

Removing elements

Removing elements is a little more tricky, as you need to handle a few different scenarios.

Case 1: Leaf node

Removing a leaf node is straightforward; simply detach the leaf node.

4 3 8 5 1 3
Lesupacv 4

Case 2: Nodes with one child

When removing nodes with one child, you’ll need to reconnect that one child with the rest of the tree:

7 0 3 1 7 5
Buducezj 4, bvofp put 8 dquyj

Case 3: Nodes with two children

Nodes with two children are a bit more complicated, so a more complex example tree will better illustrate how to handle this situation. Assume that you have the following tree and that you want to remove the value 25:

28 Nutahi 83 66 50 11 90 50 89 34 62 03 51 51 11

17 09 82 53 02 99 77 56 46 51 59 79

94 Wulkovos tamui 38 03 70 13 95 33 93 85 49 71 92 78

60 23 67 96 69 62 40 39 87 89 46 51 47

Implementation

Open up BinarySearchTree.swift to implement remove. Add the following code at the bottom of the file:

private extension BinaryNode {

  var min: BinaryNode {
    leftChild?.min ?? self
  }
}

extension BinarySearchTree {

  public mutating func remove(_ value: Element) {
    root = remove(node: root, value: value)
  }

  private func remove(node: BinaryNode<Element>?, value: Element)
    -> BinaryNode<Element>? {
    guard let node = node else {
      return nil
    }
    if value == node.value {
      // more to come
    } else if value < node.value {
      node.leftChild = remove(node: node.leftChild, value: value)
    } else {
      node.rightChild = remove(node: node.rightChild, value: value)
    }
    return node
  }
}
// 1
if node.leftChild == nil && node.rightChild == nil {
  return nil
}
// 2
if node.leftChild == nil {
  return node.rightChild
}
// 3
if node.rightChild == nil {
  return node.leftChild
}
// 4
node.value = node.rightChild!.min.value
node.rightChild = remove(node: node.rightChild, value: node.value)
example(of: "removing a node") {
  var tree = exampleTree
  print("Tree before removal:")
  print(tree)
  tree.remove(3)
  print("Tree after removing root:")
  print(tree)
}
---Example of: removing a node---
Tree before removal:
 ┌──5
┌──4
│ └──nil
3
│ ┌──2
└──1
 └──0

Tree after removing root:
┌──5
4
│ ┌──2
└──1
 └──0

Key points

  • The binary search tree is a powerful data structure for holding sorted data.
  • Elements of the binary search tree must be comparable. You can achieve this using a generic constraint or by supplying closures to perform the comparison.
  • The time complexity for insert, remove and contains methods in a BST is O(log n).
  • Performance will degrade to O(n) as the tree becomes unbalanced. This is undesirable, so you’ll learn about a self-balancing binary search tree called the AVL tree in Chapter 16.

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.