Exam 3 Review Topics
(Chapters in 5th Ed.: 14, 17, and 18)
Sorting and Big-O Analysis
- selection sort
- insertion sort
- merge sort
- number of comparisons/swaps
- Big-O analysis
o quadratic, n log(n)
- measure runtime in Java
Tree Terminologies
- nodes: root, leaf, internal node
- parent, child, ancestor, descendant
- level, height
- full, complete, balanced, empty
- path, branch
- subtree
Binary Tree Traversal
- left/right child/subtree
- in-order traversal
- preorder traversal
- post-order traversal
- representing a (complete) binary tree with an array
- efficiency
Binary Search Tree
- recursive definition
- find
- add
- remove
o a leaf node
o a node with one child
o a node with two children
- code
Generic Programming
- type variable, such as <E>
- implementing generic classes
- using generic types (interfaces, classes) in Java code
Quiz 3 Topics