CS 70

Key Points

  • A binary search tree is
    • A binary tree such that…
    • The key in every node is bigger than all keys in its left subtree and smaller than all keys in its right subtree.
  • A BST is designed for search:
    • Applications where we need to efficiency store and find data.
    • Associative containers that associate keys with values (like Python dictionaries).
  • BST lookup:
    • Compare the key to the current node.
    • If the same, we're done! If smaller, go left. If larger, go right.
  • BST insert:
    • Use a similar lookup process to find a spot at the bottom of the tree for the new key.
    • Connect the new node to the bottom of the tree.
  • BST delete:
    • Use lookup to find the node with the key.
    • If no children: just remove it!
    • If one child: move the child up to the node's place.
    • If two children: replace the node with the largest key smaller than the one being removed (the rightmost descendant of the left child).
  • Complexity of Trees (Balanced and Unbalanced):
    • Insert and delete complexities depend on lookup.
    • Lookup complexity is \( \mathrm{O}(h) \), where \( h \) is the height of the tree.
    • Height can vary depending on insertion order!
    • Stick: \( h \in \Theta(n) \).
    • Well-balanced: \( h \in \Theta( \log{n} ) \).
    • So complexity of all these operations:
      • Stick: \( \mathrm{O}(n) \).
      • Balanced: \( \mathrm{O}( \log{n} ) \).
      • Overall (if there's no guarantee of balance): \( \mathrm{O}(n) \).
  • Recursive helper functions:
    • Member functions usually operate on a specific instance of a class (e.g., one whole tree).
      • The interface a member function provides to the user probably doesn't leave it well suited for that function itself to be recursive.
        • For example, there is no smaller IntTree instance to recurse on (internally, our tree is made of Nodes).
    • Recursive functions necessarily have the data they're working on as a parameter, since each successive call needs to pass in a smaller variant of the problem to solve, until we hit the base case.
      • The parameters a recursive function needs don't necessarily provide the right interface for the user.
    • We can combine the two and address these issues by having the member function call a recursive helper function to operate on the internal data.
      • If the helper function doesn't need to use any data members from the containing class instance, declare it static.
    • When you write insert and exists yourself, we expect you to use a recursive approach (using recursive helper functions).
  • In-order traversal:
    • Visits the nodes in the tree in sorted order
    • Recursive algorithm: do-the-left-subtree, do-the-value, do-the-right-subtree.
  • Static member functions:
    • Don't operate on an instance of the class (i.e., no this object).

(When logged in, completion status appears here.)