Test #2 Flashcards
Why do we want the initial data of a BST to come in randomly?
so the BST fills in instead of becoming a linked list
What is an AVL tree?
BST that remains balanced upon insertion or deletion
What does AVL stand for?
Adelson, Velskii, and Landis whom are the inventors
Why do we want to balance a tree?
peak efficiency: makes O(log n) instead of worst case being O(n)
What is a splay tree?
a BST that moves each node that is accessed into the root node
What does the word splay mean in general?
spead out or scatter
Why do we want to splay a tree?
because 90% of the accesses of a BT occur on only 10% of the data.
What is the 90/10 rule?
When 90% of the accesses of a BST occur on only 10% of the data
AVL tree vs splay tree uses
splay : fast lookup on recently used items
AVL : if lookup is a lot more common than insertion/deletion
Hashing definition
technique that maps a key to its corresponding hash value
When and why do we want to use hashing as compared to binary search trees?
Best and avg case of O(1)
What are some common applications that use hashing?
Password verification, part lookup
What constitutes a good hashing function?
Load Factor (% of slots in use) is kept under 50% to minimize collisions and to have more wiggle room. Once 50% is reached, double size of table and rehash.
What is a collision?
when two keys are hashed to the same location
What is a perfect hash function?
no collisions
Linear probing
algorithm looks for the next available slot in the hash table to store the collided key.
What is clustering?
Quadratic probing
Chaining
way to handle collisions using an array of pointers out to a linked list of all keys that hash to that location
Folding (be able to implement in different ways)
when a key which is a string is converted into an integer for hashing
What is this?
used to reference both the data members and member functions of an object
Does this mean the same thing as this does in java?
has the same usage however in c++ it is a pointer, so u must de reference
The differences between structs and unions
Unions only hold one active value
What are the advantages of unions?
memory efficiency since only one field contains data at a time
What is a variant record and why is it used?
record type that can have different sets of fields. example: personnel with names, integers for ids
What is namespace scope?
provides a scope to the identifiers. used to prevent name collisions
Why do you need the using directive with a given namespace?
using provides access to all namespace qualifiers and the scope operator
What scope do cin and cout belong to?
std
Balanced BST vs Hashing ( BST )
built using dynamic memory
worst/average case runtime to insert or search for n items: O n log n
can easily obtain a sorted listing of all elements, find a minimum or maximum, or search for a range of values
Balanced BST vs Hashing ( Hashing )
fixed overhead for array representing table
worst case runtime to insert or search for n items is O n^2
avg case run time is O(1) for searches/insertions
cannot get a sorted list or find the minimum or maximum element
what happens when you declare a class inside another class as a friend?
Classes declared as friends to any other class will have all the member functions as friend functions to the friend class
Secondary Clustering
Unable to add an element in quadratic probing because the index calculated is never empty
