Term
| Abstract Class Requirement |
|
Definition
| One of more pure virtual functions |
|
|
Term
| Virtual Descructor - When to use |
|
Definition
All descructors in base classes MUST be virtual
( ex - virtual ~CuveV() ) |
|
|
Term
|
Definition
Use - so we don't need to write the function for various types
put this before function:
template
T maximum(T a, T b) {} |
|
|
Term
| Syntax for calling parent conscructor Shape(length) in derived class Square with length |
|
Definition
| Square::Square(double length): Shape(length) { } |
|
|
Term
| How do I compile a main.cpp file? What is in a main.cpp file? |
|
Definition
g++ -Wall filename.cpp -o filename
./filename
int main() { return 0; } |
|
|
Term
|
Definition
| declare in public section of base class |
|
|
Term
|
Definition
|
|
Term
| insertAtFront/Remove at front - Array List (run times, resize strat) |
|
Definition
Double the size of the array
Total time complexity O(n)
Each insertion is O(1) (amortized) |
|
|
Term
| insertAtFront/remove front from linked list |
|
Definition
| O(1) - pointer manipulation |
|
|
Term
| Insert/Remove an GIVEN element in an array list |
|
Definition
|
|
Term
| Insert/Remove an GIVEN element in a linked list |
|
Definition
| O(1) - pointer manipulation |
|
|
Term
| Insert at arbitrary element for array/linked list |
|
Definition
|
|
Term
|
Definition
| Similar to array list, when out of size then double it |
|
|
Term
|
Definition
Two parts:
In implementing class
::begin(); return a iterator to beginning
::end(); return a iterator one past the end
In the iterator class
base class: std::iterator
it requires us to implement basic functionality:
operator++; move to the next
operator*; dereferencing operator: returns data
operator!=; not equal operator: to check the end |
|
|
Term
|
Definition
| Every element either has 0 or 2 children |
|
|
Term
|
Definition
|
|
Term
|
Definition
| A perfect tree except for last level, all bottom nodes pushed to left |
|
|
Term
|
Definition
|
|
Term
|
Definition
|
|
Term
|
Definition
|
|
Term
|
Definition
| Transversal - visit every element, search, find specific element |
|
|
Term
|
Definition
| Breadth first search - visit nearby nodes. Visit all children before going deeper |
|
|
Term
|
Definition
Depth first search - find a path to endpoint quickly
Similar to inorder transversal |
|
|
Term
|
Definition
| everything on left side is smaller than root, evyerthing on right side is larger than root |
|
|
Term
| Find operation big O in a binary search tree (avg, worst case) |
|
Definition
| Avg = log(n) , worst case O(h) in terms of tree height - want to keep it small |
|
|
Term
| Insert binary search tree worst/avg case |
|
Definition
| O(h) worst case, O(log(n)) best case |
|
|
Term
| Delete Binary search tree runtime (avg/worst) |
|
Definition
|
|
Term
|
Definition
Left heavy trees += add to b, right heavy trees -= subtract from b
|b| <= 1 means it's balanced |
|
|
