Exam 4

Exam 4 covers trees and forests of trees of all sorts.

Exam 4 is 50 minutes long and only has short answer and multiple choice questions.

Topics Covered

• AVL Tree
  • Difference between a “Tree”, “BST”, and an “AVL”
  • Operation find, including running times in terms of h and n
  • Operation insert, including running times in terms of h and n
  • Operation delete, including running times in terms of h and n
  • Strategy for a 2-child delete
  • AVL Tree Rotations
  • Minimum/maximum nodes in an AVL tree
• BTree
  • Difference between a key and a node in a BTree
  • The order of a BTree
  • Structural properties of a BTree
• Huffman Trees
  • Tree construction
  • Encoding
  • Decoding
• K-d trees
  • constuction
  • find nearest neighbor
• Heaps
  • Construction of a Heap
  • Heap runtime
  • HeapifyUp
  • HeapifyDown
  • Array Representation
  • Priority queue ADT
• Disjoint Sets
  • Union
  • Smart Union (Size and Height)
  • Find
  • Path Compression
  • Array Representation
  • Disjoing Set Runtime
  • Union-Find (Disjoint Sets) ADT

  Assignments referenced:

• mp_traversals, mp_mosaics
• lab_avl, lab_btree, lab_huffman, lab_heaps

Points:60

Start: Thursday, November 03

End: Saturday, November 05