Terminology: node, path, root, internal node, leaf, subtree, parent, child, sibling, depth of a node, depth of a tree, height of a node, height of a tree, branch factor
Understand the difference between a general tree, a binary tree, and a binary search tree. Why would one choose to use one over the other?
Be able to write the pseudocode to:
find an item in a BST,
insert an item into a BST,
delete an item from a BST,
and perform a preorder, inorder, or postorder traversal of a general binary tree.
Know the operations for the BST ADT. Know what the inputs to and outputs from each operation would be.
Be able to write class definitions for a binary tree, a BST, and a tree node given a specification in English.
Hash Tables and Hashing
Understand why one would use a hash table for the storage and retrievel of data.
Understand what the following are: hash function, key, division method, multi-part hash function, collision, probing, separate chaining, open addressing.
Know why collisions occur and what can be done to solve this problem.
Given the description of a set of data (e.g., student records), be able to pick an appropriate key and an appropriate hash
function based on this key. You should be able to produce a hash function for an arbitrary key type (some creativity required).