Define what it means for a tree to be balanced.
Each node has the same number of dependents on each side
What is the purpose of a hash function?
Hash functions return a value for a search key that is within the size of the
Define "Open Addressing" in reference to a hash table.
Only one item per index position is permitted
Define "Separate Chaining" in reference to a hash table.
Each element in the array points to a linked list, permitting more than one item
per index position.
Define what is meant by "Collisions" in reference to a hash table.
Hash function returns an index of an occupied position.
Define "Linear Probing" in reference to a hash table.
Stepping by 1 to search for an available index position.
Define "Quadratic Probing" in reference to a hash table.
Stepping by the square of the step number to search for an available index
Define "Double Hashing" in reference to a hash table.
Hash the value by a second hash function and use that value as your step value.
What should be true of a table size in order for hashing to be successful?
Table size should be large and a prime number
How is a location determined for strings in a hash table?
Words are converted to numbers.
What is the main characteristic of a Heap (Priority Queue)?
The value with the highest priority is at the top of the queue, and is the next value to be removed.
What are the 2 characteristics of a Red-Black tree?
What are the 2 actions for balancing a Red-Black tree?
What are the 2 characteristics of a Binary tree?
Explain the process of in-order traversal.
Explain the process of pre-order traversal.
Explain the process of post-order traversal.
What are the 3 value/children configurations for nodes in a 2-3-4 tree?
What are the formulas for parent, left child, and right child in a heap?
What are the 4 rules governing Red-Black trees?
Explain insertion into a heap and the trickle-up process.
Place new value in last available position.
Repeatedly swap the new value with it's parent as long as the parent is smaller than the new
Explain deletion from a heap and the trickle-down process.
Swap the first node with the last.
Repeatedly swap the parent with it's larger child until it is larger than both it's children.