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 N1 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(N1)/4 

