Class 28 - Growing Trees

Schedule

Everyone should either have (1) completed the Blue Belt level and be working on Project 5 (target completion by 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.

Slides

Logarithms

log^b n = x means b^x = n

Changing bases

Why is it unnecessary to write the base in Θ(log N)?

What is log² 1,000,000,000?

Growing Trees

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

What is a Tree?

See Notes 27 for code for trees (and download link).

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 find_match(self, value):
        """
        Returns a node of self where node.value == value,
        or None if no such node exists.
        """
        if self._value == value:
            return self
        if self._fcompare(value, self._value):
            if self.left_child():
                return self.left_child().find_match(value)
            else:
                return None
        else:
            if self.right_child():
                return self.right_child().find_match(value)
            else:
                return None

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