## Lecture 31 - 04/07

### Midterm 2 Review

• In the various data structures, what are the runtimes for various operations (like insert, remove, contains, ...), and how do they have to do with the size of the input N$N$ or the height of the tree, etc..?
• Disjoint sets
• Quick Find
• Quick Union
• Weighted Quick Union
• Weighted Quick Union with Path Compression
• Amortized runtime: finding the average time per call
• Runtime of heaps with and without resizing capabilities (no resize is logarithmic, resize is linear)
• Self balancing trees:
• 2-3 Trees
• 2-3-4 Trees
• 2-3-... B-Trees
• LLRB's (Left Leaning Red-Black Trees) - 2-3 tree in disguise
• Search trees versus hashing structures versus heaps
• Implementations and how Abstract Data Types (ADT's) work under the hood
• Priority queue implementations with different structures
• Graph searches and traversals
• Regular Expressions