Trees

In computer science, a Tree is a very popular abstract data type (ADT) or a data structure implementing this ADT that simulates a hierarchical tree structure with a root value and subtrees of the children with a parent node, represented as a set of linked nodes.

A tree data structure can be defined recursively (locally) as a collection of nodes (starting at a root node), where each node is a data structure consisting of a value, together with a list of references to nodes (the children) with the constraints that no reference is duplicated and none point to the root.

Alternatively, a tree can be defined abstractly as a whole (globally) as an ordered tree, with a value assigned to each node. Both these perspectives are useful: while a tree can be analyzed mathematically as a whole, when actually represented as a data structure, it is usually represented and worked separately by a node (rather than as a list of nodes and an adjacency list of edges between nodes, as one may represent a digraph, for instance). For example, looking at a tree as a whole, one can talk about the parent node of a given node, but in general as a data structure, a given node only contains the list of its children but not a reference to its parent (if any).

In a previous chapter, we implemented a generic binary tree in Swift. The following is an improved version of that:

enum Tree<Element: Comparable> {
    case leaf(Element)
    indirect case node(lhs: Tree, rhs: Tree)
}

We define the Tree as an enum with three different cases:

  • Leaf: If we are at the end of a branch of the Tree; simply put, if a node does not have any children, then it is a Leaf
  • Node: A structure that has a left-hand side and right-hand side to it

The following figure presents an example Tree:

Trees

A Tree is generic and the elements in it are comparable.

Using this Tree is as simple as follows:

let functionalTree = Tree.node(lhs: Tree.leaf("First"),
                               rhs: Tree.node(lhs:
 Tree.leaf("Second"), 
                               rhs: Tree.leaf("Third")))

Our functionalTree is immutable or, in other words, it is persistent. It has a leaf as lhs and a node with two leaves as rhs. As this structure is immutable, we will not be worried whether it is going to change or not and we will be able to share this tree with other trees:

let secondFT = Tree.node(lhs: functionalTree, rhs: Tree.node(
                         lhs: Tree.leaf("Fourth"),
                         rhs: Tree.leaf("Fifth")))
let thirdFT = Tree.node(lhs: Tree.node(lhs: Tree.leaf("Fourth"),
                        rhs: Tree.leaf("Fifth")),
                        rhs: functionalTree)

In the preceding examples, we used our first Tree called functionalTree as a part of secondFT and thirdFT.

Contains

This Tree is far from complete and needs lots of functionality. For instance, we may need to check whether the Tree contains a specific value. To be able to do this, we need to add the following method to our Tree:

static func contains(_ key: Element, tree: Tree<Element>) -> Bool {
    switch tree {
    case .leaf(let element):
        return key == element
    case node(let lhs, let rhs):
        return contains(key, tree:lhs) || contains(key, tree:rhs)
    }
 }

We can test contains method as the following:

let isFound = Tree.contains("First", tree: functionalTree) // will
  return true

Binary Search Tree

Our assumption in our simple Tree was that only leaves contain a value. This is not always true. In fact, there are different types of trees with different utilities and a Binary Search Tree (BST) is one of them.

In computer science, binary search trees, sometimes called ordered or sorted binary trees, are a particular type of container: data structures that store items (such as numbers, names, and so on) in memory. They allow fast lookup, the addition and removal of items, and implementation of either dynamic sets of items or lookup tables that allow finding an item by its key (for example, finding the phone number of a person by name).

BSTs keep their keys in sorted order so that lookup and other operations can use the principle of binary search: when looking for a key in a tree (or a place to insert a new key), they traverse the tree from root to leaf, making comparisons to keys stored in the nodes of the tree and deciding, based on the comparison, whether to continue searching in the left or right subtrees. On an average, this means that each comparison allows the operations to skip about half of the tree so that each lookup, insertion, or deletion takes time proportional to the logarithm of the number of items stored in the tree. This is much better than the linear time required to find items by key in an (unsorted) array, but slower than the corresponding operations on hash tables.

Let's improve our simple tree and convert it to a BST:

enum BinarySearchTree<Element: Comparable> {
    case leaf
    indirect case node(lhs: BinarySearchTree, element: Element,
                       rhs: BinarySearchTree)
}

The BinarySearchTree tree is very similar to the previous Tree and the only difference is that node contains the element and not the leaf. Using it is as simple as follows:

let functionalBST = BinarySearchTree.node(lhs: BinarySearchTree.node(
  lhs: BinarySearchTree.leaf, element: 1,
  rhs: BinarySearchTree.leaf),
  element: 5, rhs: BinarySearchTree.node(lhs:BinarySearchTree.leaf,
  element: 9, rhs: BinarySearchTree.leaf))

Here, we create a BST as values stored in lhs are smaller than the root and values stored in rhs are larger than the root. In this example, lhs is a BST with 1 as value. Root has the value of 5 and rhs is a BST with 9 as value which is larger than root value.

Contains

Additionally, our contains method requires to be modified as it will search only in leaves. Let's improve this, assuming that our Tree is a BST:

static func contains(_ item: Element, tree: BinarySearchTree<Element>)
  -> Bool {
    switch tree {
    case .leaf:
        return false
    case .node(let lhs, let element, let rhs):
        if item < element {
            return contains(item, tree: lhs)
        } else if item > element {
            return contains(item, tree: rhs)
        }
        return true
    }
}

This method searches for a specific element and returns true if it finds it in node.

The following presents an example usage of this method:

let isFound = BinarySearchTree.contains(9, tree: functionalBST)

The isFound variable is going to be true in this case.

Size

To make this BST a little more complete, let's implement a property to check for its size:

var size: Int {
    switch self {
    case .leaf:
        return 0
    case .node(let lhs, _, let rhs):
        return 1 + lhs.size + rhs.size
    }
}

This computed property is going to provide the size of the BST and we can use it as follows:

print(functionalBST.size) // prints "3"

Elements

It would be great to be able to generate an array from BST elements. This can be done as follows:

var elements: [Element] {
    switch self {
    case .leaf:
        return []
    case .node(let lhs, let element, let rhs):
        return lhs.elements + [element] + rhs.elements
    }
}

Empty

We can implement a helper method to generate empty BSTs as follows:

static func empty() -> BinarySearchTree {
    return .leaf
}

The following is a computed property to check whether the BST is empty:

var isEmpty: Bool {
    switch self {
    case .leaf:
        return true
    case .node(_, _, _):
        return false
    }
}

Let's test these functions:

let emptyBST = BinarySearchTree<Int>.empty()
print(emptyBST.isEmpty)

In the preceding code, we created an empty BST and checked whether it is empty using the isEmpty property. Obviously, the result is going to be true.

This BST implementation is far from complete and requires to be improved by implementing methods to check whether it is a BST.

At the end, our BST becomes the following:

enum BinarySearchTree<Element: Comparable> {
    case leaf
    indirect case node(lhs: BinarySearchTree, element: Element,
                       rhs: BinarySearchTree)
 
    var size: Int {
        switch self {
        case .leaf:
            return 0
        case .node(let lhs, _, let rhs):
            return 1 + lhs.size + rhs.size
        }
    }

    var elements: [Element] {
        switch self {
        case .leaf:
            return []
        case .node(let lhs, let element, let rhs):
            return lhs.elements + [element] + rhs.elements
        }
    }

    var isEmpty: Bool {
        switch self {
        case .leaf:
            return true
        case .node(_, _, _):
            return false
        }
    }

    init() {
        self = .leaf
    }

    static func empty() -> BinarySearchTree {
        return .leaf
    }

    init(element: Element) {
        self = .node(lhs: .leaf, element: element, rhs: .leaf)
    }

    static func contains(_ item: Element,
                           tree: BinarySearchTree<Element>)
      -> Bool {
        switch tree {
        case .leaf:
            return false
        case .node(let lhs, let element, let rhs):
            if item < element {
                return contains(item, tree: lhs)
            } else if item > element {
                return contains(item, tree: rhs)
            }
            return true
        }
    }
}

Even though it does not represent a full implementation of a BST, we were able to develop it in a functional style, and we will be able to share and reuse the tree among other trees because they are immutable.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset