Class 28 - Growing Trees


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.



logb n = x means bx = n

Changing bases

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

What is log2 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)
                return None
            if self.right_child():
                return self.right_child().find_match(value)
                return None

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