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
Why is it unnecessary to write the base in Θ(log N)?
What is log2 1,000,000,000?
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?