CSCI 362 -- Exam 2 Review

Trees:

  • complete vs. full vs. non-complete
  • binary trees
  • TreeNode
    • keeping track of a parent (or not)
  • traversals:
    • inorder, preorder, postorder
  • operations:
    • depth()
    • countLeaves()
    • countInterior()
    • size()

Binary Search Trees:

  • ordering requirement
  • operations
    • minimum()
    • maximum()
    • successor()
    • predecessor()
    • find()
    • insert()
    • erase()
  • know the complexities of each!

Heaps:

  • priority queues! (Similar abstraction to queue)
  • ordering requirement
  • shape requirement
  • representation with vector/array -- index calculations for parent/children
  • operations:
    • push
    • pop
    • top
    • upHeap() / sift_up
    • downHeap() / sift_down
    • buildHeap() / make_heap
    • heapSort()
  • know the complexity for each operation (hint: height of tree)

Hash Tables:

  • vector of slots
  • average complexity for insert/erase/find
  • worst case for insert/erase/find
  • "hash function" -- what is it? What does it do?
    • goals
  • open addressing vs. separate chaining
    • how are collisions resolved for each
  • load factor of hash table
    • why would we want to change the table size?

Balanced Binary Search Trees

  • Why do we need balance?
  • "Good" insertion sequence vs. bad insertion sequence
  • Types of balance
    • depth of left and right differ by at most one (AVL)
    • all leaves exist at same level (2-3-4)
    • black node count along path from all leaves is same (red-black)
  • 2-3-4 trees
    • insertion into tree
      • spliting of 4-node (hoisting)
      • "adding" new elements at the leaf level
      • conversion of 2-node to 3-node
      • conversion of 3-node to 4-node
    • tracing insertions
    • how do we "search" for a value?
  • Red-black trees
    • invariants:
      • insertion ALWAYS as a red-node
      • root always black
      • two red nodes cannot be parent-child of each other
      • black node count along path from all leaf nodes are the same
    • conversion from 2-3-4 to RB
    • how do we "search" for a value?
    • how do we insert?
      • model what happens with 2-3-4 trees
      • rotations when red has red child
        • left rotate vs. right rotate
        • double rotate

Associative Containers:

  • Set (understand completely)
    • implemented with?
    • "const" iterators -- why?
  • Map
    • know the API for access and insertion and removal
    • implemented with?
  • unordered_set, unordered_map
    • implemented with?
    • difference from set/map
  • multi* vs non-multi
    • API differences