Term
|
Definition
| root, left subtree, right subtree |
|
|
Term
|
Definition
| left subtree, root, right subtree |
|
|
Term
|
Definition
| left subtree, right subtree, root |
|
|
Term
|
Definition
| Sequential (each level is traversed before moving to the next level) |
|
|
Term
|
Definition
| the height different between any given node and it's two subchildren is at max 1 |
|
|
Term
|
Definition
* Left subtree, left child
* Right subtree, right child |
|
|
Term
|
Definition
* Left subtree, right child
* Right subtree, left child |
|
|
Term
| AVL - Running Time Analysis |
|
Definition
|
|
Term
| Hash Tables - Seperate Chaining |
|
Definition
| Collisions dealt by creating a seperate array (Linked List) |
|
|
Term
| Hash Tables - Seperate Chaining Methods |
|
Definition
|
|
Term
| Hash Tables - Seperate Chaining Requirements |
|
Definition
Tablesize Prime
No more than half full |
|
|
Term
| Hash Tables - Seperate Chaining Runtime Analysis |
|
Definition
|
|
Term
| Hash Tables - Open Addressing |
|
Definition
| Resolves collisions by sending them to a different place in the array |
|
|
Term
| Hash Tables - Open Addressing Problems |
|
Definition
Tablesize Prime
No more than half full
Linear Probing has primary clustering
No Duplicates
Elements not deleted, set to inactive |
|
|
Term
| Hash Tables - Open Addressing Quadratic Probing |
|
Definition
| position(x) = (hash(x) + i^2) % tablesize |
|
|
Term
| Hash Tables - Open Addressing Linear Probing |
|
Definition
| position(x) = (hash(x) + i) % tablesize |
|
|
Term
| Hash Tables - Open Addressing Runtime Analysis |
|
Definition
|
|
Term
|
Definition
Compares two elements to see if they are in correct order. if not, swaps them. Runs N-1 times (through entire list)
*Smaller elements 'bubble' to the top |
|
|
Term
| Bubble Sort Runtime Analysis |
|
Definition
Best: O(N) [sorted]
Avg: O(N^2)
Worst O(N^2) |
|
|
Term
|
Definition
| Starts at front, tries to add element and then creates a new list and continues to add elements to list in correct order |
|
|
Term
| Insertion Sort Runtime Analysis |
|
Definition
Best: O(N) [sorted]
AVG: O(N^2)
Worst: O(N^2) |
|
|
Term
|
Definition
| Go through list finding the smallest element, and put it at the front. Continue through entire list. |
|
|
Term
| Selection Sort Runtime Analysis |
|
Definition
|
|
Term
|
Definition
A pair of elements in the incorrect spot
Avg # of inversions given by: N(N-1)/4 |
|
|
