Programming #4: Trees

The next data structure we’ll be talking about is a tree. Like their real life counterparts, trees as a data structure have a root, some branches, some leaves, etc. In programming, a tree is basically just an extension of a linked list. Recall that an element or node in a linked list stores its value and a pointer to the next value. With a node in a tree, we store the value of a node and the next values for its children. A tree must also be completely connected, if we start at the first node, we can reach every element in the tree. There will also be no cycles, going down a tree can’t bring us back up.

Terminology

A tree can be described by how many levels it has. The root is the first node in the tree and occurs at level 1. Anything connected to the root occurs at level 2, and so on. A parent is a node connected to other nodes at a lower level. A child is a node connected to other nodes at a higher level. The nodes at the end of the tree with no children are called leaves. Connections between a parent and a child are called edges, and a collections of edges is called a path. The height of a node is just the number of edges between it and the furthest leaf on the tree. The depth of a node is the inverse, the number of edges back up to the root.

Traversal

Recall that when we looked at list-based data structures, we could just move through the list in order to see every element. Trees do not have a clear ordered path that can be traversed. If we start at the root, should we go left or right, should we check all nodes on the same level or all the way down first?

There are two main approaches to this problem, depth-first search (DFS) and breath-first search (BFS). With DFS, we give priority to exploring children nodes. With BFS, we give priority to exploring nodes on the same level.

An example of a BFS algorithm is the level order search. We start at the root and then visit all of its children on the second level, then visit all of those node’s children on the third level, and continue till we reach the leaves.

An example of a DFS algorithm is the pre-order search. We start at the root and traverse down the leftmost children until we hit a leaf. As we move down we check off every node we travel through. When we hit the leaf we go back up to the parent and traverse to any right children. This process continues until we’ve seen everything. With an in-order search we would only check off a node when we’ve seen its child and come back to it. With post-order search we would only check off a node if we’ve seen all of its children.

An example of a pre-order search implemented in Python:

class Node(object):
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BinaryTree(object):
    def __init__(self, root):
        self.root = Node(root)

    def search(self, find_val):
        """
        Return True if the value
        is in the tree, return
        False otherwise.
        """
        return self.preorder_search(tree.root, find_val)

    def print_tree(self):
        """
        Print out all tree nodes
        as they are visited in
        a pre-order traversal.
        """
        return self.preorder_print(tree.root, "")[:-1]

    def preorder_search(self, start, find_val):
        """
        Helper method - use this to create a 
        recursive search solution.
        """
        if start:
            if start.value == find_val:
                return True
            else:
                return self.preorder_search(start.left, find_val) or \
                       self.preorder_search(start.right, find_val)
            
        return False

    def preorder_print(self, start, traversal):
        """
        Helper method - use this to create a 
        recursive print solution.
        """
        if start:
            traversal += (str(start.value) + "-")
            traversal = self.preorder_print(start.left, traversal)
            traversal = self.preorder_print(start.right, traversal)
            
        return traversal

Binary Search Tree

The searching algorithms we talked about so far will take O(n) in the worse case, since they will need to check every possible node. However, rules can be added to our tree to speed up this process. Depending on our goal, there are many different approaches we can take. For example, a binary search tree (BST) is a special case binary tree where every value to the left of a particular node is smaller than that node and every value to the right is larger.

Now when we search we will know which direction to go from the start. If the value we are looking for is larger than the value of the node we are on, we go right. Search on a balanced BST will take O(log(n)) which is the height of the tree. If the tree is non-balanced, for example a tree with one long leg, the search time will be O(n).

An example of a BST implemented in Python:

class Node(object):
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BST(object):
    def __init__(self, root):
        self.root = Node(root)

    def insert(self, new_val):
        """
        Add node to BST.
        """
        self.insert_helper(self.root, new_val)
        
    def insert_helper(self, current, new_val):
        """
        Find location for insertion.
        """
        if current.value < new_val:
            if current.right:
                self.insert_helper(current.right, new_val)
            else:
                current.right = Node(new_val)
        else:
            if current.left:
                self.insert_helper(current.left, new_val)
            else:
                current.left = Node(new_val)

    def search(self, find_val):
        """
        Implement search in BST.
        """
        return self.search_helper(self.root, find_val)
    
    def search_helper(self, current, find_val):
        """
        Find location in search.
        """
        if current:
            if current.value == find_val:
                return True
            elif current.value < find_val:
                return self.search_helper(current.right, find_val)
            else:
                return self.search_helper(current.left, find_val)
            
        return False

Heaps

A heap is another special case tree with the added rule that elements are arranged in increasing or decreasing order. In other words, the root element is either the maximum or minimum value in the tree. In a max heap, the parent must always be larger than its children. In a min heap, the opposite. Finding the maximum or minimum value will happen in constant time O(1), but searching further will take O(n) since we don’t know what direction to go from the root node.

The main benefit of heaps is that insertion times are quicker since our level structure is explicit. This makes the structure excellent for implementing a priority queue. For example, if you want to queue up items and then only dequeue the maximum or minimum value. The worst case insertion time will be O(log(n)).

In Python, the heapq library has this functionality built-in.

Advertisements

Author: David Shahrestani

"I have the strength of a bear, that has the strength of TWO bears."

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s