Class 27 - Of Trees and Logs


Everyone should either have (1) completed the Blue Belt level and be working on Project 5 (target completion by next Monday, 11 April), or (2) be making progress to completing the Blue Belt level. If you are stuck, not making progress, or unsure what you should be doing, make sure to check in with me today (in person, slack, or email) or at office hours tomorrow.


Notes and Questions

What is the search problem?

FindMatch Problem:

Inputs: lst, a list of N elements of type T; ftest, a test function T → Bool.
Output: an element, e, of lst such that ftest(e) is True, or None if no such element exists

What is the complexity of FindMatch?

def find_match(lst, ftest):
    If there is any element e in lst that
    satisfies ftest(e) == True, returns a
    satisfying element e.

    Otherwise, returns None.

What can we do if the asymptotic complexity of the problem we want to solve is too high?


Recall: A List is either (1) None, or (2) a pair whose second part is a List.

What is a Tree?

class Tree:
    A Tree is a data structure where nodes have
    zero or more children, and one parent (except
    the root which has no parent).

    All the children and parents are Tree objects or None.
    def __init__(self, value):
        self._parent = None
        self._children = []
        self._value = value

    def add_child(self, child):
        assert isinstance(child, Tree) 
        child._parent = self

    def traverse(self):
        Returns a list of all Tree objects in this tree.
        result = [self]
        for subtree in self._children:
            if subtree:
                result += subtree.traverse()
                result += [None]
        return result

Binary Tree

from tree import Tree

class BinaryTree(Tree):
    A tree where there are at most 2 children per node.

    def __init__(self, value):
        self._children = [None, None]

    def add_child(self, child):
        raise RuntimeError("Add child not allowed!")

    def set_left_child(self, child):
        assert isinstance(child, BinaryTree)
        assert not self.left_child()
        self._children[0] = child

    def set_right_child(self, child):
        assert isinstance(child, BinaryTree)
        assert not self.right_child()
        self._children[1] = child

    def left_child(self):
        return self._children[0]

    def right_child(self):
        return self._children[1]

    def traverse(self):
        nodes = []
        if self.left_child():
            nodes += self.left_child().traverse()
        if self.right_child():
            nodes += self.right_child().traverse()
        return nodes

Ordered Binary Tree

from binarytree import BinaryTree

class OrderedBinaryTree(BinaryTree):
    A tree where the ordered invariant is preserved:
        if left_node is left of current_node,
            fcompare(left_node.value, current_node.value)
        must be True

    def __init__(self, value, fcompare = lambda a, b: a < b):
        self._fcompare = fcompare

    def add_child(self, child):
        raise RuntimeError("Cannot add children directly!")

    def add_node(self, node):
        """Inserts this child in a proper location."""
        assert isinstance(node, OrderedBinaryTree)

        if self._fcompare(node._value, self._value):
            if self.left_child():
            if self.right_child():

What is the complexity of searching for a node in an OrderedBinaryTree?