Looking back at the classics: Generic data types in Swift (Part 4)
by Ana Márquez Velázquez- •
- February 04, 2016
- •
- swift• generics• ios• abstract• data• types• queues• bst
- |
- 7 minutes to read.
To demonstrate the power of Swift Generics, we’re going to show you two different ways to implement a binary search tree. First, we’ll cover a typical object-oriented implementation, and then a cleaner method based on Swift enums.
Definition
“A binary search tree is a rooted binary tree in which each internal node stores a key (and optionally, an associated value) and may have two distinguished sub-trees, commonly denoted left and right. The tree additionally satisfies the binary search tree property, which states that the key in each node must be greater than all keys stored in the left sub-tree, and smaller than all keys in right sub-tree.” Wikipedia
Advantage & Disadvantages:
The main advantage of binary search trees is that they can be really efficient sorting and searching. If you want to dig deeper into them, you can find more information in Wikipedia
Class-based Implementation
Here’s an example of a BST written in Swift. While using generics, the structure also stores any type of object and supports nil values. For clarity purposes, values contained in the tree will work as keys too, but the usual implementation associates keys with values (i.e.: telephone numbers and names).
We can implement search either iteratively or recursively. For clarity purposes, we’ve chosen the latter, even though Swift won’t guarantee tail-recursion optimization. We first examine the root node when searching, which has four distinct options (we express these as a switch block). At first glance, we’ll either have no keys (in which case we will return false as it’s an empty tree), or the key contained in the root will equal the provided element (which means the result exists in our tree, and we return true). We could also end up in a situation where our key is bigger than the current one, leading us to perform a recursive search in the left tree (if it exists), or smaller than the current one, in which case we’ll need to continue the search on the right tree.
Insertion is implemented similarly to a search operation until we reach an external node where we can insert the new key/value. Removal of a key starts with another search, but there are some situations where deleting an element should be done with extra care. Removing a node with no children is as simple as removing it from the tree. If it has one child, we only need to replace the father with the child, but removing a node with two children requires more complex logic and uses an auxiliary method findMin to recursively locate the minimum value of our right tree. This value will substitute the current node, and this operation will need to be performed on all its children until we reach the external nodes. This way, we’ll guarantee that the entire tree is sorted after the removal. This is potentially the most intensive operation of them all.
Let’s take a look at our first approach at an implementation of a BST in a Swift class-based:
public class BST<T:Comparable>{
var data: T?
var left: BST?
var right: BST?
init(data:T){
self.data = data
}
func search(element:T) -> Bool {
switch(self.data, self.left, self.right) {
case (.None, _ ,_):
return false
case let (data, _, _) where data == element:
return true
case let (data, .Some(l), _) where data > element:
return l.search(element)
case let (data, _, .Some(r)) where data < element:
return self.right?.search(element)
default:
return false
}
return false
}
func insert(element:T){
switch(self.data, self.left, self.right) {
case let (.None, _, _):
self.data = element
case let (data, .Some(l), _) where data > element:
l.insert(element)
case let (data, .None, _) where data > element:
self.left = BST(data:element)
case let (data, _, .Some(r)) where data <= element:
r.insert(element)
case let (data, _, .None) where data <= element:
self.right = BST(data:element)
default:
println("Error")
}
}
func remove(element:T) -> BST?{
switch(self.data, self.left, self.right) {
case let (.None, _, _):
return self
case let (data, .Some(l), _) where data > element:
self.left = l.remove(element)
case let (data, _, .Some(r)) where data < element:
self.right = r.remove(element)
case let (data, .None, .None) where data == element:
return .None
case let (data, .Some(l), .None) where data == element:
return left
case let (data, .None, .Some(r)) where data == element:
return right
case let (data, .Some(l), .Some(r)) where data == element:
let a = findMin(self.right!)
self.data = a?.data
self.right = r.remove(self.data!)
default:
println("Error")
}
return self
}
func findMin(var root:BST)-> BST?{
while (root.data != .None) {
if let left = root.left{
root = root.left!
}else{
return root
}
}
return root
}
public var description: String {
switch (self.data, self.left, self.right) {
case let (.None, _, _):
return "."
case let (data, .Some(l), .Some(r)):
return "[\(l.description) \(data) \(r.description)]"
case let (data, .None, .Some(r)):
return "[(.) \(data) \(r.description)]"
case let (data, .Some(l), .None):
return "[\(l.description) \(data) (.)]"
case let (data, .None, .None):
return "[(.) \(data) (.)]"
default:
return ""
}
}
}
##The power of Swift enums An enumeration defines a common type of group of related values and enables you to work with those values utilizing typesafe within your code. This allows us to simplify our code and make it clearer. In this case, we can use an immutable binary search tree, so it’s safe in multithreaded environments. They are easier to understand and also offer greater security than mutable objects. The implementation of the different methods are similar to the above ones, using recursivity in all its functions.
We can define a binary search tree as an ADT using enums like this:
internal enum TreeBranch {
case Left
case Right
}
public indirect enum BinarySearchTree<T:Comparable> {
case Empty
case Node(T, left: BinarySearchTree, right: BinarySearchTree)
func «head»() -> T? {
switch self{
case .Empty:
return .None
case let .Node(T, left: _, right: _):
return T
}
}
func «getBranch»(branch: TreeBranch) -> BinarySearchTree {
switch self {
case let .Node(_, left: _, right: right) where branch == .Right:
return right
case let .Node(_, left: left, right: _) where branch == .Left:
return left
default:
return .Empty
}
}
func «add»(element:T) -> BinarySearchTree {
switch self {
case .Empty:
return BinarySearchTree.Node(element, left: BinarySearchTree.Empty, right: BinarySearchTree.Empty)
case let .Node(value, left, right):
if element > value {
return BinarySearchTree.Node(value, left: left, right: right.add(element))
} else {
return BinarySearchTree.Node(value, left: left.add(element), right: right)
}
}
}
func «search»(element:T) -> Bool{
switch self{
case .Empty:
return false
case let .Node(value, _, _) where element == value:
return true
case let .Node(value, left, _) where value > element:
return left.search(element)
case let .Node(value, _, right) where value < element:
return right.search(element)
default:
break
}
return false
}
func «remove»(element:T) -> BinarySearchTree? {
switch self {
case .Empty:
return self
case let .Node(value, left, right) where value > element:
return BinarySearchTree.Node(value, left: left.remove(element)!, right: right)
case let .Node(value, left, right) where value < element:
return BinarySearchTree.Node(value, left:left, right: right.remove(element)!)
case let .Node(value, .Empty, .Empty) where value == element:
return BinarySearchTree.Empty
case let .Node(value, left, .Empty) where value == element:
return left
case let .Node(value, .Empty, right) where value == element:
return right
case let .Node(value, left, right) where value == element:
let a = findMin(right)
switch a {
case let .Node(value, _,_):
return BinarySearchTree.Node(value, left: left, right: right.remove(value)!)
default:
return .Empty
}
default:
break
}
return self
}
private func findMin( root:BinarySearchTree) -> BinarySearchTree<T> {
switch root{
case .Node(_, .Empty, _):
return root
case let .Node(_, left,_):
return findMin(left)
default:
return .Empty
}
}
}
»head|Returns the element the head the current BST«
»getBranch|Returns a new BST with the provided branch as specified in the provided enum (left or right)«
»add|Returns a new BinarySearchTree with the provided item added to the current contents.«
»search|Checks if a certain element is included in the current BinarySearchTree«
»remove|Removes the provided element from the current BinarySearchTree , and returns a new BinarySearchTree without that element«
The logic of the enum is much more readable than the class-based. In this case, we can avoid duplication of code. For instance when adding elements we’re reducing the switch block to two cases instead of five!
Keep in mind that you can play with the source files of this article by downloading our interactive Playground. Keep reading our future posts in the series for more generic goodies! If you have any questions, opinions, or suggestions, contact us through Facebook, Twitter or the comments section below.