Looking back at the classics: Generic data types in Swift (Part 4)

Looking back at the classics: Generic data types in Swift (Part 4)

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.

blog comments powered by Disqus

Ensure the success of your project

47 Degrees can work with you to help manage the risks of technology evolution, develop a team of top-tier engaged developers, improve productivity, lower maintenance cost, increase hardware utilization, and improve product quality; all while using the best technologies.